计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 32-35.doi: 10.11896/j.issn.1002-137X.2018.06.005
• 第十四届全国Web信息系统及其应用学术会议 • 上一篇 下一篇
胡庆成, 张勇, 邢春晓
HU Qing-cheng, ZHANG Yong, XING Chun-xiao
摘要: 社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。
中图分类号:
[1]REN X L,LV L Y.Review of ranking nodes in complex networks[J].Chinese Science Bulletin,2014,59(13),1175-1197.(in Chinese) 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,59(13):1175-1197. [2]LIU J G,REN Z M,GUO Q,et al.Node importance ranking of complex network[J].Chinese Journal of Physics,2013,62(17):178901.(in Chinese) 刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J].物理学报,2013,62(17):178901. [3]DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2001:57-66. [4]RICHARDSON M,DOMINGOS P.Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2002:61-70. [5]KEMPE D,KLEINBERG J,TARDOS E.Maximizing thespread of influence through as ocial network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137-146. [6]CHEN W,WANG Y,YANG S.E cient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2009:199-208. [7]KIMURA M,SAITO K.Tractable models for information diffusion in social networks[M]//Knowledge Discovery in Databases(PKDD 2006).Springer,2006:259-271. [8]CHEN W,YUAN Y,ZHANG L.Scalable influence maximization in social networks under the linear threshold model[C]//2010 IEEE 10th International Conference on Data Mining (ICDM).IEEE,2010:88-97. [9]WANG Y,CONG G,SONG G,et al.Community-based greedy algorithm for mining top-k influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining.ACM,2010:1039-1048. [10]GALSTYAN A,MUSOYAN V,COHEN P.Maximizing influence propagation in networks with community structure[J].Physical Review E,2009,79(5):056102. [11]LI D,XU Z M,CHAKRABORTY N,et al.Polarity related influence maximization in signed social networks[J].PloS one,2014,9(7):e102199. [12]HU Q,ZHANG Y,XU X,et al.RMDN:New Approach to Maximize Influence Spread[C]//2015 IEEE 39th Annual Computer Software and Applications Conference.IEEE,2015:702-711. [13]MARSDEN P V.Egocentric and sociocentric measures of network centrality[J].Social Networks,2002,24(4):407-422. [14]WALKER G,KOGUT B,SHAN W.Social capital,structural holes and the formation of an industry network[J].Organization Science,1997,8(2):109-125. [15]AHUJA G.Collaboration networks,structural holes,and innovation:A longitudinal study[J].Administrative Science Quarterly,2000,45(3):425-455. [16]BURT R S.Structural holes:The social structure of competition[M].Cambridge:Harvard University Press,2009. [17]PALLA G,DERE'NYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818. [18]XIE N.Social network analysis of blogs[D].United Kingdom: University of Bristol,2006. [19]BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4):175-308. |
[1] | 桑春艳, 胥文, 贾朝龙, 文俊浩. 社交网络中基于注意力机制的网络舆情事件演化趋势预测[J]. 计算机科学, 2021, 48(7): 118-123. |
[2] | 杨旭华, 王晨. 基于网络嵌入与局部合力的复杂网络社区划分算法[J]. 计算机科学, 2021, 48(4): 229-236. |
[3] | 袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法[J]. 计算机科学, 2021, 48(3): 313-319. |
[4] | 杨卓璇, 马源培, 严冠. 基于耦合强度的多项式时间社团探测算法[J]. 计算机科学, 2020, 47(6A): 102-107. |
[5] | 包峻波, 闫光辉, 李俊成. 结合非完全信息博弈的SIR传播模型[J]. 计算机科学, 2020, 47(6): 230-235. |
[6] | 富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法[J]. 计算机科学, 2020, 47(5): 96-102. |
[7] | 张新明, 李双倩, 刘艳, 毛文涛, 刘尚旺, 刘国奇. 信息共享模型和组外贪心策略的郊狼优化算法[J]. 计算机科学, 2020, 47(5): 217-224. |
[8] | 胡俊钦, 张佳俊, 黄引豪, 陈星, 林兵. 边缘环境下DNN应用的计算迁移调度技术[J]. 计算机科学, 2020, 47(10): 247-255. |
[9] | 李卓, 徐哲, 陈昕, 李淑琴. 面向移动群智感知的位置相关在线多任务分配算法[J]. 计算机科学, 2019, 46(6): 102-106. |
[10] | 韩忠明, 郑晨烨, 段大高, 董健. 基于多信息融合表示学习的关联用户挖掘算法[J]. 计算机科学, 2019, 46(4): 77-82. |
[11] | 张晓琴, 安晓丹, 曹付元. 基于谱聚类的二分网络社区发现算法[J]. 计算机科学, 2019, 46(4): 216-221. |
[12] | 徐方, 邓敏, 熊曾刚, 叶从欢, 徐宁. 移动社会网络中基于多维上下文匹配的数据转发算法[J]. 计算机科学, 2019, 46(2): 81-87. |
[13] | 金婷, 谭文安, 孙勇, 赵尧. 模糊多目标进化的社会团队形成方法[J]. 计算机科学, 2019, 46(2): 315-320. |
[14] | 宾晟, 孙更新. 基于多关系社交网络的协同过滤推荐算法[J]. 计算机科学, 2019, 46(12): 56-62. |
[15] | 陈晋音,胡可科,李玉玮. 基于MB-RRT*的无人机多点航迹规划算法研究[J]. 计算机科学, 2018, 45(6A): 85-90. |
|