● 摘要
影响力最大化问题是当前社会网络研究的热点问题之一，它最初的研究动机来自于口碑营销。比如，一个初创公司想要推广自己的产品，但推广经费有限，于是它先让一部分有影响力的人免费试用产品，希望他们把产品推荐给自己的朋友等，经推荐后认可了产品的朋友又将产品推荐给各自的朋友，如此构成了社会网络上的级联（cascade）传播。影响力最大化问题的目标是找出有影响力的少数节点（种子节点），让这些节点成为信息传播的源头后，网络上最终级联传播的范围最大（即接收信息的节点最多）。影响力最大化可用于创新推广（产品、技术、政策、知识等）、事件监测（谣言、水污染、传染病等）、专家发现、朋友推荐等等。
影响力最大化的研究主要分为影响力传播模型和基于模型的算法两个方面。本文首先介绍了目前应用最多的两个社会网络传播模型：线性阈值模型和独立级联模型，并分析了两个模型的特点。同时，本文详述了典型的影响力最大化算法。通过分析对比，本文总结了各种算法的优势和不足。本文指出已有的算法是集中式的，面对当前的社会网络规模（数亿节点，十亿到百亿级边）是不可扩展的。 然后，本文介绍并总结了目前大规模网络并行计算的相关技术和方法，提出了基于IRIE（影响力排序与估计算法）的分布式影响力最大化计算框架。在该框架下，本文通过对网络切分和基于BSP模型表达点中心性的图计算，设计了多个分布式算法。算法设计基于试验测试和理论证明，提出了基于消息传递增量更新节点、基于蓄水池机制延迟合并通信等优化方案，旨在保证算法正确性的前提下，减少计算和通信，提高集群并行效率。
最后，本文在大规模的真实社会网络和人造网络上进行了多维度的实验，分析对比了分布式的算法和基于单节点的集中式算法在运行时间、通信量、内存消耗方面的情况。实验结果显示，本文实现的分布式算法运行时间优于集中式算法，并且集群内存消耗总量并未明显上升。其中，精心设计和实现的分布式算法dIRIEr极大地减少了通信开销，算法并行效率显著提升，显示出较高的加速比。在大规模网络上，dIRIEr显示出良好的扩展性，其运行时间随着计算节点增多而持续大幅下降，并且可以处理先进的集中式算法无法处理的超大规模网络。