 Complex network

In the context of network theory, a complex network is a graph (network) with nontrivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in real graphs. The study of complex networks is a young and active area of scientific research inspired largely by the empirical study of realworld networks such as computer networks and social networks.
Contents
Definition
Most social, biological, and technological networks display substantial nontrivial topological features, with patterns of connection between their elements that are neither purely regular nor purely random. Such features include a heavy tail in the degree distribution, a high clustering coefficient, assortativity or disassortativity among vertices, community structure, and hierarchical structure. In the case of directed networks these features also include reciprocity, triad significance profile and other features. In contrast, many of the mathematical models of networks that have been studied in the past, such as lattices and random graphs, do not show these features.
Two wellknown and much studied classes of complex networks are scalefree networks and smallworld networks, whose discovery and definition are canonical casestudies in the field. Both are characterized by specific structural features—powerlaw degree distributions for the former and short path lengths and high clustering for the latter. However, as the study of complex networks has continued to grow in importance and popularity, many other aspects of network structure have attracted attention as well.
The field continues to develop at a brisk pace, and has brought together researchers from many areas including mathematics, physics, biology, computer science, sociology, epidemiology, and others. Ideas from network science have been applied to the analysis of metabolic and genetic regulatory networks, the design of robust and scalable communication networks both wired and wireless, the development of vaccination strategies for the control of disease, and a broad range of other practical issues. Research on networks has seen regular publication in some of the most visible scientific journals and vigorous funding in many countries, has been the topic of conferences in a variety of different fields, and has been the subject of numerous books both for the lay person and for the expert.
Scalefree networks
Main article: Scalefree networksA network is named scalefree ^{[1]}
if its degree distribution, i.e., the probability that a node selected uniformly at random has a certain number of links (degree), follows a particular mathematical function called a power law. The power law implies that the degree distribution of these networks has no characteristic scale. In contrast, network with a single welldefined scale are somewhat similar to a lattice in that every node has (roughly) the same degree. Examples of networks with a single scale include the Erdős–Rényi (ER) random graph and hypercubes. In a network with a scalefree degree distribution, some vertices have a degree that is orders of magnitude larger than the average  these vertices are often called "hubs", although this is a bit misleading as there is no inherent threshold above which a node can be viewed as a hub. If there were such a threshold, the network would not be scalefree.
Interest in scalefree networks began in the late 1990s with the apparent discovery of a powerlaw degree distribution in many real world networks such as the World Wide Web, the network of Autonomous systems (ASs), some network of Internet routers, protein interaction networks, email networks, etc. Although many of these distributions are not unambiguously power laws, their breadth, both in degree and in domain, shows that networks exhibiting such a distribution are clearly very different from what you would expect if edges existed independently and at random (a Poisson distribution). Indeed, there are many different ways to build a network with a powerlaw degree distribution. The Yule process is a canonical generative process for power laws, and has been known since 1925. However, it is known by many other names due to its frequent reinvention, e.g., The Gibrat principle by Herbert Simon, the Matthew effect, cumulative advantage and, most recently, preferential attachment by Barabási and Albert for powerlaw degree distributions.
Networks with a powerlaw degree distribution can be highly resistant to the random deletion of vertices, i.e., the vast majority of vertices remain connected together in a giant component. Such networks can also be quite sensitive to targeted attacks aimed at fracturing the network quickly. When the graph is uniformly random except for the degree distribution, these critical vertices are the ones with the highest degree, and have thus been implicated in the spread of disease (natural and artificial) in social and communication networks, and in the spread of fads (both of which are modeled by a percolation or branching process). While random graphs (ER) have an average distance of order log N ^{[2]} between nodes, where N is the number of nodes, scale free graph can have a distance of log log N. Such graphs are called ultra small world networks.^{[3]}
Smallworld networks
Main article: Smallworld networkA network is called a smallworld network ^{[2]} by analogy with the smallworld phenomenon (popularly known as six degrees of separation). The small world hypothesis, which was first described by the Hungarian writer Frigyes Karinthy in 1929, and tested experimentally by Stanley Milgram (1967), is the idea that two arbitrary people are connected by only six degrees of separation, i.e. the diameter of the corresponding graph of social connections is not much larger than six. In 1998, Duncan J. Watts and Steven Strogatz published the first smallworld network model, which through a single parameter smoothly interpolates between a random graph to a lattice. Their model demonstrated that with the addition of only a small number of longrange links, a regular graph, in which the diameter is proportional to the size of the network, can be transformed into a "small world" in which the average number of edges between any two vertices is very small (mathematically, it should grow as the logarithm of the size of the network), while the clustering coefficient stays large. It is known that a wide variety of abstract graphs exhibit the smallworld property, e.g., random graphs and scalefree networks. Further, real world networks such as the World Wide Web and the metabolic network also exhibit this property.
In the scientific literature on networks, there is some ambiguity associated with the term "small world." In addition to referring to the size of the diameter of the network, it can also refer to the cooccurrence of a small diameter and a high clustering coefficient. The clustering coefficient is a metric that represents the density of triangles in the network. For instance, sparse random graphs have a vanishingly small clustering coefficient while real world networks often have a coefficient significantly larger. Scientists point to this difference as suggesting that edges are correlated in real world networks.
A framework for studying interactions between networks was recently established. Due to interdependencies such systems become significantly more vulnerable, with the appearance of cascading failures and a first order percolation transition.
Researchers and scientists
(with papers on complex networks cited at least 100 times)
 Réka Albert
 Luis Amaral
 Alex Arenas
 AlbertLászló Barabási
 Alain Barrat
 Marc Barthelemy
 Carl Bergstrom
 Stefano Boccaletti
 Guido Caldarelli
 Sergey Dorogovtsev
 Roger Guimerà
 Shlomo Havlin
 Jon Kleinberg
 José Mendes
 Yamir Moreno
 Adilson E. Motter
 Mark Newman
 Sidney Redner
 Martin Rosvall
 Kim Sneppen
 H. Eugene Stanley
 Steven Strogatz
 Alessandro Vespignani
 Duncan J. Watts
 YiCheng Zhang
See also
 Complex Systems
 Complexity Science
 Dynamic Network Analysis
 Network theory
 Network science
 Percolation theory
 Random graph
Books
 AlbertLászló Barabási, Linked: How Everything is Connected to Everything Else, 2004, ISBN 0452284392
 Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Dynamical processes on complex networks, Cambridge University Press, 2008, ISBN 9780521879507
 Stefan Bornholdt (Editor) and Heinz Georg Schuster (Editor), Handbook of Graphs and Networks: From the Genome to the Internet, 2003, ISBN 3527403361
 Guido Caldarelli, ScaleFree Networks Oxford University Press, 2007, ISBN 0199211517
 Reuven Cohen and Shlomo Havlin, Complex Networks: Structure, Robustness and Function, Cambridge University Press, 2010, ISBN 9780521841566
 S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0198515901
 Mark Newman, Networks: An Introduction, Oxford University Press, 2010, ISBN 9780199206650
 Mark Newman, AlbertLászló Barabási, and Duncan J. Watts, The Structure and Dynamics of Networks, Princeton University Press, Princeton, 2006, ISBN 9780691113579
 R. PastorSatorras and A. Vespignani, Evolution and Structure of the Internet: A statistical physics approach, Cambridge University Press, 2004, ISBN 0521826985
 Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, 2003, ISBN 0393041425
 Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, Princeton University Press, 2003, ISBN 0691117047
References
 ^ A Barabasi, E. Bonabeau (05 2003). "ScaleFree Networks". Scientific American: 50–59.
 ^ ^{a} ^{b} S. H. Strogatz, D. J. Watts (1998). "Collective dynamics of 'smallworld' networks". Nature 393: 440–442. doi:10.1038/30918.
 ^ R. Cohen, S. Havlin (2003). "Scalefree networks are ultrasmall". Phys. Rev. Lett 90: 058701. http://havlin.biu.ac.il/Publications.php?keyword=Scalefree+networks+are+ultrasmall&year=*&match=all.
 D. J. Watts and S. H. Strogatz., Collective dynamics of 'smallworld' networks, Nature Vol 393 (1998) 440442
 S. H. Strogatz, Exploring Complex Networks, Nature Vol 410 (2001) 268276
 R. Albert and A.L. Barabási, "Statistical mechanics of complex networks" Reviews of Modern Physics 74, (2002) 47
 S. N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks, Adv. Phys. 51, 1079 (2002)
 M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167256 (2003)
 A. Barabasi and E. Bonabeau, ScaleFree Networks, Scientific American, (May 2003), 5059
 S. Boccaletti et al., Complex Networks: Structure and Dynamics, Phys. Rep., 424 (2006), 175308.
 S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys. 80, 1275, (2008)
 J. Kim, T. Wilhelm, "What is a complex graph?" Physica A 387, 2637 (2008).
 R. Cohen, K. Erez, D. benAvraham, S. Havlin, "Resilience of the Internet to random breakdown" Phys. Rev. Lett. 85, 4626 (2000).
 R. Cohen, K. Erez, D. benAvraham, S. Havlin, "Breakdown of the Internet under intentional attack" Phys. Rev. Lett. 86, 3682 (2001)
 R. Cohen, S. Havlin, "Scalefree networks are ultrasmall" Phys. Rev. Lett. 90, 058701 (2003)
 A. E. Motter, "Cascade control and defense in complex networks" Phys. Rev. Lett. 93, 098701 (2004)
 S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, S. Havlin, "Catastrophic cascade of failures in interdependent networks" Nature 465, 08932 (2010)
External links
 imGraph Free Excel addin for drawing graphs.
 Network Science — United States Military Academy  Network Science Center
 Resources in Complex Networks — University of São Paulo  Institute of Physics at São Carlos
 CxNets — Complex Networks Collaboratory
 Networks Wiki
 GNET — Group of Complex Systems & Random Networks
 UCLA Human Complex Systems Program
 New England Complex Systems Institute
 Santa Fe Institute Networks Group
 Barabasi Networks Group
 Cosin Project Codes, Papers and Data on Complex Networks
 Complex network on arxiv.org
 [1] — Anna Nagurney's Virtual Center for Supernetworks
 BIOREL resource for quantitative estimation of the network bias in relation to external information
 Complexity Virtual Laboratory (VLAB)
 complexnetworks.fr — French computer science research group on networks
 Video Lectures on complex networks by Prof. Shlomo Havlin
 A short course on complex networks by Prof. Shlomo Havlin
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Complex network zeta function — Different definitions have been given for the dimension of a complex network or graph. For example, metric dimension is defined in terms of the resolving set for a graph. Dimension has also been defined based on the box covering method applied to … Wikipedia
Network science — is a new and emerging scientific discipline that examines the interconnections among diverse physical or engineered networks, information networks, biological networks, cognitive and semantic networks, and social networks. This field of science… … Wikipedia
Network complexity — is the number of nodes and alternative paths that exist within a computer network, as well as the variety of communication media, communications equipment, protocols, and hardware and software platforms found in the network. Simple network: A… … Wikipedia
Network — and networking may refer to: Contents 1 Mathematics 2 Electric, electronic, biological, and biosocial 3 Proper nouns (names) 4 See also … Wikipedia
Network theory — For network theory of the regulation of the adaptive immune system see Immune network theory For the sociological theory, see Social network Network theory is an area of computer science and network science and part of graph theory. It has… … Wikipedia
Complex system — This article largely discusses complex systems as a subject of mathematics and the attempts to emulate physical complex systems with emergent properties. For other scientific and professional disciplines addressing complexity in their fields see… … Wikipedia
Network controllability — Controlling a simple network. Network Controllability concerns the controllability a network. Controllability describes our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable… … Wikipedia
Network Science — Science des réseaux La Science des Réseaux, ou Network Science, est une discipline scientifique émergente qui se donne pour objet l étude des relations, liens et interconnexions entre les choses, et non les choses en elles mêmes. Champ… … Wikipédia en Français
Network science — Science des réseaux La Science des Réseaux, ou Network Science, est une discipline scientifique émergente qui se donne pour objet l étude des relations, liens et interconnexions entre les choses, et non les choses en elles mêmes. Champ… … Wikipédia en Français
complex — 1 adjective 1 consisting of many different parts or processes that are closely connected: There is a complex network of roads round the city.  Photosynthesis is a highly complex process. 2 difficult to understand or deal with: Mental illness is… … Longman dictionary of contemporary English