7 2-3 Vol. 7 No. 2-3 2010 9 COMPLEX SYSTEMS AND COMPLEXITY SCIENCE Sep. 2010 1672-3813 2010 02-03 - 0173-14 1 2 1 3 4 5 6 7 8 9 10 1. CH - 1700 2. 430072 3. 050043 4. D - 14469 5. 100876 6. 200444 7. 550005 8. 102413 9. 610054 10. 230026 N94 A Looking into Complex Networks L Lin-yuan 1 LU Jun-an 2 ZHANG Zi-ke 1 YAN Xiao-yong 3 WU Ye 4 5 SHI Ding-hua 6 ZHOU Hai-ping 7 FANG Jin-qing 8 ZHOU Tao 9 10 1. Department of Physics University of Fribourg Fribourg 1700 Switzerland 2. School of Mathematics and Statistics Wuhan University Wuhan 430072 China 3. Department of Transportation Engineering Shijiazhuang Tiedao University Shijiazhuang 050043 China 4. Interdisciplinary Center for Dynamics of Complex Systems University Potsdam Potsdam D-14469 Germany 5. School of Science Beijing University of Posts and Telecommunications Beijing 100876 6. Department of Mathematics Shanghai University Shanghai 200444 China 7. Department of Computer Science Guiyang College Guiyang 550005 China 8. China Institute of Atomic Energy Beijing 102413 China 9. Web Sciences Center University of Electronic Science and Technology of China Chengdu 610054 China 10. Department of Modern Physics University of Science and Technology of China Hefei 230026 China Abstract This article summaries the discussions about the open issues and research tendency of complex networks by several active scholars. The statement covers both fundamental problems like the understand- 2010-06 - 21 1984 -
174 2010 9 ing of power-law degree distributions the underlying connections between different flow-driven dynamics and the mechanism leading to acceleratingly growing and the in-depth analyses like the understanding of mesoscales in complex networks. Moreover we introduce some typical interdisciplinary studies where complex networks play a major role including the link prediction in complex networks recommender systems for user-object bipartite networks the integration of cyber physical systems and complex networks the human dynamics in the online network space and the possibly important role of the studies of complex networks in national security. Key words complex networks degree distribution acceleratingly growing synchronization epidemic spreading network traffic flow-driven dynamics mesoscales link prediction recommender systems cyber physical systems human dynamics 1 1998 Watts Strogatz 1 1999 Barabási Albertt 2 1 10 2000 ~ 200910 complex networks topic SCI 4 925 76 834 1 2 SCI 1 318 1 SCI 2 SCI 1 318 7 229
7 2-3 175 2 Barabási 3 4-6 7-9 10-13 3 3 2 4 1 3 2 7 1 3 2 10 1 3 2 10 13 3 2 1 14 1 1 Barabási 2 BA 7 7 2 2 2 2 3 2 t - 1 2 t 2 t + 1 3 t 3 t - 1 3 t - 2 3 2 3 3 3 3 t + 1 /2 7 2 2 2 2 3 2 3 2 7 3 2 1 3 2 7 Heaviside 4 1 1 1
176 2010 9 k 1 3 2005 1 Motter Kurths E 15 1 k k k 16 17 2005 E 2 590 3 2006 2 2006 4 E 18 19 2006 E 2 425 6 4 k k α k α 1-1 flow-driven dynamics contact process k f k f k = 1 /k f k 2008 12 E 20 4 CHAOS 20 010202 2010 Announcement Focus Issue on Mesoscales in Complex Networks Mesoscales 2006 21
7 2-3 177 21 motifs cliques cores loops Lyapunov 22 KM ER SF 0 SF ER SF ER SF GC NC GC SF ER NC ER SF ER GC SF ER NC SF SF hubs hubs ER SF SF ER 23-24 1 SF hubs ER SF ER 2 SF 3 5
178 2010 9 25 26-32 m t m t 25 27 33 34 6
7 2-3 179 35 36 37 Liben-Nowell Kleinberg 38 39 6 9 resource allocation index local path 9 40 41 42 43 5
180 2010 9 Clauset Moore Newman 44 Guimera Sales-Pardo 37 Stochastic Block Model 44 45 Leskovec Huttenlocher Kleinberg 46 Multi-Partite Networks 1 2 3 4 5 7 The Big Bang Theory Shelton Heat Conduction
7 2-3 181 47-48 - Mass Diffusion 49-53 Random Walk 48 53 48 8 Cyber physical system CPS CPS 54-55 Internet CPS
182 2010 9 CPS CPS CPS CPS CPS 8. 1 CPS 20 40 CPS CPS CPS NSF CPS CPS 2007 7 PCAST CPS 8. 2 CPS RFID RFID CPS RFID CPS CPS RFID CPS CPS 56 CPS CPS / 57 8. 3 CPS CPS CPS CPS CPS / CPS CPS CPS 1 CPS 2 CPS 3 CPS 8. 4 CPS 10 CPS
7 2-3 183 CPS CPS CPS CPS 9 2005 58 - Barabási Nature 59 Barabási inter-event inter-event power-law Weill Barabási inter-event time BBS interevent BBS BBS 3 A B B A A
184 2010 9 10 1945 8 6 B-29 14 1945 8 9 8 2009 John Bohannon e-mail Brian Uzzi 5 1 Watts D J Strogatz S H. Collective dynamics of small-world networks J. Nature 1998 393 440-442. 2 Barab si A-L Albert R. Emergence of scaling in random networks J. Science 1999 286 509-512. 3 Barab si A-L Ravasz E Vicsek T. Determinic scale-free networks J. Physica A 2001 229 559-564. 4 Farkas I Derényi I Jeong H et al. Networks in life scaling properties and eigenvalue spectra J. Physica A 2002 314 25-34. 5 Ravasz E Barab si A-L. Hierarchical organization in complex networks J. Phys Rev E 2003 67 026112.
7 2-3 185 6 Ravasz E Somera A L Mongru D A et al. Hierarchical organization of modularity in metabolic networks J. Science 2002 297 1551-1555. 7 Dorogovtsev S N Gotsev A V Mendes J F F. Pseudofractal scale-free web J. Phys Rev E 2002 65 066122. 8 Jung S Kim S Kahng B. Geometric fractal growth model for scale free networks J. Phys Rev E 2002 65 056101. 9 Zhang Z Z Rong L L Zhou S G. A geometric fractal growth model for pseudofractal scale-free web J. Physica A 2007 377 329-339. 10 Andrade J S Herrmann H J Andrade R F S et al. Apollonian networks simultaneously scale-free small world euclidean space filling and with matching graphs J. Phys Rev Let 2005 94 018702. 11 Zhang Z Z Rong L L Zhou S G. Evolving apollonian networks with small-world scale-free topologies J. Phys Rev E 2006 74 046105. 12 Guo J L. Scale-free networks with self-similarity degree exponents J. Chin Phys Lett 2010 27 038901. 13 Andrade J S Herrmann H J Andrade R F S et al. Erratum apollonian networks simultaneously scale-free small world euclidean space filling and with matching graphs J. Phys Rev Lett 2009 102 079901. 14 Li L Alderson D Doyle J C et al. Towards a theory of scale-free graphs definitions properties and implications J. Internet Math 2005 2 431-523. 15 Motter A E Zhou C S Kurths J. Network synchronization diffusion and the paradox of heterogeneity J. Phys Rev E 71 2005 016116. 16 Nishikawa T Motter A E Lai Y C et al. Heterogeneity in oscillator networks are smaller worlds easier to synchronize J. Phys Rev Lett 2003 91 014101. 17 Zhao M Zhou T Chen G R Wang B H. Enhancing the network synchronizability J. Front Phys China 2007 2 460. 18 Wang W X Wang B H Yin C Y et al. Traffic dynamics based on local routing protocol on scale-free networks J. Phys Rev E 2006 73 026111. 19 Yan G Zhou T Hu B et al. Efficient routing on complex networks J. Phys Rev E 2006 73 046108. 20 Yang R Zhou T Xie Y B et al. Optimal contact process on complex networks J. Phys Rev E 2008 78 066109. 21 Arenas A Diaz-Guilera A Perez-Vicente C J. Synchronization processes in complex networks J. Physica D 2006 224 27-34. 22 Gomez-Gardenes J Moreno Y Arenas A. Paths to synchronization on complex networks J. Phys Rev Lett 2007 98 034101. 23 Chen J Lu J A Wu X et al. Generalized synchronization of complex dynamical networks via impulsive control J. Chaos 2009 19 043119. 24 Liu H Chen J Lu J A et al. Generalized synchronization in complex dynamical networks via adaptive couplings J. Physica A 2010 389 1759-1770. 25 Dorogovtsev S N Mendes J F F. Evolution of networks J. Adv Phys 2002 51 1079. 26 Barab si A-L Jeong H Néda Z et al. Evolution of the social network of scientic collaboration J. Physica A 2002 311 590. 27 Sen P. Accelerated growth in outgoing links in evolving networks deterministic versus stochastic picture J. Phys Rev E 2004 69 046107. 28 Shi D H Chen Q H Liu L M. Markov chain-based numerical method for degree distributions of growing networks J. Phys Rev E 2005 71 036140. 29 Gagen M J Mattick J S. Accelerating hyperaccelerating and decelerating networks J. Phys Rev E 2005 72 016123. 30 Yuan W J Luo X S Zhou J F et al. Acceleratingly growing scale-free networks with tunable degree exponents J. Physica A 2008 387 5311-5316. 31 Smith D M D Onnela J P Jones N S. Master-equation analysis of accelerating networks J. Phys Rev E 2009 79 056101. 32 Zhang Z Z Fang L J Zhou S G et al. Effects of accelerating growth on the evolution of weighted complex networks J. Physica A 2009 388 225-232. 33 Varian H R. Intermediate Microeconomics a Modern Approach M. New York W W Norton & Company 2006 65. 34 Lü L Zhang Z K Zhou T. Zipf' s law leads to heaps' law analyzing their relation in finite-size systems DB /OL. 2010-05 - 03. http / /arxiv. org /abs /1002. 3861.
186 2010 9 35. J. 2010 39 5 651-661. Lü Linyuan. Link prediction on complex networks J. Journal of University of Electronic Science and Technology of China Natural Science Edition 2010 39 5 651-661. 36 Zhang Q M Shang M S Lü L. Similarity-based classification in partial labeled networks J. Int J Mod Phys C 2010 21 813. 37 Guimera R Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks J. PNAS 2009 106 22073. 38 Liben-Nowell D Kleinberg J. The link-prediction problem for social networks J. J Am Soc Inform Sci Technol 2007 58 1019. 39 Zhou T Lü L Zhang Y C. Predicting missing links via local information J. Eur Phys J B 2009 71 623. 40 Pan Y Li D H Liu J G et al. Detecting community structure in complex networks via node similarity J. Physica A 2010 389 2849. 41 Wang Y L Zhou T Shi J J et al. Emipirical analysis of dependence between stations in Chinese railway network J. Physica A 2009 388 2949. 42 Lü L Jin C H Zhou T. Similarity index based on local paths for link prediction of complex networks J. Phys Rev E 2009 80 046122. 43 Liu W P Lü L. Link prediction based on local random walk J. Europhys Lett 2010 89 58007. 44 Clauset A Moore C Newman M E J. Hierarchical structure and the prediction of missing links in networks J. Nature 2008 453 98. 45 Lü L Zhou T. Link prediction in weighted networks the role of weak ties J. Europhys Lett 2010 89 18001. 46 Leskovec J Huttenlocher D Kleinberg J. Predicting positive and negative links in online social networks C. Proc WWW 2010. New York ACM 2010. 47 Zhang Y C Blattner M Yu Y K. Heat conduction process on community networks as a recommendation model J. Phys Rev Lett 2007 99 154301. 48 Zhou T Kuscsik Z Liu J G et al. Hybrid algorithms to customize and optimize diversity and accuracy of recommendations J. PNAS 2010 107 4511 49 Zhang Y C Medo M Ren J et al. Recommendation model based on opinion diffusion J. EPL 2007 80 68003. 50 Zhou T Ren J Medo M et al. Bipartite network projection and personal recommendation J. Phys Rev E 2007 176 046115. 51 Zhou T Jiang L L Su R Q et al. Effect of initial configuration on network-based recommendation J. EPL 2008 81 58004. 52 Zhang Z K Zhou T Zhang Y C. Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs J. Physica A 2010 389 179. 53 Zhou T Su R Q Liu R R et al. Accurate and diverse recommendations via eliminating redundant correlations J. New J Phys 2009 11 123008. 54 Stankovic J Lee I Mok A et al. Opportunities and obligations for physical computing systems J. IEEE Computer 2005 38 11 23-31. 55 Edward L. Cyber physical systems design challenges C. Proc 11th IEEE international symposium on object oriented real-time distributed computing. USA IEEE Press 2008. 56 Mohan P Padmanabhan V Ramjee R. Nericell rich monitoring of road and traffic conditions using mobile smartphones C. Proc 6th ACM Conference on Embedded Network Sensor Systems. New York ACM Press 2008. 57 Wang M Cao J Li J et al. Middleware for wireless sensor networks a survey J. J Comput Sci Technol 2008 23 305-326. 58 Barab si A-L. The origin of bursts and heavy tails in human dynamics J. Nature 2005 435 207-211. 59 Oliveira J G Barab si A-L. Darwin and Einstein correspondence patterns J. Nature 2005 437 1251.