社会网络中基于社群衰减的影响力最大化算法

孙子力 彭舰 仝博

摘 要：针对现有网络传播模型忽略了信息传播过程中的信息衰减，传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题，提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化（IMID）算法（Influence Maximization On Internal Decay）。首先对整个社会网络进行社群结构划分，评估社群中节点影响力范围，并考虑社群之间关联点之间的关联概率，在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析，该算法不仅降低了时间复杂度，还获得了接近贪心算法的影响力传播范围，影响覆盖率达到90%以上。因此，在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点，会让信息以最小的代价在网络中获得广泛传播。

关键词：信息传播;影响力最大化;社会网络;社群划分

中图分类号： TP301.6

文献标志码：A

文章编号：1001-9081（2019）03-0834-05

Abstract： The existing network transmissionspread model ignores the information attenuation in the process of information transmissionspread， and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence transmissionspread range. To solve these problems， an algorithm of Influence Maximization on Internal Decay （IMID） based on community structure was proposed. Firstly， the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated. Then， with spread probability of association points between the communities considered， the attenuation degree of information spread between nodes was calculated. Experimental and analysis results show that the proposed algorithm not only reduces the time complexity， but also obtains the influence transmission range near that of greedy algorithm， with influence coverage over 90%. Therefore， with several nodes selected as the initial nodes between the core seed node set and connected communities， information will be widely disseminatedspread in the network at the minimum cost.

Key words： information spread; influence maximization; social network; community division

0 引言

目前，移動设备和互联网的发展为信息传播提供了巨大的便利，社群网络的发展形成了一个又一个的社会网络，如Facebook、Twitter以及国内的微信朋友圈、微博、QQ等。从线上到线下，人们的决定也被不同的社会网络所影响。社会网络在信息的传播扩散过程中发挥了非常重要的作用。从大规模社群网络中寻找k个节点使得某一事件传播范围最广，这是传统社群网络所关心的问题。但是社群网络复杂多样，除了传统基于独立节点的社群网络意外，基于社群的社群网络也越来越多，例如豆瓣兴趣小组、微信朋友圈等。一个社群表现出来的特性是社群之间的联系较少，但是社群内部的联系度较高。例如一个家庭在决定是否要第二个孩子的时候，受家庭内部影响较大，而社群外部影响较小。因社群关系距离远近对一个群体性决定又产生不同影响，这说明信息即使在社群内部也是存在衰减的，节点层级增大，增加节点所带来的信息增益也越来越小，因此，在社群网络中研究衰减情况下影响力最大化问题变得越来越重要。挖掘社会网络的影响力关键节点，解决社群网络的影响力最大化问题、提高算法效率是一个值得研究的领域。

近些年，影响力最大化问题得到工业界和学术界的广泛研究与讨论。Kempe等[1]将影响力最大化问题定义为一个离散的优化问题，证明了影响力最大化是一个NP难的问题，并提出了近似比为（1-1/e）的爬山贪心算法;但是时间复杂度较高，并不能解决现实情况下影响力最大化问题。IMID算法通过社群划分，缩小单一计算单元，提高时间复杂度。Leskovec等[2]利用次模函数减少在影响力传播过程评估次数的CELF（Cost-Effective Lazy Forward）算法。Goyal等[3]受CELF影响提出了CELF++算法，CELF++算法将同时计算节点u相对于S∪{u}的边际增益，而CELF则需要两轮蒙特卡罗模拟，因此可以提高时间效率;但CELF++算法依旧要进行多次蒙特卡洛模拟，因此无法高效处理大规模社群网络情况。而IMID算法并没有使用蒙特卡洛模拟，而是简化边际影响力计算，从而提高影响力计算效率。Chen等[4]通过考虑已经选择的节点对当前候选节点的影响提出了SD（SingleDegree）算法，SD算法对所有节点都基于度进行排序，然后迭代选择具有最大度数的节点并添加到种子集合S中。SD算法在影响力传播方面有较好的表现，但是它并没有考虑特定的信息传播模型，所以对性能的提升非常有限。IMID算法引入社群衰减，通过社群衰减度对社会关系建模，更准确描述不同类型的社会关系对信息传播的影响。Zhu等[5]通过研究有限的传播距离和影响传递性提出了半规划的算法，但是半规划算法忽略社群结构的影响。文献[6]中结合时间连续马尔可夫链与独立级联模型（Independent Cascade Model， ICM）进行影响力最大化分析，考虑了影响最大化问题的分布传播问题，考虑了时序对信息传播的影响，但是没有考虑网络结构边界点的传播概率。IMID算法在选择初始节点的时候考虑核心种子节点和社群边缘节点对局部影响力传播的影响。文献[7]中考虑了社区结构，并通过组合熵的方法来将较小的社区合并为一个大的社区，网络的切割让边际节点的影响力传播计算效率低下，整个算法的时间复杂度非常高。IMID算法不仅降低时间复杂度，还获得了贪心算法的传播范围。

本文利用斯坦福大学SNAP（Stanford Network Analysis Project）的公开数据来进行影响力计算，并获取种子节点。通过将大规模社群网络进行社群聚合，并考虑传播概率以及信息衰减，本文提出一个基于社群衰减的影响力最大化（Influence Maximization on Internal Decay， IMID）算法，实验结果相对于由文献[8]提出的独立路径算法（Independent Path Algorithm， IPA），以及Degree和SD算法，受影响节点更多，信息传播范围更广，并且时间复杂度更低。本文的主要工作有：1）分析在社群网络中影响力传播过程;2）针对社群内部的信息衰减情况，建立UARM（User Attenuation Rating Mechanism）机制，并根据用户衰减机制提出了新的传播模型，分析了在衰减模型下，社群内部的信息传播过程;3）提出一种基于社群结构的影响力最大化IMID（Influence Maximization on Internal Decay）算法，在群衰减的社群网络中获取种子节点。

IMID算法并没有使用蒙特卡洛模拟，而是简化边际影响力计算，从而提高影响力和计算效率。IMID算法引入社群衰减，通过社群衰减度对社会关系建模，更准确描述不同类型的社会关系对信息传播的影响。IMID算法在选择初始节点的时候考虑核心种子节点和社群边缘节点对局部影响力传播的影响。IMID算法不仅降低时间复杂度，还获得了贪心算法的传播范围。

1 社群衰减信息传播模型

在传统社群网络影响力最大化问题中，独立级联模型和线性阈值模型使用较为广泛，但是独立级联模型与线性阈值模型没有考虑社群结构和衰减度对信息传播的影响，针对传统影响力传播模型的缺陷，本文提出社群衰减信息传播模型并给出相关定义。

社群内部内部节点集NCi对社群内部影响较大。虽然边界节点集Nbi对社群内部影响较小，但它是社群之间的纽带，对社群之间的影响力传播影响较大。对于社群衰减模型，在候选节点集中选择k个节点，经过k个节点使得信息传播范围最大。

社群衰减模型是基于独立级联模型的改进模型，相比于独立级联模型，社群衰减模型增加社群结构，并调整社群内部节点和边界节点的选取比例。社群网络之间连接稀疏，即边界之间的联系较少。如果忽略边界点之间的联系，信息在社群之间便无法传播。在选取k个影响力种子节点时，k-k′个节点从边界点集合Nb中获取，k′个节点从社群内部节点获取。

对于一个给定的社会网络，首先使用Louvain算法对整个大规模网络进行社群划分，Louvain算法基于模块化优化，并已经被证明在社群划分方面有很好的性能表现。得到社群结构以后，将整个信息传播过程如图1所示分为两个阶段：1）种子节点的扩散;2）社群内部的传播。

1）种子节点的扩散。

这一阶段的目的是使信息在不同社群之间进行传播。初始的种子节点S向S的邻居节点集N（S）传播，由此产生第二阶段点集N（S），N（S）可能分布在不同的社群内部，种子节点的初始信息便传递到了不同社群内部。对于第二阶段节点集合中任意一一个节点v∈N（S），在种子扩散阶段被激活的概率为：

2）社群内部的传播。

在这个阶段，影响力只会在社群内部进行传播。社群内部的影响力传播彼此独立并且互不干涉。

定义3 社群影响力。对于某个社群C′，初始时刻只能被种子节点S及其邻近节点所影响，所以社群集合的影响力可以定义为：

单一社群的影响力是社群节点影响力的累加和。根据式（6）可以将社群内部节点分为种子节点的子集和非种子节点子集。式（7）中|S∩C′|表示第一阶段种子节点传播过程中影响力数值大小，其中C′表示内部节点集合，式（7）后半部分表示社群内部传播过程中影响力的提升，二者相加就可以得到社群的影响力大小。在获取每一个单一社群的影响力之后就可以计算得到整个社群网络的影响力传播范围。

2 基于社群衰减的影响力最大化算法

本文提出了一个基于社群衰减的影响力最大（Influence Maximization on Internal Decay， IMID）算法，根据社会网络结构进行社群划分，然后获得使影响力传播范围最大的种子节点集合，即：

IMID算法的核心思想是简化全局影响力计算，在计算社群节点边际影响力的过程中，需要证明全局影响力的目标函数是一个次模函数。定理1用以证明σ（S）是一个次模函数。

通过影响力功能函数的次模属性和单调性，Kempe的爬山贪心算法确保了（1-1/e-ε）的近似比，σ（S）的近似估计可以替代时间复杂度较高的蒙特卡洛模拟，通过影响力最大化目标函数的次模属性可以获得每个节点增加到种子节点时的边际增益，进而IMID算法伪代码如下：

其中EIIA（G，S，u， ρ）用以计算d（v，u）<4时，新增一个节点的有效影响力增益。对于一个给定的社群网络，IMID算法的贪心策略比传统的贪心算法时间复杂度更低，因为IMID算法没有使用蒙特卡洛计算影响力变化。对于一个给定的节点u，尝试计算节点u加入到种子节点以后影响力变化时，可以使用衰减模型中影响力动态变化来计算影响力增益值。EIIA（Efficent Incremental Influence Algorithm）的伪代码如下：

3 实验与分析

3.1 实验数据

本文实验使用NETHEPT、DBLP两个公开数据集，其中包括用户ID、社群划分、边集等信息。

NEHEPT和DBLP是有关学术论文领域作者之间联系的数据集，如果作者i与作者j之间合作过一篇文章，那么这两个节点之间就有一条无向边。数据集中Nodes表示节点数码，Edges表示边的数量，Communities表示数据集中社群的数量。NETHEPT包含15200个节点，31300条边，2200个社群结构。DBLP包含317000個节点，1000000条边，11900个社群结构。Max_Degree代表了社群网络中节点度的最大值，用以影响力传播范围的计算。Avg.Com.Size表示社群网络中平均节点数目，用以表示社群规模。

3.2 对比算法

本文实验的对比算法主要使用IPA[8]、SingleDegree[4]、Degree[4]三个算法。IPA假设信息只在传播概率大于某个阈值的传播路径上进行传播。SingleDegree算法属于基于中心的启发式算法，在算法的每次迭代过程中都会选择度数最大的节点，然后将该节点加入到种子节点集合中。一旦节点被加入到种子集合中，该节点的邻居节点都会被从候选节点集中删除。Degree算法则是简单从候选节点集合中选取度数最大的节点。

3.3 实验运行环境

本实验运行环境如下：CPU为2.7GHz Intel Core i5，内存为8GB 1600MHz DDR3，操作系统使用OS X。本文实验代码主要使用C++完成。

3.4 实验步骤及结果分析

本文提出了IMID算法，本次实验主要采用Louvain算法对大规模社会网络进行社群划分。Louvain算法基于多层优化Modularity，它能够刻画发现社区的紧密程度，可以被当作一个优化函数，Modularity的定义如下：

Louvain将社群划分为两个阶段。第一个阶段：不断地遍历社群网络中的节点，将单节点尝试加入能够使modularity达到最大的社群中，直到社群网络中的节点都不再变化。第二个阶段：处理第一阶段的结果，将一个个小的社区归并为一个超节点来重新构造新的网络，这时边的权重为两个节点内所有原始节点的边权重之和。迭代这两个步骤直至算法稳定。

在实验中，影响力传播范围显示如果忽略社群之间的弱连接节点，将不能解决社群衰减模型下影响力最大化问题。影响力度量问题与影响力最大化问题是不一样的，为了说明这个问题，定义差异对比函数：

图3的结果显示IMID和Degree算法结果之间的差异随着种子节点数目k增加呈现先增大后平稳下降的趋势。这说明在种子节点数目比较少的时候，两者之间的相似度较高。然而当k的增大的时候Degree算法的前k个节点更加聚合，而IMID算法得到的k个节点则包含了社群之间的弱连接节点。当k值持续增大时，未被检测到的社群之间的连接点变少，差异性呈现平稳下降趋势。

如图4所示，描述在NetHEPT下不同种子节点数目下影响力的传播范围。实验表明在种子节点数目较少时，整个网络中不同算法的影响力传播范围差异较小。在种子节点数节点数超过25以后，IMID相对于SingleDegree和Degree的传播范围差距开始变大;当k=50的时候，IMID算法的传播范围比SingleDegree多了8.64%。

图4是在数据集DBLP下，IMID算法与IPA、SingleDegre、Degree算法影響力传播范围差值的对比。当k=50时，IMID算法的传播范围相对于SingleDegree算法提高了8.6%。

时间效率也是算法研究过程中非常重要的一个指标。表2展示了几个算法在不同数据集下的运行时间。

IMID算法相对于影响力传播范围来说效率非常高IMID算法比其他影响力最大化算法运行效率更高，在k=50的时候，NETHEPT和DBLP上运行时间都小于1s。DBLP有317000节点，相对于IPA提升明显。IMID算法采用二段式传播模型，考虑社群结构对影响力传播的提升。与传统的影响力最大化算法相比，边际节点计算与社群划分可以提高模型算法的并行化程度，从而评估模型时间效率复杂度不高并且比较稳定。

随着种子节点数k越来越大，影响力传播范围的差别越来越大。当k的数值达到50的时候，差别达到最大。基于中心的启发式算法虽然影响力传播范围较好，但是无法提供性能上的保证，在k值超过一定范围的时候，影响传播范围的增速小于IMID算法，这也从侧面说明了社群结构的分阶段传播可以提高影响力的传播能力。

4 结语

为了解决社群网络中考虑信息衰减情况下影响力最大化问题，提出了一个基于社群衰减的信息传播模型，将信息传播分为两个阶段，简化影响力传播的计算方法;并在单独社群网络中快速有效地寻找初始节点，使信息以最小代价在网络中尽量传播。基于社群衰减的IMID算法同时考虑到了边界点的影响力传播问题，减小了因社群划分而导致局部与整体的差异，通过并行处理挖掘每个社群内部有影响力的节点。实验结果证明了IMID算法的有效性和算法效率。后续会继续提高算法的效率和精度，并与基于地理位置的社群网络结合，挖掘出最有影响力的k个用户，为网络信息传播提供理论依据和实践经验。

参考文献 （References）

[1] KEMPE D， KLEINBERG J， TARDOS E. Maximizing the spread of influence through a social network [C]// KDD '03： Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 137-146.

[2] LESKOVEC J， KRAUSE A， GUESTRIN C， et al. Cost-effective outbreak detection in networks [C]// Proceedings of the 2007 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429.

[3] GOYAL A， LU W， LAKSHMANAN L V S. CELF++：optimizing the greedy algorithm for influence maximization in social networks [C]// Proceedings of the 2011 International Conference Companion on World Wide Web. New York： ACM， 2011：47-48.

[4] CHEN W， WANG Y， YANG S. Efficient influence maximization in social networks [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 199-208.

[5] ZHU T， WANG B， WU B， et al. Maximizing the spread of influence ranking in social networks [J]. Information Sciences， 2014， 278： 535-544.

[6] LAMBA H， NARAYANAM R. A novel and model independent approach for efficient influence maximization in social networks [C]// Proceedings of the 2013 International Conference on Web Information Systems Engineering， LNCS 8181. Berlin： Springer， 2013： 73-87.

[7] 郭浩，陸余良，王宇，等.基于信息传播的微博用户影响力度量[J].山东大学学报（理学版），2012， 47（5）：78-83.（GUO H， LU Y L， WANG Y， et al. Measuring user influence of a microblog based on information diffusion[J]. Journal of Shandong University （Natural Science）， 2012， 47（5）： 78-83.）

[8] WANG Y， CONG G， SONG G， et al. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks [C]// Proceedings of the 2010 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 1039-1048.

[9] YU H， KIM S K， KIM J. Scalable and parallelizable processing of influence maximization for large-scale social networks [C]// Proceedings of the 2013 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2013： 266-277.

[10] 吴凯，季新生，郭进时，等.基于微博网络的影响力最大化算法[J].计算机应用，2013，33（8）：2091-2094.（WU K， JI X S， GUO J S， et al. Influence maximization algorithm for micro-blog network [J]. Journal of Computer Applications， 2013， 33（8）： 2091-2094.）

[11] FISCHETTI M， KAHR M， LEITNER M， et al. Least cost influence propagation in （social） networks [J]. Mathematical Programming， 2018， 170（1）： 293-325.

[12] 田家堂，王轶彤，冯小军.一种新型的社会网络影响最大化算法[J].计算机学报，2011，34（10）：1956-1965.（TIAN J T， WANG Y T， FENG X J. A new hybrid algorithm for influence maximization in social networks [J]. Chinese Journal of Computers， 2011， 34（10）： 1956-1965.）

[13] TONG G， WU W， TANG S， et al. Adaptive influence maximization in dynamic social networks [J]. IEEE/ACM Transactions on Networking， 2017， 25（1）： 112-125.

[14] LI Y， FAN J， WANG Y， et al. Influence maximization on social graphs： a survey [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（10）： 1852-1872.

[15] FISCHETTI M， KAHR M， LEITNER M， et al. Least cost influence propagation in （social） networks [J]. Mathematical Programming， 2018， 170（1）： 293-325.