计算机科学 ›› 2016, Vol. 43 ›› Issue (5): 47-50.doi: 10.11896/j.issn.1002-137X.2016.05.008
王学光
WANG Xue-guang
摘要： 社会网络关键节点发现问题有着许多重要的应用,如何找到网络中具有最大影响力的K个节点是一个NP问题。考虑到社会网络中普遍存在着社区结构,提出一种新的社会网络的关键节点发现算法,其在两个信息融合模型的基础上利用Owen值和Monte-Carlo方法得到每个节点的边际贡献,其中边际贡献最大的K个节点即为该问题的解。实验结果表明,该算法更适用于网络中存在社区结构的情形,在时间效率上相对于Greedy算法有几十倍的提高。
| [1] He Nan,Li De-yi,Gan Wen-yan,et al.Mining Vital Nodes in Complex Networks[J].Computer Science,2007,34(12):1-5(in Chinese)赫南,李德毅,淦文燕,等.复杂网络中重要性节点发掘综述[J].计算机科学,2007,34(12):1-5 [2] Domingos P,Richardson M.Mining the network value of cus-tomers[C]∥The 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD).San Francisco,CA,2001:57-66 [3] Domingos P,Richardson M.Mining knowledge-sharing sites for viral marketing[C]∥The 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD).Ed-monton,Canada,2002:61-70 [4] Kempe D,Kleinberg J M,Tardos .Maximizing the spread of influence through a social network[C]∥The 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD).Washington D C,2003:137-146 [5] Nemhauser G,Wolsey L,Fisher M.An analysis of the approximations for maximizing submodular set functions[J].Mathematical Programming,1978,14(1):265-294 [6] Even-Dar E,Shapira A.A note on maximizing the spread of influence in social networks[M]∥ Internet and Network Economics:Third International Workshop,WINE 2007,San Diego,CA,USA,Dec 12-14,2007.2007:281-286 [7] Lahiri M,Cebrian M.The genetic algorithm as a general diffusion model for social networks[C]∥The Twenty-Fourth AAAI Conference on Artificial Intelligence.Atlanta,Georgia,2010:494-499 [8] Goldenberg J,Libai B,Muller E.Talk of the network:A complex systems look at the underlying process of word-of-mouth[J].Marketing Letters,2001,12(3):211-223 [9] Granovetter M.Threshold models of collective behavior[J].American Journal of Sociology,1978,83(6):1420-1443 [10] Shapley L S.A value for n-person games[M]∥Kuhn H W,Tucker A W,eds.Contributions to the Theory of Games II.Princeton University Press,1953:307-317 [11] Owen G.Values of games with a priori unions[M]∥Henn R,Moeschlin O,eds.Mmathematical Economics and Game Theory:Essays in Honer of Oskar Morgenstern.Springer-Verlag,Berlin,1977:76-88 [12] Scott J.Social Network Analysis:A Handbook(2nd Ed)[M].Sage:London,2000 [13] Caulier J F.Network Games as TU Cooperative Games:TheCore,the Shapley Value and Simple Network Games.http://centres.fusl.ac.be/CEREC/document/seminars/caulier_cerec_feb2009.pdf [14] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms(2nd ed)[M].Cambridge,MA:MIT Press,2001 [15] Guimerà R,Amaral L A N.Functional cartography of complex metabolic networks[J].Nature,2005,433:895-900 [16] Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].P hysical Review E,2004,70(6):066111(6) [17] Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512 [18] Leskovec J,Kleinberg J,Faloutsos C.Graphs over time:Densification laws,shrinking diameters and possible explanations[C]∥The 11th ACM SIGKDD international conference on Knowledge discovery in data mining(KDD).Chicago,Illinois,USA,2005:177-187 [19] http://dblp.uni-trier.de [20] Viswanath B,Mislove A,Cha M,et al.On the evolution of user interaction in Facebook[C]∥The 2nd ACM SIGCOMM Workshop on Social Networks(WOSN).Barcelona,Spain,2009:37-42 [21] http://www-2.cs.cmu.edu/~enron [22] Mislove A,Marcon M,Gummadi K P,et al.Measurement andanalysis of online social networks[C]∥The 7th ACM SIGCOMM conference on Internet measurement conference(IMC).San Diego,California,USA,2007:29-42 [23] Chen Q,Chang H,Govindan R,et al.The origin of power laws in Internet topologies revisited[C]∥The 21st Annual Joint Conference of the IEEE Computer and Communications Societies.Los Alamitos,CA,USA,2002:608-617 [24] Watts D J,Strogatz S H.Collective dynamics of “small-world” networks[J].Nature,1998,393:440-442 |
| No related articles found! |
|
||
首页