[1]曹玖新,闵绘宇,徐顺,等.基于启发式和贪心策略的社交网络影响最大化算法[J].东南大学学报(自然科学版),2016,46(5):950-956.[doi:10.3969/j.issn.1001-0505.2016.05.009]
 Cao Jiuxin,Min Huiyu,Xu Shun,et al.Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks[J].Journal of Southeast University (Natural Science Edition),2016,46(5):950-956.[doi:10.3969/j.issn.1001-0505.2016.05.009]
点击复制

基于启发式和贪心策略的社交网络影响最大化算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
46
期数:
2016年第5期
页码:
950-956
栏目:
计算机科学与工程
出版日期:
2016-09-20

文章信息/Info

Title:
Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks
作者:
曹玖新闵绘宇徐顺刘波
东南大学计算机科学与工程学院, 南京211189; 东南大学软件学院, 苏州215123
Author(s):
Cao Jiuxin Min Huiyu Xu Shun Liu Bo
School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
College of Software Engineering, Southeast University, Suzhou 215123, China
关键词:
社交网络 影响最大化 贪心算法 启发式算法 传播模型
Keywords:
social networks influence maximization greedy algorithm heuristic algorithm dissemination model
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2016.05.009
摘要:
为解决传统影响力最大化算法在影响范围和运行时间上存在的不平衡问题,提出了一种综合启发式和贪心算法的社交网络影响力最大化算法(MHG).该算法综合考虑了贪心算法和启发式算法的优势,将种子节点的选择分为2个阶段,即通过启发式算法选出候选种子节点集和使用贪心算法从候选种子节点集中筛选出种子节点集合.结果表明,与现有的启发式算法相比,MHG算法在影响范围上具有显著优势,且接近贪心算法,但其运行时间明显少于贪心算法,因而在效果和时间2个方面取得了较好的平衡.在真实数据集及不同传播模型下,MHG算法均表现出稳定的影响范围,体现了该算法在大规模社会网络处理中的可扩展性.
Abstract:
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 show that 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.

参考文献/References:

[1] Domingos P, Richardson M. Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. San Francisco, CA, USA, 2001:57-66. DOI:10.1145/502512.502525.
[2] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada, 2002:61-70. DOI:10.1145/775047.775057.
[3] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2003:137-146. DOI:10.1145/956750.956769.
[4] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, CA, USA, 2007: 420-429. DOI:10.1145/1281192.1281239.
[5] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 199-208. DOI:10.1145/1557019.1557047.
[6] Goyal A, Lu W, Lakshmanan L V S. CELF++: optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International Conference Companion on World Wide Web. Hyderabad, India, 2011: 47-48.
[7] Wasserman S, Faust K. Social network analysis[J]. Encyclopedia of Social Network Analysis & Mining, 2011, 22(S1):109-127.
[8] Brin S, Page L. Reprint of: The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks, 2012, 56(18):3825-3833. DOI:10.1016/j.comnet.2012.10.007.
[9] Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2010:1029-1038. DOI:10.1145/1835804.1835934.
[10] Jung K, Heo W, Chen W. IRIE: Scalable and robust influence maximization in social networks[C]//IEEE 12th International Conference on Data Mining(ICDM). Brussels, Belgium, 2011:918-923. DOI:10.1109/icdm.2012.79.
[11] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893. DOI:10.1038/nphys1746.
[12] 曹玖新, 董丹, 徐顺, 等. 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015, 38(2):238-248. DOI:10.3724/SP.J.1016.2015.00238.
  Cao Jiuxin, Dong Dan, Xu Shun, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2):238-248. DOI:10.3724/SP.J.1016.2015.00238.(in Chinese)
[13] Cao T, Wu X, Wang S, et al. OASNET: An optimal allocation approach to influence maximization in modular social networks[C]//Proceedings of the 2010 ACM Symposium on Applied Computing(SAC). Sierre, Switzerland, 2010:1088-1094.
[14] Kleinberg J. The small-world phenomenon: An algorithm perspective[C]//Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. Portland, OR, USA, 2000:163-170. DOI:10.1145/335305.335325.
[15] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth[J]. Knowledge and Information Systems, 2013, 42(1):181-213. DOI:10.1007/s10115-013-0693-z.

相似文献/References:

[1]刘锡文,蒋俊杰.社交网络中基于用户投票的推荐机制[J].东南大学学报(自然科学版),2013,43(2):301.[doi:10.3969/j.issn.1001-0505.2013.02.014]
 Liu Xiwen,Jiang Junjie.Recommendation mechanism based on user voting in the social network[J].Journal of Southeast University (Natural Science Edition),2013,43(5):301.[doi:10.3969/j.issn.1001-0505.2013.02.014]
[2]张琳,张进.基于PPIN的社交网络推荐系统[J].东南大学学报(自然科学版),2017,47(3):478.[doi:10.3969/j.issn.1001-0505.2017.03.011]
 Zhang Lin,Zhang Jin.Social network recommendation system based on PPIN[J].Journal of Southeast University (Natural Science Edition),2017,47(5):478.[doi:10.3969/j.issn.1001-0505.2017.03.011]

备注/Memo

备注/Memo:
收稿日期: 2016-03-17.
作者简介: 曹玖新(1967—),男,博士,教授,博士生导师,jx.cao@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(61272531, 61472081)、江苏省科技厅产学研前瞻性联合研究资助项目(SBY2014020139).
引用本文: 曹玖新,闵绘宇,徐顺,等.基于启发式和贪心策略的社交网络影响最大化算法[J].东南大学学报(自然科学版),2016,46(5):950-956. DOI:10.3969/j.issn.1001-0505.2016.05.009.
更新日期/Last Update: 2016-09-20