Social Network Evolution Analysis Based on Graph Entropy
GUO Rui1,2, ZHONG Ning1,2, LI Wen-Bin3
1.International WIC Institute, Beijing University of Technology, Beijing 100022 2.Department of Biological Information, Maebashi Institute of Technology, Maebashi-City, Japan 371-0816 3.School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031
Abstract The order of networks in evolution is described by graph entropy. And the different evolution tendencies of connectivity entropy and centrality entropy are discussed. The different evolution tendencies reflect one characteristics of social networks inconsistency of multiscale. Then, the important nodes in networks are detected by entropy participation ratio. Finally, the reason of the distinct tendencies of global property and local property is shown in theory.
[1] Watts D J, Strogatz S H. Collective Dynamics of Small-World Networks. Nature, 1998, 393: 440-442 [2] Barabasi A L, Albert R. Emergence of Scaling in Random Networks. Science, 1999, 286(5439): 509-512 [3] Guimera R, Danon L, Dl'az-Guilera A, et al. Self-Similar Community Structure in a Network of Human Interactions [EB/OL]. [2003-04-30]. http://amaral.northwestern.edu/Publications/Papers/roger pro3a.pdf [4] Newman M E J, Forrest S, Balthrop J. Email Networks and the Spread of Computer Viruses [EB/OL]. [2002-09-10]. http://www.cs.unm.edu/~immsec/publications/Email%20Networks%20and%20the%20Spread%20of%20Computer%20Viruses.pdf [5] Boykin P O, Roychowdhury V P. Personal Email Networks: An Effective. IEEE Computer, 2002, 38(4): 61-68 [6] Ebel H, Mielsch L I, Borbholdt S. Scale-Free Topology of Email Networks [EB/OL]. [2002-09-30]. http://www.itp.uni-bremen.de/complex/preo35/03.pdf [7] Nieminen U J. On the Centrality in a Directed Graph. Social Science Research, 1973, 2: 371-378 [8] Freeman L C. Centrality in Social Networks: Conceptual Clarification. Social Networks, 1979, 1: 215-239 [9] Albert R, Barabasi A L. Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 2002, 74(1): 47-97 [10] Dorogovtsev S N, Mendes J F F. Evolution of Networks. Advances in Physics, 2002, 51(4): 1079-1187 [11] Barabasi A L, Jeonga H, Neda Z, et al. Evolution of the Social Network of Scientific Collaborations. Physica A: Statistical and Theoretical Physics, 2002, 311(3): 590-614 [12] Newman M E J. Assortative Mixing in Networks. Physical Review Letters, 2002, 89(20): 208-212 [13] Enron Email Database [DB/OL]. [2007-11-02]. http://bailando.sims.berkeley.edu/enron/enron.sql.gz [14] Shetty J, Adibi J. Discovering Important Nodes through Graph Entropy: The Case of Enron Email Database // Proc of the 3rd International Workshop on Link Discovery. Chicago, USA, 2005: 74-81 [15] Volchenkov D, Blanchard P. Discovering Important Nodes through Graph Entropy Encoded in Urban Space Syntax [EB/OL]. [2007-09-27]. http://arxiv.org/PS_cache/arxiv/pdf/0709/0709.4415v1.pdf [16] Prigogine I. From Being to Becoming. New York, USA: Freeman, 2007 [17] Wang Wenxu, Wang Binghong, Hu Bo, et al. General Dynamics of Topology and Traffic on Weighted Technological Networks [EB/OL]. [2005-05-12]. http://www.sklse.org/whucn/resource/WangBH.pdf [18] Barabasi A L, Albert R, Jeong H. Mean-Field Theory for Scale-Free Random Networks. Physica A: Statistical and Theoretical Physics, 1999, 272: 173-187 [19] Goh K I, Kahng B, Kim D. Universal Behavior of Load Distribution in Scale-Free Networks [EB/OL]. [2003-10-29]. http://arxiv.org/PS_cache/cond-mat/pdf/0304/0304314v3.pdf [20] Goh K I, Oh E, Kahng B, et al. Betweeness Centrality Correlation in Social Networks [EB/OL]. [2003-02-01]. http://arxiv.org/PS_cache/Cond-mat/pdf/0210/0210224v1.pdf [21] Li Wenbin, Zhong Ning, Liu Jiming, et al. Perspective of Applying the Global Email Network // Proc of the IEEE/WIC/ACM International Conference on Web Intelligence. Hongkong, China, 2006: 117-120 [7] Wu Fang, Huberman B A, Adamic L A, et al. Information Flow in Social Groups. Physica A: Statistical and Theoretical Physis, 2004, 337(1/2): 327-335 [11] Boccaletti S, Latora V, Moreno Y, et al. Complex Networks: Structure and Dynamics. Physics Reports, 2006, 424(4/5): 175-308 [21] Berger-Wolf T Y, Saia J. A Framework for Analysis of Dynamic Social Networks // Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, USA, 2006: 523-528 [22] Carley K. Dynamic Network Analysis // Proc of the NRC Workshop on Social Network Modeling and Analysis. Wanshington, USA, 2003: 133-145 [23] Barabasi A L. The Origin of Bursts and Heavy Tails in Human Dynamics. Nature, 2005, 435: 207-211 [24] Skyrms B, Pemantle R. A Dynamic Model of Social Network Formation [EB/OL]. [2000-05-09]. http://www.pnas.org/content/97/16/9340.full.pdf [28] Vazquez A, Oliveira J G, Barabasi A L. The Inhomogeneous Evolution of Subgraphs and Cycles in Complex Networks. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2005, 71(2): 025103 [29] Holme P, Newman M E J. Nonequilibrium Phase Transition in the Coevolution of Networks and Opinions. Physical Review E: Statistical, Nonlinear and Soft Matter Physics, 2006, 74(5): 056108 [30] de Menezes M A, Barabási A L. Fluctuations in Network Dynamics. Physical Review Letters, 2004, 92(2): 028701 [31] Leicht E A, Clarkson G, Shedden K, et al. Large-Scale Structure of Time Evolving Citation Networks. The European Physical Journal B: Condensed Matter and Complex Systems, 2007, 59(1): 75-83
2009, Vol. 22 
