新型影响力最大化算法.pdf

《新型影响力最大化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、libRoADcAsTINGANDTRANr's-~Mll惠QUZJ“～⋯⋯【本文献信息】宋伟，梁霖，李锋．新型影响力最大化算法[J]．电视技术，2014，38(15)新型影响力最大化算法宋伟，梁霖，李绎(1．南京邮电大学通信与信息工程学院，江苏南京210003；2．华为技术有限公司，北京100094)【摘要】如何从包含成千上万个节点的社会网络中选取初始节点集来传播信息，使最后接受者的数量达到最大化，已成为社会网络领域研究的热点。在此背景下，提出了一种新的初始节点选择算法——基于社区的影响力最大化算法，该算法在综合考虑传播效果及时间

2、复杂度的基础上，将初始节点的选择过程划分为网络划分、启发、贪心三个阶段。并通过实验证明，与已有算法相比，该算法最终的传播效果更为理想，且时间复杂度较低。【关键词】社会网络；信息传播；信息接受最大化；节点选择【中图分类号】TN919．8【文献标志码】ANewMaximizationAlgorithmBasedonCommunitySONGWei，LIANGLin，LIFeng~(J．CollegeofTeleconmmnications＆InformationEngineering，NanjingUniversityofPostsan

3、dTelecommunications，Nanjing210003，China；2．HuaweiTechnologiesCo．，Ltd．，Belting100094，China)【Al~traet】Howtochooseinitialnodesfromsocialnetworkwhichconsistsofthousandsofnodestospreadinformation，inordertomaximizetheaccept—anceofinformation，hascurrentlybecomeahottopic．Basedo

4、nthis，anewalgorithmtochoseinitialnodes，whichcalledanewmaximizationalgorithmbasedoncommunity，isproposed．Consideringdifusionefectsandtimecomplexity，theprocessofselectinginitialnodesaredividedintothreestageswhichcallednetworkdivision，inspirationandgreedy．Simulationresults

5、showthattheproposedalgorithmissuperiorthanmanyotheralgorithmsintermsoffinaldifusionefectsandtimecomplexity．【Keywords】socialnetwork；informationdissemination；MAI；nodeselection近几年，随着互联网技术的进步，各种大型复杂社交个社团的朋友发出的邀请，影响力不如不同社团的朋友，网络不断出现。如何从复杂网络中选取初始节点集来传同一社团中度大的朋友影响力更大。播信息，使得信息

6、接受最大化已成为社会网络领域研究的在此背景下，本文基于线性阈值模型(LT)提出了新热点。且在疾病传播、产品推广、社会稳定、舆情扩散和故的初始节点选择算法一基于社区的影响力最大化算障控制等方面都有着十分重要的应用。法，利用LT模型的影响力累积特性，以扩大最终的影响针对影响力最大化问题，很多研究者针对某一具体范围为目的，兼顾时间复杂度来研究社会网络中的影响力最大化问题。的网络结构提出了不同的算法，如贪心算法、Maxdegree算法等。目前，大部分研究认为，具有越多链接的节点影响1相关工作力越大⋯，位于网络越核心位置的节点，在传播过程中所

7、1．1贪心算法起的作用越大。Kempe和Kleinberg等人曾在2003年提出使用贪心对此，文献[3]提出了不同的看法并通过调查分析指算法来求解影响力最大化问题，以下简称KK算法。KK出对于单个传播源而言，度最大的节点并不一定是最具影算法的基本思想是：设最初的初始节点集合S=(2j，将k响力的节点，通过K—shel1分解得到的K—shell值最大个初始节点的选择过程分为k步，每一步都选择当前网络的节点才是最有影响力的节点。而对于多个传播源网络，中边际影响值最大的节点加入集合．s，以得到局部最优度大的节点往往比K—shell值大的节

8、点具有更好的传播解，直到IsI=k，即为最有影响力的初始节点集合Js。效果。因为K—shell值大的节点往往都聚集在网络核心该算法虽然能保证至少得到最优解的63％_6J，但是由于部位，传播过程中存在交叉感染现象，出现较大允余。每一步初