Computer Science ›› 2016, Vol. 43 ›› Issue (5): 47-50.doi: 10.11896/j.issn.1002-137X.2016.05.008

Previous Articles     Next Articles

Research on Critical Nodes in Social Networks Based on Owen Values

WANG Xue-guang   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Discovering critical nodes in social networks has many important applications and how to find out K critical nodes with the most influence in a social network is a NP problem.Considering the widespread community structure in social networks,this paper presented an algorithm of discovering critical nodes based on two information diffusion mo-dels and obtained each node’s marginal contribution by using Owen value and Monte-Carlo method.And the solution of the critical nodes problem is the K nodes with the highest marginal contributions.The results show that the algorithm is more suitable for the networks with community structure and the time efficiency of the algorithm is dozens of times than the Greedy algorithm.

Key words: Community structure,Critical node problem,Owen values,Influence maximization

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!