基于启发式和贪心策略的社交网络影响最大化算法  

Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks

作　　者：曹玖新[1,2] 闵绘宇[1,2] 徐顺[1,2] 刘波[1,2] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]东南大学软件学院,苏州215123

出　　处：《东南大学学报（自然科学版）》2016年第5期950-956,共7页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(61272531;61472081);江苏省科技厅产学研前瞻性联合研究资助项目(SBY2014020139)

摘　　要：为解决传统影响力最大化算法在影响范围和运行时间上存在的不平衡问题,提出了一种综合启发式和贪心算法的社交网络影响力最大化算法(MHG).该算法综合考虑了贪心算法和启发式算法的优势,将种子节点的选择分为2个阶段,即通过启发式算法选出候选种子节点集和使用贪心算法从候选种子节点集中筛选出种子节点集合.结果表明,与现有的启发式算法相比,MHG算法在影响范围上具有显著优势,且接近贪心算法,但其运行时间明显少于贪心算法,因而在效果和时间2个方面取得了较好的平衡.在真实数据集及不同传播模型下,MHG算法均表现出稳定的影响范围,体现了该算法在大规模社会网络处理中的可扩展性.To solve the imbalance problem between the influence scope and the running time of the classic influence maximization algorithms,a mixed heuristic and greedy strategies based algorithm（ MHG algorithm） for influence maximization in social networks is proposed. The algorithm considers the advantages on the greedy and heuristic strategies,and the selection of seed nodes is divided into two steps. First,the candidate node set is selected by the heuristic algorithm,and then the final seed node set is deduced from this set by the greedy algorithm. The results showthat the MHG algorithm is superior in influence scope compared with current heuristic algorithms. It exhibits the approximate effect of the greedy algorithm,but the running time is obviously lower. Therefore,the MHG algorithm achieves a good balance between the influence scope and the running time. Moreover,the MHG algorithm presents a stable influence scope when running on real data sets and different dissemination models,showing its scalability in large scale social networks.

关 键 词：社交网络 影响最大化 贪心算法 启发式算法 传播模型 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]