资源描述：
《一种新的复杂网络影响力最大化发现方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一种新的复杂网络影响力最大化发现方法胡庆成张勇许信辉邢春晓陈池陈信欢AnewapproachforinfluencemaximizationincomplexnetworksHuQing-ChengZhangYongXuXin-HuiXingChun-XiaoChenChiChenXin-Hua引用信息Citation:ActaPhysicaSinica,64,190101(2015)DOI:10.7498/aps.64.190101在线阅读Viewonline:http://dx.doi.org/10.7498/aps.64.1
2、90101当期内容Viewtableofcontents:http://wulixb.iphy.ac.cn/CN/Y2015/V64/I19您可能感兴趣的其他文章Articlesyoumaybeinterestedin利用邻域“结构洞”寻找社会网络中最具影响力节点Leveragingneighborhood“structuralholes”toidentifyingkeyspreadersinsocialnetworks物理学报.2015,64(2):020101http://dx.doi.org/10.7498/aps.64.0
3、20101随机系统的概率密度函数形状调节Theshaperegulationofprobabilitydensityfunctionforstochasticsystems物理学报.2014,63(24):240508http://dx.doi.org/10.7498/aps.63.240508一种基于最大流的网络结构熵Anewnetworkstructureentropybasedonmaximumflow物理学报.2014,63(6):060504http://dx.doi.org/10.7498/aps.63.060504非
4、高斯噪声驱动下一维双稳系统的逻辑操作Thereliabilityoflogicaloperationinaone-dimensionalbistablesysteminducedbynon-Gaussiannoise物理学报.2013,62(19):190510http://dx.doi.org/10.7498/aps.62.190510一种新的网络传播中最有影响力的节点发现方法Anewapproachtoidentifyinfluentialspreadersincomplexnetworks物理学报.2013,62(14):1
5、40101http://dx.doi.org/10.7498/aps.62.140101物理学报ActaPhys.Sin.Vol.64,No.19(2015)190101一种新的复杂网络影响力最大化发现方法胡庆成y张勇许信辉邢春晓陈池陈信欢(清华大学计算机科学与技术系,信息技术研究院,清华信息科学与技术国家实验室,北京100084)(2014年12月8日收到;2015年6月10日收到修改稿)复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一,其研究在理论和现实应用中都有重大的意义.在给定s值的前提下,如何寻找发现s个最
6、大影响范围的节点集,这是个组合优化问题,Kempe等已经证明该问题是NP-hard问题.目前已有的随机算法时间复杂度低,但是结果最差;其他贪心算法时间复杂度很高,不能适用于大型社会网络中,并且这些典型贪心算法必须以了解网络的全局信息为前提,而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的.我们提出了一种新的影响力最大化算法模型RMDN,及改进的模型算法RMDN++,模型只需要知道随机选择的节点以及其邻居节点信息,从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题,算法的时间复杂度仅为O(slog(n)
7、);然后,我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示,RMDN,RMDN++算法有着和现有典型算法相近的影响力传播效果,且有时还略优,同时在运行时间上则有显著的提高;我们从理论上推导证明了方法的可行性.本文所提出的模型算法适用性更广,可操作性更强,为这项具有挑战性研究提供了新的思路和方法.关键词:复杂网络,影响力最大化,信息传播,贪心算法PACS:01.75.+m,05.90.+m,89.75.–k,89.70.HjDOI:10.7498/aps.64.190101模式和影响力传播方式,既能从社会学角度加深
8、理1引言解人们的社会行为,同时也能促进政治、经济和文化活动等领域的交流与传播,其在理论和现实应用影响力分析是复杂网络的重要研究内容,现中都有重大的意义.例如有效的控制疾病传播、流实世界中的诸多系统都以复杂网络(ComplexNet-言散布、计算机病
