基于社交网络弱连接属性的影响力最大化算法

来源：软件学报杂志2016年第S2期北京时间：

作者：易秀双,胡金林,王兴伟

单位：易秀双，东北大学 信息科学与工程学院, 辽宁 沈阳 11081911,胡金林，东北大学 信息科学与工程学院, 辽宁 沈阳 11081902,王兴伟，东北大学 信息科学与工程学院, 辽宁 沈阳 11081903

摘要：首先研究了目前影响力最大化问题的解决方案，并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现，弱连接可以有效地打通社交网络中不同社团之间的信息壁垒，使得信息在不同社区间流通.利用弱连接的这一作用，同时基于贪心思想，提出BWTG（base-on weak tie greedy)算法来解决影响力最大化问题，并根据解空间的不同，把BWTG算法分为BCWTG（base-on complete weak tie greedy)和BNCWTG（base-on not complete weak tie greedy)两种算法.影响力最大化问题的传统评价指标有两种：时间复杂度和最终激活节点数，但考虑到实际情况，定义了ANNI（actived nodes/node influence)这一新的评价指标，用于衡量回报与付出之比.为了验证BCWTG和BNCWTG算法的性能，在不同类型、不同规模的真实数据集中对算法进行实验验证，在时间复杂度、最终激活节点数和ANNI这3个方面与经典的Greedy算法进行对比，实验结果表明，BCWTG算法和BNCWTG算法在运算时间和ANNI方面有所提高，最终激活节点数方面却弱于Greedy算法，但当满足一定条件时，BCWTG和BNCWTG算法在最终激活节点数方面也能接近Greedy算法.

关键词：社交网络;弱连接;影响力最大化;节点影响力;关系强度

基金资助：国家杰出青年科学基金（61225012)；国家自然科学基金（61070162，71071028，70931001)；高等学校博士学科点专项科研基金（20120042130003，20100042110025，20110042110024)；中央高校基本科研业务费专项资金（N110204003，N120104001)