摘要
随着信息技术的发展和社会文明的进步,当前涌现出各式各样的大规模信息网络,如互联网自治域级和路由级的拓扑网络、上层的点对点网络、万维网上的在线社会网络等等。这些网络不仅规模大、结构复杂,而且其结构直接影响网络上的群体行为,从而影响网络的功能。因为这类信息网络与我们的日常生活息息相关,所以深入理解这些网络的拓扑性质、演化规律及其结构对功能的影响就显得尤为重要。实际上,自1998年以来,大量的实证研究表明这类网络具有一些共同的拓扑特征,如“小世界”效应、“无标度”性质、模块性等等,并将这类规模很大且结构复杂的网络笼统地称作“复杂网络”。与传统的小规模或者结构简单的网络相比,复杂网络是一个具有较大挑战的研究课题,因此也吸引了多个学科的学者不断加入到这个研究队伍中来,并逐步形成了“复杂网络”这个交叉研究领域。
毋庸置疑,扩散与传输是信息网络上最常见的群体行为,例如信息包在互联网各路由器之间的传递,新闻、舆情、口碑等在在线社会网络中的扩散等。于是,一个很自然的问题就是：底层的网络结构对扩散和传输行为有何影响?这正是本文研究的两个问题。具体地,主要研究内容和成果如下：
1、分析了含权网络上的扩散行为,结果表明：边权分布越弥散扩散速度也就越慢,且扩散速度在达到峰值之后呈现幂率衰减行为(SI模型)；边权的非对称性对扩散阈值有重要影响,可以通过对边权的非对称性进行平衡或再分配从而增大或减小网络的扩散阈值(SIS模型)。
2、分析了含有群落结构的无标度网络上的扩散行为,结果表明：当无标度网络的模块性较大时,全局同步扩散行为将会消失：而在一个中等的模块性下,网络群落内部的同步扩散行为存在一个最小值;随着网络节点的平均度逐渐增大,同步行为存在一个明显的相变行为(SIRS模型)。
3、从扩散的角度分析了复杂网络的同步性能,结果表明：拉普拉斯特征值之比相同时,网络的同步性能也可能大不一样。具体地,通过理论分析和数值模拟发现了同步时间和最大延时容忍与网络的拉普拉斯特征值之间的对应关系,适当的延时能够提高网络的同步速度。
4、着眼于扩散行为对网络结构演化的反向影响,提出了一个权重网络的演化模型。该模型能够生成生成具有幂率度分布、幂率点权分布、幂率边权分布、点权与节点度非线性相关、大的簇系数、度度相关性为负的权重网络。
5、针对无标度网络,提出了一种有效路由策略。与传统的最短路径路由相比,该有效路由策略能够较大地提高网络的处理能力,从而缓解网络的拥塞。
本论文中的研究结果有助于更好地理解信息网络上的扩散和传输行为的特征和机理。
Spurred by the development of information technology and the advance of social civilization, more and more large-scale information networks emerge. Typical exam-ples include AS-level and router-level topological networks of the Internet, peer-to-peer overlay networks, and online social networks in the World Wide Web. As the networks are closely related to our daily life, it is of utmost importance to search proper methods to characterize basic properties and the evolution of a network's structure, to understand the interplay between the structure and the function of a network. Actually, since 1998 a number of empirical studies have shown that most large-scale networks have some common topological properties, such as the well-known'small-world'effect, scale-freeness, modularity, etc. The kinds of large-scale networks are called roughly'complex networks'. In contrast to simple and small networks, complex network is a very chal-lenging object for research, which attracts more and more attention of interdisplinary researchers recently.
Diffusion and transmission are two important processes taking place in various information networks, such as transmission of packets among ASs or routers in the Internet, diffusion of news, public events or sentiment as well as experience in online social networks, and so on. An important and interesting question is:how does the underlying network structure affect the diffusion and transmission of information on a network? That is the subjectⅠstudied in the thesis. Detailedly, the contents and main results of the thesis are summarized as follows.
1. I have studied the diffusion on weighted scale-free networks and found that the large dispersion of edges weights induce slow diffusion, and the velocity of the diffusion decays in a power-law form after its peak value (SI model). Besides, my results also show that one can restore the diffusion threshold by redistributing or balancing the asymmetric weights of edges (SIS model).
2. I have studied the SIRS diffusion on scale-free networks with communities and found that there exists a critical value of the modularity which separates the global diffusion-induced synchronous phase and asynchronous phase, and the intra-community synchronization is weak while the modularity equals one medium value.
3. I have analyzed the synchronization phenomena on networks from a view point of diffusion and found a relationship between the synchronizing performance, including synchronizing speed and time-delay tolerance, and the Laplacian eigenvalues of the network. Furthermore, I found that proper time-delay can improve the synchronizing speed.
4. Based on the reverse effects of diffusion on network structural evolution, I have thereby proposed an evolutionary model for weighted complex networks. This model can generate weighted scale-free networks with power-law node-degree distribution, power-law node-strength distribution, power-law edge-weight distribution, assortativ-ity, nonlinear degree-strength relation and large clustering coefficient, which were dis-covered widely in real-world information networks.
5. I have also proposed an efficient routing strategy which, comparing with the traditional shortest path routing, can improve the transmission capacity and thus can reduce the congestion of scale-free networks in general. The results in the thesis contribute to a better understanding of information diffu-sion and transmission on real-world large-scale networks.
引文
郭雷,许晓鸣主编.复杂网络.上海科技教育出版社,2006.
汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社,北京,2006.
王飞跃.社会计算的意义及其展望.中国计算机学会通讯,(2),2006.
李国杰.关于网络社会宏观信息学研究的一些思考.中国计算机学会通讯,(2),2006.
张国强,张国清.Internet网络的关联性研究.软件学报,17(3),2006.
程学期,陈海强,韩战钢.社会信息的网络化分析初探.中国计算机学会通讯,(2),2006.
周涛,傅忠谦,牛永伟,王达,曾燕,汪秉宏,and周佩玲.复杂网络上传播动力学研究综述.自然科学进展,15(5),2005.
L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law networks. Physical Review E,64(4):046135,2001.
E. Adar and L. A. Adamic. Tracking information epidemics in blogspace. In Web Intelligence, Compiegne, France,2005.
R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks. Review of Modern Physics,74(1):47-97,2002.
R. Albert. H. Jeong, and A.-L. Barabasi. Diameter of the world-wide web. Nature,401 (6749):130,1999.
A. Almendral and A. Diaz-Guilera. Dynamical and spectral properties of complex net-works. New Journal of Physics,9:187,2007.
R. M. Anderson and R. M. May. Infectious Diseases of Humans:Dynamics and Control. Oxford University Press, USA,1991.
L. Backstrom, D. Huttenlocher, J. M. Kleinberg, and X. Y. Lan. Group formation in large social networks:membership, growth, and evolution. In KDD'06:Proceedings of the 12th ACMSIGKDD, pages 44-54, New York, NY, USA,2006. ACM Press.
N. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Griffin, London,1975.
X. Ban, J. Gao, and A. van de Rijt. Navigation in real-world complex networks through embedding in latent spaces. In Proceedings of the Workshop on Algorithm Engineer- ing and Experiments (ALENEX10), January 2010.
A.-L. Barabasi. Linked:How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life. Plume Books,2003.
A.-L. Barabasi. The architecture of complexity. IEEE Control System Magzine,27(4), 2007.
A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science,286 (5439):509-512,1999.
A.-L. Barabasi and Z. N. Oltvai. Network Biology:Understanding the cell's functional organization. Nature Review Genetics,5:101-113,2004.
M. Barahona and L. M. Pecora. Synchronization in small-world systems. Physical Review Letters,89(5):054101,2002.
A. Barrat and M. Weigt. On the properties of small-world network models. The Euro-pean Physical Journal B,13(3):547-560,2000.
A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America,101:3747-3752,2004a.
A. Barrat, M. Barthelemy, and A. Vespignani. Weighted evolving networks:Coupling topology and weight dynamics. Physical Review Letters,92(22):228701, Jun 2004b.
A. Barrat, M. Barthelemy, and A. Vespignani. Dynamical Processes on Complex Net-works. Cambridge University Press, New York, NY, USA,2008.
M. Barthelemy, A. Barrat, R. Pastor-Satorras, and A. Vespignani. Velocity and hierar-chical spread of epidemic outbreaks in scale-free networks. Physical Review Letters, 92:178701,2004.
A. Blum, H. Chan, and M. Rwebangira. In In ANALCO'06:Proceedings of the 3rd Workshop on Analytic Algorilhmics and Combinatorics),2006.
S. Boettcher and A. G. Percus. Optimization with extremal dynamics. Physical Review Letters,86(23):5211-5214,2001.
M. Boguna, R. Pastor-Satorras, and A. Vespignani. Absence of epidemic threshold in scale-free networks with degree correlations. Physical Review Letters,90(2):028701, 2003.
B. Bollobas. Graph Theory:An Introductory Course. Springer Verlag, New York, 1979.
B. Bollobas. Random Graphs. Cambridge University Press,2nd edition,2001.
B. Bollobas and O. Riordan. Clique percolation. Random Structure and Algorithms,35 (3):294-322,2009.
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks,33(1-6):309-320, 2000.
T.N.Bui and C.Jones. Finding good approximate vertex and edge partitions is np-hard. Information Processing Letters,42(3):153-159,1992.
R. S. Burt. Structural holes:The social structure of competition. Harvard University Press, Cambridge, MA,1992.
G. Caldarelli. Scale-Free Networks. Oxford University Press,2007.
J. M. Carlson and J. Doyle. Highly optimized tolerance:a mechanism for power laws in designed systems. Physical Review E,60(2):1412-1417.1999.
S. Carmi, S. Carter, J. Sun, and D. ben Avraham. Asymptotic behavior of the kleinberg model. Physical Review Letters,102(23):238702, Jun 2009.
C. Caretta Cartozo and P. De Los Rios. Extended navigability of small world networks: Exact results and new insights. Physical Review Letters,102(23):238703. Jun 2009.
D. Chakrabarti and C. Faloutsos. Graph mining:Laws, generators, and algorithms. ACM Computing Surveys,38(1),2006.
D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos. Epidemic thresholds in real networks. ACM Transaction on Information System Security,10(4),2008.
T. Chen, W. Wu, and W. Zhou. Global μ-synchronization of linearly coupled unbounded time-varying delayed neural networks with unbounded delayed coupling. IEEE trans-action on Neural Networks,19,2008.
N. A. Christakis and J. H. Fowler. Connected:The Surprising Power of Our Social Networks and How They Shape Our Lives. Little, Brown and Company,2009.
F. R. K. Chung. Spectral Graph Theory. American Mathematical Society,1997.
F. R. K. Chung and L. Lu. The diameter of sparse random graphs. Advances in Applied Mathematics,26(4):257-279,2001.
A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. SIAM Review, (51),2009.
V. Colizza, R. Pastor-Satorras, and A. Vespignani. Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nature Physics,3:276-282. 2007.
D. Cosley, D. Huttenlocher, J. M. Kleinberg, X. Lan, and S. Suri. Sequential influence models in social networks. In Proc.4th International AAAI Conference on Weblogs and Social Media,2010,2010.
O. Simsek and D. Jensen. Navigating networks by using homophily and degree. Pro-ceedings of the National Academy of Sciences of USA,105(35):12758-12762,2008.
D. Cvetkovic, M. Doob, and H. Sachs. Spectra of graphs-Theory and application. Deutscher Verlag der Wissenschaften-Academic Press, Berlin,1980.
E. M. Daly and M. Haahr. Social network analysis for information flow in disconnected delay-tolerant manets. IEEE Transactions on Mobile. Computing,8(5):606-621, 2009.
B. Danila, Y. Yu, J. A. Marsh, and K. E. Bassler. Optimal transport on complex net-works. Physical Review E,74(4):046106,2006.
D. J. de Solla Price. Networks of scientific papers. Science,169:510-515.1965.
D. J. de Solla Price. A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science, (27),292-306.
I. Derenyi, G. Palla, and T. Vicsek. Clique percolation in random networks. Physical Review Letters, (94),2005.
L. Donetti, P. I. Hurtado, and M. A. Mu noz. Entangled networks, synchronization, and optimal network topology. Physical Review Letters,95(18):188701,2005.
S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks:From Biological Nets to the Internet and WWW. Oxford University Press,2003.
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. Structure of growing networks with preferential linking. Physical Review Letters,85:4633-4636,2000a.
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. Structure of growing networks with preferential linking. Physical Review Letters,85:4633-4636,2000b.
J. Doyle and J. M. Carlson. Power laws, highly optimized tolerance, and generalized source coding. Physical Review Letters,84(24):5656-5659,2000.
J. Doyle and J. M. Carlson. Complexity and robustness. Proceedings of the National Academy of Sciences of USA,99:2538-2545,2002.
D. Easley and J. M. Kleinberg. Networks, Crowds, and Markets:Reasoning About a Highly Connected World. To be published by Cambridge University Press,2010. URL http://www.cs.cornell.edu/home/kleinber/networks-book/.
H. Ebel, L.-I. Mielsch, and S. Bornholdt. Scale-free topology of e-mail networks. Phys- ical Review E,66(3):035103,2002.
P. Erdos and A. Renyi. On the evolution of random graphs. Publication of the Mathe-matical Institute of the Hungarian Academy of Science, pages 17-61,1960.
P. Erdos and G. Szekeres. A combinatorial problem in geometry. Compositio Math., (2),1935.
A. Fabrikant, E. Koutsoupias, and C. H. Papadimitriou. Heuristically optimized trade-offs:A new paradigm for power laws in the internet. In In ICALP'02:Proceedings of the 29th International Colloquium on Automata, Languages, and Programming), volume 2380,2002.
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM'99:Proceedings of the conference on Applications, tech-nologies, architectures, and protocols for computer communication, pages 251-262, New York, NY, USA,1999. ACM.
A. Flaxman, A. M. Frieze, and J. Vera. A geometric preferential attachment model of networks. In Stefano Leonardi, editor, In WAW'04:Proceedings of the 2nd Workshop On Algorithms And Models For The Web-Graph, volume 3243 of Lecture Notes in Computer Science, pages 44-55. Springer,2004.
A. Flaxman, A. M. Frieze, and J. Vera. A geometric preferential attachment model of networks ii. In In WAW'04:Proceedings of the 2nd Workshop On Algorithms And Models For The Web-Graph, pages 41-55,2007.
J. Fodor. The Modularity of Mind. MIT/Bradford Press, Cambridge, MA,1983.
S. Fortunato. Community detection in graphs. Physics Reports,486(3-5):75-174, 2010.
S. Fortunato and M. Barthelemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences,104(1):36-41,2007.
L. C. Freeman. Centrality in social networks:Conceptual clarification. Social Networks, 1(3):215-239,1979.
A. Fronczak, P. Fronczak, and J. A. Holyst. Mean-field theory for clustering coefficients in barabasi-albert networks. Physical Reviewe E,68(4),2003.
P. M. Gade and S. Sinha. Dynamic transitions in small world networks:Approach to equilibrium limit. Physical Review E,72,2005.
M. Girvan and M. E. J. Newman. Community structure in social and biological net-works. Proceedings of the National Academy of Sciences of the United States of America,99(12):7821-6,2002.
K. I. Goh, B. Kahng, and D. Kim. Universal behavior of load distribution in scale-free networks. Physical Review Letters,87(27):278701,2001.
J. Goldenberg, B. Libai, and E. Muller. Talk of the network:A complex systems look at the underlying process of word-of-mouth. Marketing Letters,2001.
M. Granovetter. The strength of weak ties. American Journal of Sociology,78(6): 201-233,1973.
M. Granovetter. Threshold Models of Collective Behavior. American Journal of Soci-ology,83(6):1420,1978.
D. Gruhl, R. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In WWW'04:Proceedings of the 13th international conference on World Wide Web, pages 491-501. ACM New York, NY, USA,2004.
R. Guimera, A. Diaz-Guilera, F. Vega-Redondo, A. Cabrales, and A. Arenas. Optimal network topologies for local search with congestion. Physical Review Letters,89 (24):248701,2002.
F. Harary. Graph Theory. Addison-Wesley, Reading, Cambridge, MA,1969.
P. Holme and B. J. Kim. Growing scale-free networks with tunable clustering. Physical Reviewe E,65(2),2002.
M.-B. Hu, W.-X. Wang, R. Jiang, Q.-S. Wu, and Y.-H. Wu. The effect of bandwidth in scale-free network traffic, EPL,79(1):14003,2007.
B. A.-Huberman. The Laws of the Web:Patterns in the Ecology of Information. The MIT Press,2001.
B. A. Huberman and L. A. Adamic. Growth dynamics of the world-wide web. Nature, 399,1999.
L. Hufnagel, D. Brockmann, and T. Geisel. Forecast and control of epidemics in a globalized world. Proceedings of the National Academy of Sciences of the United States of America,101,2004.
N. Kashtan and U. Alon. Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences of USA,102(39):13773-13778, 2005.
M.J. Keeling and P. Rohani. Modeling Infectious Diseases in Humans and Animals. Princeton University Press,2008.
D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD'03:Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146. ACM Press, 2003.
J. M. Kleinberg. Navigation in a small world. Nature,406(6798),2000a.
J. M. Kleinberg. The small-world phenomenon:an algorithm perspective. In STOC'00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 163-170, New York, NY, USA,2000b. ACM.
J. M. Kleinberg. The convergence of social and technological networks. Communica-tions of the ACM,51(11),2008.
J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The Web as a graph:measurements, models and methods. In Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON), volume 1627 of Lecture Notes in Computer Science, pages 1-18, Tokyo, Japan,1999. Springer.
P. L. Krapivsky and S. Redner. Organization of growing random networks. Physical Review E,6306(6):066123,2001.
P. L. Krapivsky and S. Redner. Network growth by copying. Physical Review E,70: 036118,2005.
P. L. Krapivsky, S. Redner, and F. Leyvraz. Connectivity of growing random networks. Physical Review Letters,85(21):4629-4632,2000.
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the Web graph. In In FOCS'00:Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 57,2000.
R. Kumar, J. Novak, P. Raghavan, and A. Tomkins. Structure and evolution of blogspace. Communication of ACM,47(12):35-39,2004.
R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In KDD'06:Proceedings of the 12th ACM SIGKDD, pages 611-617, New York, NY, USA,2006. ACM.
J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD 06:Proceedings of the 12th ACM SIGKDD, pages 631-636, New York, NY, USA,2006. ACM Press.
J. Leskovec,J. M. Kleinberg. and C. Faloutsos. Graphs over time:densification laws, shrinking diameters and possible explanations. In KDD'05:Proceeding of the eleventh ACM SIGKDD, pages 177-187, New York, NY, USA,2005. ACM Press.
J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing.
ACM Transaction on Web,1(1):5,2007.
J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Statistical properties of community structure in large social and information networks. In WWW'08:Pro-ceeding of the 17th international conference on World Wide Web, pages 695-704, New York, NY, USA,2008. ACM.
C.-G. Li and P. K. Maini. An evolving network model with community structure. Jour-nal of Physics A:Mathematical and General,38(45),2005.
L. Li, D. Alderson, J. C. Doyle, and W. Willinger. Towards a theory of scale-free graphs: Definition, properties, and implications. Internet Mathematics,2(4):431-523,2005.
X. Li and G. Chen. A local-world evolving network model. Physica A,328(1-2): 274-286,2003.
X. Li and X.-F. Wang. Controlling the spreading in small-world evolving networks: Stability, oscillation, and topology. IEEE Transaction on Automatic Control,51(3), 2006.
X. Li, X.-F. Wang, and G. Chen. Pinning a complex dynamical network to its equilib-rium. IEEE Transaction on Circuits and Systems-Ⅰ:Regular Papers,51(10),2004.
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences of USA, 102(33):11623-11628. 2005.
E. N. Lorenz. Deterministic nonperiodic flow. Journal of the Atmospheric Sciences, 20:130,1963.
J. Lu and G. Chen. A brief overview of some recent advances in complex dynamical networks control and synchronization. In ISCAS, pages 2518-2521. IEEE,2008.
R. D. Luce and A. D. Perry. A method of matrix analysis of group structure. Prychome-trika,14(2),1949.
S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science,296:910-913,2002.
R. M. May and, A. L. Lloyd. Infection dynamics on scale-free networks. Physical Review E,64(6):066112,2001.
S. Milgram. The small world problem. Psychology Today,1:61,1967.
A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measure-ment and analysis of online social networks. In IMC'07:Proceedings of the 5th ACM/USENIX Internet Measurement Conference,2007.
V. Misra, W. Gong, and D. F. Towsley. Fluid-based analysis of a network of aqm routers supporting tcp flows with an application to red. In SIGCOMM 00', pages 151-160, 2000.
M. Molloy and B. Reed. A critical point for random graphs with a given degree se-quence. Random Structure and Algorithms,6(2-3):161-179,1995.
C. Moore and M. E. J Newman. Epidemics and percolation in small-world networks. Physical Review E,61(5):5678-5682,2000.
M. Bogu na and D. Krioukov. Navigating ultrasmall worlds in ultrashort time. Physical Review Letters,102(5):058701,2009.
M. Bogu na, D. Krioukov, and kc claffy. Navigability of complex networks. Nature Physics,5,2008.
M. E. J. Newman. Assortative mixing in networks. Physical Review Letters,89(20): 208701,2002.
M. E. J. Newman. The structure and function of complex networks. SIAM Review,45 (2):167-256,2003.
M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America,103(23):8577-8582, 2006.
M. E. J. Newman and D. J. Watts. Renormalization group analysis of the small-world network model. Phyisics Letter A,263(4-6),1999.
M. E. J. Newman, A.-L. Barabasi, and D. J. Watts. The Structure and Dynamics of Networks. Princeton University Press,2006.
R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transaction on Automatic Control,49: 1520-1533,2004.
R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE,95(1):215-233,2007.
G. Palla,I. Derenyi,I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature,435(7043):814-818, 2005.
M. Parameswaran and A. B. Whinston. Research issues in social computing. Journal of the Association for Information Systems,8:336-350,2007.
R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys- ical Review Letters,86(14):3200-3203,2001.
R. Pastor-Satorras and A. Vespignani. Epidemic dynamics in finite size scale-free net-works. Physical Review E,65(3):035108,2002.
L. M. Pecora and T. L. Carroll. Master stability functions for synchronized coupled systems. Physical Review Letters,80(10):2109-2112,1998.
D. M. Pennock, G. W. Flake, S. Lawrence, E..1. Glover, and C. L. Giles. Complexity and robustness. Proceedings of the National Academy of Sciences of USA,99(8): 5207-5211,2002.
S. R. Proulx, D. E. L. Promislow, and P. C. Phillips. Network thinking in ecology and evolution. Trends in Ecology and Evolution,20(6):345-353,2005.
W. Ren, R. W. Beard, and E. M. Atkins. A survey of consensus problems in multi-agent coordination. American Control Conference,2005. Proceedings of the 2005, 3:1859-1864,2005.
M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD'02:Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 61-70. ACM,2002.
M. Ripeanu, A. lamnitchi, and I. Foster. Mapping the Gnutella network. IEEE Internet Computing Journal,6(1):50-57; 2002.
E. M. Rogers. Diffusion of innovations. Free Press, New York,1995.
D. Saad and M. Opper, editors. Advanced Mean Field Methods—Theory and Practice. MIT Press,2000.
F. C. Santos, J. F. Rodrigues, and J. M. Pacheco. Epidemic spreading and cooperation dynamics on homogeneous small-world networks. Physical Review E,72(5),2005.
H. W. Shen, X. Q. Cheng, K. Cai, and M.-B. Hu. Detect overlapping and hierarchical community structure in networks. arXiv:CoRR, abs/0810.3093,2008.
C. Song, S. Havlin, and H. A. Makse. Self-similarity of complex networks. Nature, 433(7024):392-395,2005.
V. Spirin and L. A. Mirny. Protein complexes and functional modules in molecular networks. Proceedings of the National Academy of Sciences of the United States of America,100:12123-12128,2003.
S. Sreenivasan, R. Cohen, E. Lopez, Z. Toroczkai, and H. E. Stanley. Structural bottle-necks for communication in networks. Physical Review E.75(3):036105,2007.
B. Tadic and G. J. Rodgers. Packet transport on scale-free networks. Advances in Complex Systems,5,2002.
B. Tadic, S. Thurner, and G. J. Rodgers. Traffic on complex networks:Towards under-standing global statistical properties from microscopic density fluctuations. Physical Review E,69,2004.
L. Tauro, C. Palmer, G. Siganos, and M. Faloutsos. A simple conceptual model for the internet topology. In GLOBECOM' 01:Global Telecommunications Conference, volume 3, San Antonio, Texas, USA,2001. IEEE CS Press.
C. Teuscher. Nature-inspired interconnects for self-assambled large-scale network-on-chip designs. Chaos,17,2007.
M. Timme, F. Wolf, and T. Geisel. Topological speed limits to network synchronization. Physical Review Letters,92(7):074101,2004.
Z. Toroczkai and K. E. Bassler. Jamming is limited in scale-free systems. Nature,428, 2004.
J. Travers and S. Milgram. An experimental study of the small world problem. Sociom-etry,32:425-443,1969.
A. Vazquez. Disordered networks generated by recursive searches. Europhysics Letters, 54(4),2001.
A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dy-namical properties of the Internet. Physical Review E,65(6):66130,2002.
A. Vazquez. M. Boguna, Y. Moreno, R. Pastor-Satorras, and A. Vespignani. Topology and correlations in structured scale-free networks. Physical Review E,67:046111, 2003.
W.-X. Wang, B.-H. Wang, B. Hu, G. Yan, and Q. Ou. General dynamics of topology and traffic on weighted technological networks. Physical Review Letters,94(18): 188702,2005.
X.-F. Wang and G. Chen. Synchronization in small-world dynamical networks. Inter-national Journal of Bifurcation and Chaos,12(1):187-192,2002.
X.-F. Wang and G. Chen. Complex networks:small-world, scale-free and beyond. IEEE Circuits and Systems Magazine,3(1):6-20,2003.
S. Wasserman and K. Faust. Social Network Analysis:Methods and Applications. Cam-bridge University Press,1994.
D. J. Watts. Six Degrees:The Science of a Connected Age. W. W. Norton & Company, 2004.
D. J. Watts and S. H. Strogatz. Collective dynamics of'small-world'networks. Nature, 393(6684):440-442,1998.
F. Wei, W. N. Qian, C. Wang, and A. Y. Zhou. Detecting overlapping community structures in networks. World Wide Web,12(2):235-261,2009.
J.-J. Wu, H.-J. Sun, and Z.-Y. Gao. Dynamic urban traffic flow behavior on scale-free networks. Physica A,387,2008.
R. Xulvi-Brunet and I. M. Sokolov. Reshuffling scale-free networks:From random to assortative. Physical Review E,70(6),2004.
R. Xulvi-Brunet and I. M. Sokolov. Changing correlations in networks:Assortativity and dissortativity. in Acta Physica Polonica, Series B, Zakopane,36(5),2005.
G. Yan, T. Zhou, J. Wang, Z.-Q. Fu, and B.-H. Wang. Epidemic spread in weighted scale-free networks. Chinese Physics Letters,22(2),2005.
G. Yan, T. Zhou, B. Hu, Z.-Q. Fu, and B.-H. Wang. Efficient routing on complex networks. Physical Review E,73,2006.
G. Yan, Z.-Q. Fu, J. Ren, and W.-X. Wang. Collective synchronization induced by epidemic dynamics on complex networks with communities. Physical Review E,75 (1):016108,2007.
G. Yan, Z.-Q. Fu, and G. Chen. Epidemic threshold and phase transition in scale-free networks with asymmetric infection. The European Physical Journal B,65(4), 2008a.
G. Yan, Z.-Q. Fu, and G. Chen. Consensus on de bruijn graphs. The European Physical Journal B,63(4),2008b.
G. Yan, G. Chen, J. Lu, and Z.-Q. Fu. Synchronization performance of complex oscil-lator networks. Physical Review E.80,2009.
Y. Zhang, J. Wang, Y. Wang, and L. Zhou. Parallel community detection on large networks with propinquity dynamics. In KDD'09:Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 997-1006, New York, NY, USA,2009. ACM.
L. Zhao, Y.-C. Lai, K. Park, and N. Ye. Onset of traffic congestion in complex networks. Physical Review E,71(2):026125,2005.
T. Zhou. Mixing navigation on networks. Physica A,387,2008.