王 双，李 斌，刘学军，胡 平

（南京工业大学 电子与信息工程学院，江苏 南京211816）

基于社区度的边界节点影响力最大化算法*

王 双，李 斌，刘学军，胡 平

（南京工业大学 电子与信息工程学院，江苏 南京211816）

通常跨社区的信息传播更具有现实意义，而且大范围的信息传播往往也是跨社区的。为此提出一种基于社区度的边界节点影响力最大化算法，利用社会网络中的社区结构对社区中与其他社区有连接边的边界点进行研究，从而缩小选择初始节点的范围，降低时间复杂度。同时为更准确地评估边界节点的影响力，综合节点度、节点所直接相连社区数以及相应社区的规模作为社区度来衡量节点在信息传播中的重要性。最后通过实验验证了本算法相比其他算法具有更大的影响传播范围和更低的时间复杂度。

影响力最大化；社区度；边界节点；社会网络

0 引言

近年来，随着互联网和Web技术的不断革新，影响最大化问题作为社会网络分析领域的重要问题得到了快速发展，并已引起越来越多的学者关注。Li等[1]研究了基于位置感知的影响力最大化问题，通过用户影响力的上界选择种子节点并消除不重要的节点，减少了初始种子节点的选择范围。Kim等[2]基于 IC模型将独立影响路径作为影响评估单元，但是算法未考虑不同节点影响力的相关性。Zhao等[3]提出基于网络社区结构的节点影响力度量策略，但是算法未考虑节点度在信息传播中的重要性。Jung等[4]提出了基于 IC扩展模型的IRIE算法。……