胡庆成,张勇,邢春晓.基于有重叠社区划分的社会网络影响最大化方法研究[J].计算机科学,2018,45(6):32-35
基于有重叠社区划分的社会网络影响最大化方法研究
K-clique Heuristic Algorithm for Influence Maximization in Social Network
投稿时间:2017-03-11  修订日期:2017-06-02
DOI:10.11896/j.issn.1002-137X.2018.06.005
中文关键词:  社会网络,影响最大化,信息传播,贪心算法,社区划分
英文关键词:Social network,Influence maximization,Information diffusion,Greedy algorithm,K-clique
基金项目:本文受国家自然科学基金(91646202),教育部在线教育研究中心在线教育研究基金(2017YB142),千人计划、清华大学自主科研计划基金,863计划:心血管疾病大数据平台的构建和应用研究(SS2015AA020102)资助
作者单位E-mail
胡庆成 清华大学计算机科学与技术系 北京100084 清华大学信息技术研究院 北京100084 huqingcheng@tsinghua.edu.cn 
张勇 清华大学计算机科学与技术系 北京100084 清华大学信息技术研究院 北京100084  
邢春晓 清华大学计算机科学与技术系 北京100084 清华大学信息技术研究院 北京100084  
摘要点击次数: 181
全文下载次数: 144
中文摘要:
      社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。
英文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器