基于拓扑势的影响力最大化算法  

Influence maximization algorithm based on topology potential

作　　者：王秀芳 牛炜南 孙承爱 仇丽青 WANG Xiu-fang;NIU Wei-nan;SUN Cheng-ai;QIU Li-qing(College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao 266510,China)

机构地区：[1]山东科技大学计算机科学与工程学院,山东青岛266510

出　　处：《计算机工程与设计》2020年第3期735-741,共7页Computer Engineering and Design

基　　金：国家自然科学基金青年基金项目(622814971)。

摘　　要：针对影响力最大化问题中贪心算法时间效率低的局限性,提出基于拓扑势的影响力最大化算法。基于拓扑势理论,确定节点是“山峰”“山谷”和“斜坡”节点;启发式地选取加权度最大的k个“山峰”和“山谷”节点构成候选种子集;采用CELF(cost-effective forward)算法确定最优种子集,提高影响范围。实验结果表明,基于拓扑势的算法在Amazon数据集上比贪心算法的运行时间快了98%,在时间复杂度方面比其它传统算法更具优势。To deal with the low efficiency of greedy algorithm,an algorithm for influence maximization based on topology potential was proposed.The topological potential theory was utilized to ensure the peak,valley and slope nodes.Top k weighted degree nodes were selected as candidate seed set by combining peak and valley nodes.The CELF(cost-effective forward)algorithm was conducted to ensure the optimal seed set,which improved both efficiency and accuracy.The experimental results show that this algorithm on Amazon dataset runs 98%faster than greedy algorithm,which performs better than other traditional algorithms in efficiency.

关 键 词：社交网络 影响力最大化 拓扑势 CELF算法 加权度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]