基于3-layer中心度的社交网络影响力最大化算法.pdf

《基于3-layer中心度的社交网络影响力最大化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第1期计算机科学Vo1．41No．12014年1月ComputerScienceJan2014基于3-layer中心度的社交网络影响力最大化算法王俊余伟胡亚慧李石君(武汉大学计算机学院武汉430072)摘要社交网络影响最大化问题是指如何寻找网络中有限的初始节点，使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围，但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高；基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点，但计算复

2、杂度也过高。考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度，定义了3-layer局部中心度，以计算节点的潜在影响力值。基于线性阈值模型，启发选择一部分种子节点：每一次都选取潜在影响力最大的节点作为种子节点进行激活；运用贪心算法选取剩下的一部分种子节点：每一次都选取具有最大影响增量的节点作为种子节点进行激活。实验表明，该混合算法具有很好的激活范围以及非常低的时间复杂度。关键词社交网络，影响力最大化，启发式算法，3-layer局部中心度，贪心算法中图法分类号TP311．13文献标识码AH

3、euristicAlgorithmBasedon3-layerCentralityforInfluenceMaximizationinSocialNetworksWANGJunYUWeiHUYa-huiLIShun(Sehoo1ofComputer，WuhanUniversity，Wuhan430072，China)AbstractInfluentialmaximizationinasocialnetworkistheproblemoffindingthelimitedinitialnodeswhi

4、chcanmaxi—mizethespreadofinfluence．Somegreedyalgorithmscangetwidespreadofinfluence，buthavetoohighcosttobeap—pliedinlarge-scalesocialnetworks．TheheuristicmethodbasedondegreecentralityissimplebutoflowaccuracNHeu—risticalgorithmsbasedonglobalmetricssuchas

5、betweennesscentralityandclosenesscentralitycanbetteridentifythemostinfluentialnodes，butthecomputationalcomplexityofwhichismuchhightoo．Asatradeoffbetweenthelow-accu—ratedegreecentralityandothertime-consumingmeasures，wedefinedthe3-layerlocalcentralityfor

6、computingthepo—tentialinfluenceofnodes．Basedonlinearthresholdmodel，weselectedsomeseednodesthroughtheheuristicalgorithminwhichthenodewithmaximalpotentialinfluenceisselectedateachstep，andwechoseanotherseednodesbythegreedyalgorithminwhichthenodewiththelar

7、gestinfluenceincrementischosenateachtime．Theexperimentalresultsshowthatourhybridalgorithmhasgoodspreadofinfluenceandlowtimecomplexity．KeywordsSocialnetwork，Influencemaximization，Heuristicalgorithm，3-layerlocalcentrality，Greedyalgorithm对于谣言在社会中的扩散、计算机病毒

8、在计算机网络上1引言的蔓延、传染病在人群中的流行等不良传播，我们要找出其中一个人使用了一种新的产品后可能会告诉他的朋友们也影响力最大的传播种子，然后重点将这些传播种子去除或阻去使用这种产品，他的朋友们又把这种产品推荐给他们的朋隔，以扼制这些不良影响的快速传播势头。友，于是产生了级联推荐的效果，这就是“口碑效应”。商家近年来，由于大型社交网络如Facebook、人人网、微博等计划推出新产品时，就可以利用这种效应：商家可以先找到一的兴起，各种信息通过社交网络被广泛传播。如