基于有重叠社区划分的社会网络影响最大化方法研究

doi:10.11896/j.issn.1002-137X.2018.06.005

计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 32-35.doi: 10.11896/j.issn.1002-137X.2018.06.005

• 第十四届全国Web信息系统及其应用学术会议 • 上一篇下一篇

基于有重叠社区划分的社会网络影响最大化方法研究

胡庆成, 张勇, 邢春晓

清华大学计算机科学与技术系北京100084;
清华大学信息技术研究院北京100084

收稿日期:2017-03-11 出版日期:2018-06-15 发布日期:2018-07-24
作者简介:胡庆成(1977-),男,博士,主要研究方向为信息传播、大数据分析、复杂网络等,E-mail:huqingcheng@tsinghua.edu.cn(通信作者);张勇(1973-),男,博士,副教授,主要研究方向为大数据管理与分析、数据科学;邢春晓(1967-),男,教授,博士生导师,主要研究方向为大数据、知识工程和数据科学
基金资助:
本文受国家自然科学基金(91646202),教育部在线教育研究中心在线教育研究基金(2017YB142),千人计划、清华大学自主科研计划基金,863计划:心血管疾病大数据平台的构建和应用研究(SS2015AA020102)资助

K-clique Heuristic Algorithm for Influence Maximization in Social Network

HU Qing-cheng, ZHANG Yong, XING Chun-xiao

Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;
Research Institute of Information Technology,Tsinghua University,Beijing 100084,China

Received:2017-03-11 Online:2018-06-15 Published:2018-07-24

摘要/Abstract

摘要： 社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。

关键词: 社会网络, 社区划分, 贪心算法, 信息传播, 影响最大化

Abstract: Influence maximization is the problem of obtaining a set of nodes with specified size in social network to ma-ximize their aggregate influence under certain influence diffusion model,and it can yield significant benefit both in theory and real life.Influence maximization has been proved to be NP-hard by Kempe D et al.This paper proposed a new algorithm for influence maximization named K-clique Heuristic.The basic idea of the algorithm is that the nodes in social network spans multiple social circles.If these nodes are more widely spread in field and range,they have greater intersectionality and influence.The experimental results show that the proposed model is effective,and it may also shed light on the profound problem of influence maximization in social network.

Key words: Greedy algorithm, Influence maximization, Information diffusion, K-clique, Social network

中图分类号:

TP311

胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究[J]. 计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005

HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network[J]. Computer Science, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005

参考文献

[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.

相关文章 15

[1]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[2]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165
[3]	畅雅雯, 杨波, 高玥琳, 黄靖云. 基于SEIR的微信公众号信息传播建模与分析 Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR 计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169
[4]	左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法 Budget-aware Influence Maximization in Social Networks 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228
[5]	邵玉, 陈崚, 刘维. 独立级联模型下基于最大似然的负影响力源定位方法 Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model 计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190
[6]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[7]	桑春艳, 胥文, 贾朝龙, 文俊浩. 社交网络中基于注意力机制的网络舆情事件演化趋势预测 Prediction of Evolution Trend of Online Public Opinion Events Based on Attention Mechanism in Social Networks 计算机科学, 2021, 48(7): 118-123. https://doi.org/10.11896/jsjkx.200600155
[8]	杨旭华, 王晨. 基于网络嵌入与局部合力的复杂网络社区划分算法 Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force 计算机科学, 2021, 48(4): 229-236. https://doi.org/10.11896/jsjkx.200200102
[9]	袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法 Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game 计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079
[10]	杨卓璇, 马源培, 严冠. 基于耦合强度的多项式时间社团探测算法 Polynomial Time Community Detection Algorithm Based on Coupling Strength 计算机科学, 2020, 47(6A): 102-107. https://doi.org/10.11896/JsJkx.190900170
[11]	包峻波, 闫光辉, 李俊成. 结合非完全信息博弈的SIR传播模型 SIR Propagation Model Combing Incomplete Information Game 计算机科学, 2020, 47(6): 230-235. https://doi.org/10.11896/jsjkx.190400164
[12]	张新明, 李双倩, 刘艳, 毛文涛, 刘尚旺, 刘国奇. 信息共享模型和组外贪心策略的郊狼优化算法 Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection 计算机科学, 2020, 47(5): 217-224. https://doi.org/10.11896/jsjkx.190400039
[13]	富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法 Event Detection Method Based on Node Evolution Staged Optimization 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072
[14]	胡俊钦, 张佳俊, 黄引豪, 陈星, 林兵. 边缘环境下DNN应用的计算迁移调度技术 Computation Offloading Scheduling Technology for DNN Applications in Edge Environment 计算机科学, 2020, 47(10): 247-255. https://doi.org/10.11896/jsjkx.190900106
[15]	李卓, 徐哲, 陈昕, 李淑琴. 面向移动群智感知的位置相关在线多任务分配算法 Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing 计算机科学, 2019, 46(6): 102-106. https://doi.org/10.11896/j.issn.1002-137X.2019.06.014

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于有重叠社区划分的社会网络影响最大化方法研究

K-clique Heuristic Algorithm for Influence Maximization in Social Network

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0