基于Owen值算法的社会网络关键节点问题研究
|
摘要
社会网络关键节点发现问题有着许多重要的应用,如何找到网络中具有最大影响力的K个节点是一个NP问题。考虑到社会网络中普遍存在着社区结构,提出一种新的社会网络的关键节点发现算法,其在两个信息融合模型的基础上利用Owen值和Monte-Carlo方法得到每个节点的边际贡献,其中边际贡献最大的K个节点即为该问题的解。实验结果表明,该算法更适用于网络中存在社区结构的情形,在时间效率上相对于Greedy算法有几十倍的提高。
Discovering critical nodes in social networks has many important applications and how to find out Kcritical 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 models 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 Knodes 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.
Discovering critical nodes in social networks has many important applications and how to find out Kcritical 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 models 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 Knodes 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.
引文
[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 customers[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).Edmonton,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:The Core,the Shapley Value and Simple Network Games[OL].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].Physical 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 and analysis 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
[2]Domingos P,Richardson M.Mining the network value of customers[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).Edmonton,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:The Core,the Shapley Value and Simple Network Games[OL].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].Physical 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 and analysis 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