| 摘要: |
| 首先研究了目前影响力最大化问题的解决方案，并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现，弱连接可以有效地打通社交网络中不同社团之间的信息壁垒，使得信息在不同社区间流通.利用弱连接的这一作用，同时基于贪心思想，提出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算法. |
| 关键词: 社交网络 弱连接 影响力最大化 节点影响力 关系强度 |
| DOI： |
| 分类号: |
| 基金项目:国家杰出青年科学基金（61225012)；国家自然科学基金（61070162，71071028，70931001)；高等学校博士学科点专项科研基金（20120042130003，20100042110025，20110042110024)；中央高校基本科研业务费专项资金（N110204003，N120104001) |
|
| Influence Maximization Algorithm Based on the Weak Tie in Social Network |
|
YI Xiu-Shuang, HU Jin-Lin, WANG Xing-Wei
|
|
School of Information Science and Engineering, Northeast University, Shenyang 110819, China
|
| Abstract: |
| This thesis introduced the solution of influence maximization and analyzed the advantages and disadvantages of those solutions. After studying the weak tie in social network, it is found that weak ties can effectively break the information barriers between different societies in social network and make information circulate in different societies. Making use of the weak tie's advantages, this thesis proposes a new solution, the BWTG algorithm, based on the greedy thought to resolve influence maximization problem. According to different solution spaces, the BWTG algorithm is divided into two different types:BCWTG and BNCWTG algorithm. There are two traditional evaluation indexes of influence maximization problem, namely, time complexity and the final activated nodes number. But considering the practical situation, a new evaluation index named ANNI is proposed to measure the ratio of profit and pay. Besides, in order to verify the performance of the proposed algorithm, different scales and types of data are used to carry out the experiment. The time complexity, the final activated nodes number and ANNI are compared with the classical Greedy algorithm. The experimental result finds that BCWTG and BNCWTG algorithm have lower time complexity and higher ANNI, but lower final activated nodes number than Greedy algorithm. But under some certain conditions, BCWTG and BNCWTG can be almost equal to Greedy in activated nodes number. |
| Key words: social network weak ties influence spread maximization node influence tie strength |
