计算机科学

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

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

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

胡庆成, 张勇, 邢春晓   

  1. 清华大学计算机科学与技术系 北京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   

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

PDF (PC)

476

摘要： 社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,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: Social network, Influence maximization, Information diffusion, Greedy algorithm, K-clique

中图分类号: 

  • TP311
[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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 编辑部. 新网站开通，欢迎大家订阅！[J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[7] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[8] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[9] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[10] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发