Computer Science ›› 2013, Vol. 40 ›› Issue (4): 155-159.

Previous Articles     Next Articles

Discovering Critical Nodes in Social Networks Based on Cooperative Games

WANG Xue-guang   

  • Online:2018-11-16 Published:2018-11-16

Abstract: Discovering critical nodes in social networks has many important applications and more and more institutions and scholars have been attended.For finding out the top K critical nodes in social networks,this paper presented a method based on cooperative games to obtain each node’s marginal contribution by using Owen value and considering the widespread community structure in social networks.And then we can get the solution of the critical nodes problem.The feasibility and effectiveness of our method were verified on two synthetic datasets and four real datasets.

Key words: Social networks,Critical node problem,Cooperative games,Owen values

[1] 赫南,等.复杂网络中重要性节点发掘综述[J].计算机科学,2007,34(12):1-5
[2] 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,DC,2003:137-146
[3] Even-Dar E,Shapira A.A note on maximizing the spread of influence in social networks[C]∥WINE 2007,LNCS 4858.2007:281-286
[4] 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
[5] 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
[6] Granovetter M.Threshold models of collective behavior[J].American Journal of Sociology,1978,83(6):1420-1443
[7] Nemhauser G,Wolsey L,Fisher M.An analysis of the approximations for maximizing submodular set functions[J].Mathematical Programming,1978,14(1):265-294
[8] Costa L F,Rodrigues F A,Travieso G,et al.Characterization of complex networks-A survey of measurements[J].Advances in Physics,2007,56(1):167-242
[9] Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks and ISDN Systems,1998,30(1-7):107-117
[10] Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632
[11] White S,Smyth P.Algorithms for estimating relative importance in networks[C]∥The ninth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD).Washing-ton,DC,2003:266-275
[12] Shetty J,Adibi J.Discovering Important Nodes through Graph Entropy The Case of Enron Email Database[C]∥The 3rd international workshop on Link discovery.Chicago,Illinois,2005:74-81
[13] Li Y M,Lai C Y,Chen C W.Identifying Bloggers with Marketing Influence in the Blogosphere[C]∥The 11th International Conference on Electronic Commerce (ICEC).Taipei,Taiwan,2009:335-340
[14] Li Y M,Lai C Y,Lin C H.Discovering Influential Nodes for Viral Marketing[C]∥The 42nd Hawaii International Conference on System Sciences (HICSS).Waikoloa,2009:1-10
[15] Lappas T,Terzi E,Gunopulos D,et al.Finding Effectors in Social Networks[C]∥The 16th ACM SIGKDD conference on Knowledge discovery and data mining (KDD).Washington,DC,2010:1059-1068
[16] Java A,Kolari P,Finin T,et al.Modeling the spread of influence on the blogosphere[C]∥The 15th International World Wide Web Conference.Edinburgh,UK,2006
[17] Hussain D M A.Terrorist Networks Analysis through Argument Driven Hypotheses Model[C]∥The Second International Conference on Availability,Reliability and Security.Vienna,Austria,2007:480-492
[18] Zhai Z,Xu H,Jia P.Identifying Opinion Leaders in BBS[C]∥The IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology.Sydney,Australia,2008:398-401
[19] Kargar M,An A.Discovering top-k teams of experts with without a leader in social networks[C]∥The 20th ACM International Conference on Information and Knowledge Management (CIKM).Glasgow,Scotland,UK,2011:895-994
[20] Zhang Y,Zhou J,Cheng J.Preference-based Top-K Influential Nodes Mining in Social Networks[C]∥The IEEE 10th International Conference on Trust,Security and Privacy in Computing and Communications.Changsha,China,2011:1512-1518
[21] 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
[22] 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
[23] Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C]∥The 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD).San Jose,California,2007:420-429
[24] Chen W,Wang Y,Yang S.Efficient influence maximization in social networks[C]∥The 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD).Paris,France,2009:199-207
[25] Chen W,Wang C,Wang Y.Scalable influence maximization for prevalent viral marketing in large scale social networks[C]∥The 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD).Washington,DC,2010:1029-1038
[26] Chen W,Yuan Y,Zhang L.Scalable influence maximization in social networks under the linear threshold model[C]∥The 2010IEEE International Conference on Data Mining (ICDM).Sydney,Australia,2010:88-97
[27] Chen W,Collins A,Cummings R,et al.Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate[C]∥2011SIAM International Conference on Data Mining.Mesa,Arizona,USA,2011
[28] 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
[29] Owen G.Values of games with a priori unions[M]∥Henn R,Moeschlin O,eds.Essays in mathematical economics and game theory.Springer-Verlag,Berlin,1977:76-88
[30] Scott J.Social Network Analysis(2nd ed)[M].A Handbook,Sage,London,2000
[31] Caulier J-F.Network Games as TU Cooperative Games[M].The Core,the Shapley Value and Simple Network Games,2009
[32] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms(2nd ed)[M].Cambridge,MA:MIT Press,2001
[33] Guimerà R,Amaral L A N.Functional cartography of complex metabolic networks[J].Nature,2005,433:895-900
[34] Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111(6)
[35] Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512
[36] 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
[37] http://dblp.uni-trier.de/
[38] 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
[39] http://www-2.cs.cmu.edu/~enron/
[40] Mislove A,Marcon M,Gummadi K P,et al.Measurement and analysis of online social networks[C]∥The 7th ACM SIGCOMM conference on Internet measurement conference (IMC).San Diego,California,USA,2007:29-42

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!