新型影响力最大化算法

宋 伟，梁 霖，李 锋

(1.南京邮电大学通信与信息工程学院，江苏南京210003;2.华为技术有限公司，北京100094)

近几年，随着互联网技术的进步，各种大型复杂社交网络不断出现。如何从复杂网络中选取初始节点集来传播信息，使得信息接受最大化已成为社会网络领域研究的热点。且在疾病传播、产品推广、社会稳定、舆情扩散和故障控制等方面都有着十分重要的应用。

针对影响力最大化问题，很多研究者针对某一具体的网络结构提出了不同的算法，如贪心算法、Maxdegree算法等。目前，大部分研究认为，具有越多链接的节点影响力越大［1］，位于网络越核心位置的节点，在传播过程中所起的作用越大［2］。

对此，文献［3］提出了不同的看法并通过调查分析指出对于单个传播源而言，度最大的节点并不一定是最具影响力的节点，通过K-shell分解得到的K-shell值最大的节点才是最有影响力的节点。而对于多个传播源网络，度大的节点往往比K-shell值大的节点具有更好的传播效果。因为K-shell值大的节点往往都聚集在网络核心部位，传播过程中存在交叉感染现象，出现较大允余。

文献［4］指出不同的网络拓扑结构也会对传播效率产生影响，并通过实验证明在网人数和传播路径等因素均相同的条件下，clustered-lattice network比random network传播效果更好。文献［5］也通过数据分析发现同一个社团的朋友发出的邀请，影响力不如不同社团的朋友，同一社团中度大的朋友影响力更大。

在此背景下，本文基于线性阈值模型(LT)提出了新的初始节点选择算法——基于社区的影响力最大化算法，利用LT模型的影响力累积特性，以扩大最终的影响范围为目的，兼顾时间复杂度来研究社会网络中的影响力最大化问题。

1 相关工作

1.1 贪心算法

Kempe和Kleinberg等人曾在2003年提出使用贪心算法来求解影响力最大化问题，以下简称KK算法。KK算法的基本思想是:设最初的初始节点集合S=∅，将k个初始节点的选择过程分为k步，每一步都选择当前网络中边际影响值最大的节点加入集合S，以得到局部最优解，直到|S|=k，即为最有影响力的初始节点集合S。该算法虽然能保证至少得到最优解的63%［6］，但是由于每一步初始节点的选择，都要重新计算网络中所有未激活节点的边际影响值，所以时间复杂度相当高，这对于拥有成千上万个节点的大型网络来说并不适用。

1.2 Maxdegree算法

Maxdegree算法是经典的启发式节点重要性排序方法，它将网络中的节点按度值大小进行排序，选取邻边数目最大的k个节点作为初始节点［7］。该算法认为节点的度值越大，网络中与其相连的节点越多，则该节点在网络中的影响力越大。以度作为节点的重要性指标进行排序，它的优点是对于任意节点数量的网络而言，时间复杂度均很低，仅为O(E+NlbN)，其中E为网络中的邻边数量，N为节点总数。但该算法也有其明显的缺点:在选取初始节点时，最具影响力的节点，其邻居节点可能有较多的重合，冗余度增加，不利于信息更有效地传播扩散;有些位于网络中不同位置(核心和边缘)的节点虽然度值相同，但其重要程度不同，所以单靠度来排序并不科学。

2 基于社区的影响力最大化算法

由于KK算法的时间复杂度很高，并不适用于大型的复杂网络;Maxdegree算法虽然时间复杂度很低，但没有考虑网络结构的问题。现实的复杂网络通常含有大量节点，节点与节点之间有着紧密的联系，所以将网络划分为若干社区对于研究复杂网络中的信息传播具有重要意义。基于此，提出了一种新型的混合式影响力最大化算法——基于社区的影响力最大化算法。该算法利用LT模型的影响力累积特性，综合考虑了KK算法和Maxdegree算法的优劣，将复杂网络中初始节点的选择过程划分为以下3个阶段。

2.1 划分网络阶段

该阶段利用复杂网络的社区性，使用社区发现算法将社交网络划分为若干个社区。国内社区发现算法研究者姜秀芳等人曾提出一种基于社区紧密度的快速发现算法(FHACC)来划分网络［8］。该算法使用紧密度矩阵来表示各节点之间的紧密程度(每个社区抽象为一个节点)，节点之间共有的邻居节点数目越多，紧密值越大，根据得到的紧密矩阵，将紧密值最大的节点进行合并，不断迭代，直到迭代后社区的个数和各社区内的节点不再变化，迭代终止。该算法的时间复杂度很低，仅为O(mk+mt)，其中m为网络中连边的总数，k为所有节点的平均度值，t为迭代次数。用该方法将复杂网络划分为多个社区，有以下几点好处:1)划分出的各社区内部，节点的紧密程度、相似度增加，使信息更容易在社区内部传播;2)启发阶段初始节点的选择分散在各社区中，有效避免了节点选择过于集中问题，提高了信息大范围传播的可能性和传播速度。

2.2 启发阶段

划分社区后，根据每个社区的节点数占全网络节点总数的比值，在各社区内部按度值大小选取相应数目的初始节点，共计「ck⏋个。如复杂网络中的节点总数为2 000，启发阶段共需选取12个初始节点，划分为2个社区后，社区1和社区2的节点数分别为1 503和497，则社区1和2选取的初始节点个数为9，3(「(1503/2000)×12⏋=9)。各社区内初始节点的选择按度值排序主要因为:划分社区后的复杂网络，社区内部节点的紧密值增加，此时，度越大的节点在社区中重要性越大，对邻居节点的影响程度也越大;其次，初始阶段的复杂网络含有大量未激活节点，使用时间复杂度较低的Maxdegree算法更有利于信息高效地传播与扩散。

2.3 贪心阶段

经过划分社区和启发阶段之后，网络中未激活节点的数目大大减少，使用贪心算法从整个网络剩下的未激活节点中选择最具影响力的k－|ck|个节点加入初始节点集，不仅可以让“累积”大量影响力的未激活节点一触即发，更扩大了传播的影响范围。设启发阶段初始节点集合为sq，贪心阶段初始节点集合为sg，则s=sq∪sg就是复杂网络中影响力最大的初始节点集合。

基于社区的影响力最大化算法框架的伪代码如下:

输入:社会网络图G(V，E)，初始节点个数k。

输出:影响力最大的k个初始节点集合s和最终被影响的节点总数。

1)读取网络;

2)使用FHACC算法根据紧密矩阵将复杂网络划分为n个社区;

3)初始集合S=∅，k1=，k2=k－;

4)根据各社区内节点数目，在第i个社区(i=1，…，n)选取ki个度值最大的节点加入启发阶段初始节点集合

sq中，使得最终sq的节点总数为k1，即ki=k1;

5)基于集合sq激活尚未激活的节点;

6)循环j=1到k2;

7)计算当前所有未激活节点的边际影响值;

8)选择边际影响值最大的节点u;

10)基于集合si+k1激活尚未激活的节点;

11)结束循环。

3 实验和评估

上文介绍了基于社区的影响力最大化算法的设计与框架。本节主要在美国大学足球联盟的数据集上验证该算法的有效性，并验证该算法的传播效果优于已提出的部分算法。Football数据集是2000年美国大学秋季常规赛的关系数据，节点代表球队，边代表球队之间存在比赛关系。简化后的网络拓扑中共有115个顶点、613条边，使用FHACC算法经历5次迭代后，网络被划分为12个社区，划分结果如图1所示。

图1 社区划分图

对不同的初始节点数目k和参数c进行实验，模拟实验次数为50次，实验结果为50次结果取平均。实验效果如图2所示，横坐标为初始节点的数目，纵坐标为最终被影响的节点总数。当初始节点总数一定时，c取值不同，最终的影响效果不同。c=1时，为Maxdegree算法，影响效果最差;c=0时，为KK算法，相比于其他的c值，传播效果略差。由图可知，当c=0．5时，本文提出的算法传播效果最好，且随着初始节点数量的增多，被影响的节点总数呈递增趋势。

图2 变量c不同取值时传播效果对比

其他的初始节点选择算法，如随机算法、Maxdegree算法、KK算法，在取不同总数的初始节点时，与本文提出的基于社区的影响力最大化算法相比，最终影响的节点范围如图3所示。

图3 不同算法传播效果对比

可知，基于社区的影响力最大化算法其传播效果均优于之前提出的随机选择算法、Maxdegree算法、KK算法等，且随着初始节点数量的增多，相比于其他算法，传播效果越好。前面主要对算法的最终影响范围做了比较分析，下面对算法的时间复杂度进行比较。比较结果如表1所示。

表1 算法时间复杂度比较

可见，本文提出的算法在时间复杂度上也明显优于KK算法。

4 总结

基于线性阈值模型，本文综合考虑了贪心算法和Maxdegree算法的优劣，指出信息在网络传播之前，可以根据节点之间的紧密程度和相似性将复杂网络划分为多个社区。并基于此提出了一种新型影响力最大化算法——基于社区的影响力最大化算法。将此算法在美国Football联盟数据集上进行了验证，实验结果表明，该算法相对于未划分社区的网络来说，传播速度和范围明显上升，时间复杂度较KK算法也有显著改善。

虽然基于社区的影响力最大化算法在综合考虑影响范围和时间复杂度的基础上较之前有较大提升，但仍然存在很多需要改进和提高的地方。比如划分社区算法的改进;划分社区之后启发阶段初始节点的选择使用的是时间复杂度较低的Maxdegree算法，仍然会存在邻居重叠的现象等。

:

［1］ PASTOR-SATORRAS R，VESPIGNANI A.Epidemic spreading in scale-free networks［J］.Phys.Rev.Lett.，2011，86(14):3200-3203.

［2］ CHEN Wei，WANG Yajun，YANG Siyu.Efficient influence maximization in social networks［C］//Proc.15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris，France:ACM Press，2009:199-208.

［3］ KITSAK M.Identifying influential spreaders in complex networks［J］.Nature，2010(7):1-36.

［4］ CENTOLA D.The spread of behavior in an online social network experiment［J］.Science，2010(325):56-78.

［5］ UGANDER J，BACKSTROM L.Structural diversity in social contagion［J］.Proceedings of the National Academy of Sciences，2012，109(16):5962-5966.

［6］ GOYAL A，LU W，LAKSHMANAN L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks［C］//Proc.20th International Conference Companion on World Wide Web.Hyderabad，India:［s.n.］，2011:47-48.

［7］ KEMPE D，KLEINBERG J，TARDOS E.Maximizing the spread of influence through a social network［C］//Proc.9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ［S.l.］:ACM Press，2003:137-146.

［8］姜秀芳.面向复杂网络的社区发现算法研究［D］.西安:西安电子科技大学，2011:25-34.