In the context of Network theory, the term "complex network" refers to a network (graph) that has certain non-trivial topological features that do not occur in simple networks. Network theory or diktyology is a branch of applied mathematics and physics, with the same general subject matter as graph theory. ... In Graph theory, a digraph with weighted edges is called a network. ... Topology (Greek topos = place and logos = word) is a branch of mathematics concerned with the study of topological spaces. ...

Most social, biological, and technological networks (as well as certain network-driven phenomena) can be considered complex by virtue of non-trivial topological structure (see e.g., social network, computer network, neural network, epidemiology). Such non-trivial features include: a heavy-tail in the degree distribution; a high clustering coefficient; assortativity or disassortativity among vertices; community structure at many scales; and evidence of a hierarchical structure. Social interactions and their consequences are the subject of sociology. ... Biology studies the variety of life (clockwise from top-left) E. coli, tree fern, gazelle, Goliath beetle Biology is the science of life (from the Greek words bios = life and logos = word). ... Technology (Gr. ... // Look up network in Wiktionary, the free dictionary. ... A social network is a social structure made of nodes which are generally individuals or organizations. ... A computer network is a system for communication between computers. ... In cognitive neuroscience, a neural network (also known as a neuronal network or biological neural network to distinguish from artificial neural networks) is a population of interconnected neurons. ... Epidemiology is the scientific study of factors affecting the health and illness of populations, and serves as the foundation and logic of interventions made in the interest of public health and preventive medicine. ... In the mathematical field of graph theory the degree distribution of a graph is a function describing the total number of vertices in a graph with a given degree (number of connections to other vertices). ... Example clustering coefficient on an undirected graph for the shaded node i. ... Assortativity refers to a preference for a networks nodes to attach to others that are similar or different in some way. ... Clustering can refer to Computer clustering - (in Computer science) the connection of many low-cost computers using special hardware and software such that they can be used as one larger computer. ... A hierarchy (in Greek: , it is derived from -hieros, sacred, and -arkho, rule) is a system of ranking and organizing things or people, where each element of the system (except for the top element) is subordinate to a single other element. ...

In contrast, simple networks have none of these properties, and are typically represented by graphs such as a lattice or a random graph, which exhibit a high similarity no matter what part is examined. The ordinary meaning of lattice is the basis for several technical usages A cherry lattice pastry A mathematical lattice that is a type of partially ordered set. ... In mathematics, a random graph is a graph that is generated by some random process. ... Several equivalence relations in mathematics are called similarity. ...

The two most well-known examples of complex networks are those of scale-free networks and small-world networks. Both are specific models of complex networks discovered in the late 1990s by physicists, and are canonical case-studies in the field. However, as network science has continued to grow in importance and popularity, other models of complex networks have been developed. Indeed, the field continues to develop at a brisk pace, and has brought together researchers from a variety of fields. Network science, and the study and use of complex networks in particular, shows some promise of helping to unravel the structure of the genetic regulatory network, to explain how to build robust and scalable communication networks both wired and wireless, to aid in the development of more efficient vaccination strategies, and to produce a near endless stream of attractive pictures. A scale-free network is a specific kind of complex network in which the distribution of connectivity is extremely uneven. ... A small-world network is a specific kind of network (to be more precise a special kind of a complex network) in which the distribution of connectivity is not confined to a certain scale, and where every node can be reached from every other by a small number of hops...

Scale-free networks

A network is named scale-free 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 well-defined 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 random graph and hypercubes. In a network with a scale-free 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, then it wouldn't be a scale-free distribution! A scale-free network is a specific kind of complex network in which the distribution of connectivity is extremely uneven. ... In the mathematical field of graph theory the degree distribution of a graph is a function describing the total number of vertices in a graph with a given degree (number of connections to other vertices). ... See Also: Watt In physics, a power law relationship between two scalar quantities x and y is any such that the relationship can be written as where a (the constant of proportionality) and k (the exponent of the power law) are constants. ... Paul ErdÅ‘s also Pál ErdÅ‘s, in English Paul Erdos or Paul Erdös, (March 26, 1913 – September 20, 1996) was an immensely prolific (and famously eccentric) Hungarian mathematician who, with hundreds of collaborators, worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set... Alfréd Rényi (March 20, 1921 – February 1, 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. ... In mathematics, a random graph is a graph that is generated by some random process. ... This article refers to the mathematical concept. ...

Interest in scale-free networks began in the late 1990s with the apparent discovery of a power-law degree distribution in many real world networks such as the World Wide Web, the network of Autonomous systems (ASs), the 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 power-law 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 power-law degree distributions. A scale-free network is a specific kind of complex network that has attracted attention since many real-world networks fall into this category. ... WWWs historical logo designed by Robert Cailliau The World Wide Web (WWW or simply the Web) is a system of interlinked, hypertext documents that runs over the Internet. ... In the Internet, an autonomous system (AS) is a collection of IP networks and routers, under the control of one or more entities, that presents a common routing policy to the Internet. ... In probability theory and statistics, the Poisson distribution is a discrete probability distribution. ... Simon is a common name. ... Preferential attachment is a mechanism or algorithm for growing scale-free networks, i. ... Albert-Laszlo Barabasi (Barabási Albert-László) (born March 30, 1967) is a Romanian-born American physicist, the Emil T. Hofmann professor of physics at the University of Notre Dame. ...

Networks with a power-law 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). Giant component is a network theory term referring to a connected subgraph that contains a majority of the entire graphs nodes. ... In chemistry and other physical sciences, percolation is a type of filtering. ... In probability theory, a branching process is a Markov process that models a population in which each individual in generation n produces some random number of individuals in generation n + 1, according to a fixed probability distribution that does not vary from individual to individual. ...

Small-world networks

A network is called a small-world network by analogy with the small-world phenomenon (popularly known as six degrees of separation). The small world hypothesis, 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 small-world 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 long-range 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 small-world property, e.g., random graphs and scale-free networks. Further, real world networks such as the World Wide Web and the metabolic network also exhibit this property. In mathematics and physics, a small-world network is a class of random graphs where most nodes are also neighbors of one another, but every node can be reached from every other by a small number of hops or steps. ... The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. ... This article or section is in need of attention from an expert on the subject. ... Frigyes Karinthy (1887 in Budapest - 1938 in Siófok) was a Hungarian author, playwright, poet, journalist and translator. ... Stanley Milgram Stanley Milgram (August 15, 1933 – December 20, 1984) was a psychologist at Yale University, Harvard University and the City University of New York. ... Duncan J. Watts is an associate professor of sociology at Columbia University and author of the book Six Degrees: The Science of a Connected Age (Norton, 2003). ... Steven H. Strogatz is Professor of theoretical and applied mechanics at Cornell University. ... In mathematics, a random graph is a graph that is generated by some random process. ... The ordinary meaning of lattice is the basis for several technical usages A cherry lattice pastry A mathematical lattice that is a type of partially ordered set. ... In mathematics, a random graph is a graph that is generated by some random process. ... A scale-free network is a specific kind of complex network that has attracted attention since many real-world networks fall into this category. ... WWWs historical logo designed by Robert Cailliau The World Wide Web (WWW or simply the Web) is a system of interlinked, hypertext documents that runs over the Internet. ...

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 co-occurrence 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. Example clustering coefficient on an undirected graph for the shaded node i. ...

Researchers and scientists

• L.A.N. Amaral
• Albert-László Barabási
• Alain Barrat
• Marc Barthelemy
• Guido Caldarelli
• Sergey Dorogovtsev
• Shlomo Havlin
• Matthieu Latapy
• Neo Martinez
• Jose Fernando F. Mendes
• Mark Newman
• Romualdo Pastor-Satorras
• Sidney Redner
• Kim Sneppen
• Ricard V. Solé
• Steven Strogatz
• Alessandro Vespignani
• Duncan J. Watts

External links

• cxnets - Complex Networks Collaboratory
• Networks Wiki
• GNET - Group of Complex Systems & Random Networks
• UCLA Human Complex Systems Program
• BIOREL resource for quantitative estimation of the network bias in relation to external information
• New England Complex Systems Institute
• Santa Fe Institute Networks Group
• Barabasi Networks Group
• Scale-Free and Small-World Networks
• VisualComplexity.com - Gallery of network visualizations
• Resources in Complex Networks - Resources in Complex Networks
• Cosin Project Codes, Papers and Data on Complex Networks
• Complex network on arxiv.org

References

• M. E. J. Newman The structure and function of complex networks (Review article)
• A. Barabasi and E. Bonabeau, Scale-Free Networks, Scientific American, (May 2003), 50-59
• S. H. Strogatz, Exploring Complex Networks, Nature Vol 410 (2001) 268-276
• D. J. Watts and S. H. Strogatz., Collective dynamics of 'small-world' networks, Nature Vol 393 (1998) 440-442
• S. N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks, Adv. Phys. 51, 1079 (2002)

Books

• Barabási, Albert-László Linked: How Everything is Connected to Everything Else, 2004 ISBN 0-452-28439-2
• S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0-19-851590-1
• R. Pastor-Satorras and A. Vespignani, "Evolution and Structure of the Internet: a statistical physics approach", Cambridge University Press, 2004, ISBN 0-521-82698-5
• Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, 2003, ISBN 0-393-04142-5
• Duncan J. Watts, Small Worlds : The Dynamics of Networks between Order and Randomness, Princeton University Press, 2003, ISBN 0-691-11704-7
• Stefan Bornholdt (Editor) and Heinz Georg Schuster (Editor), Handbook of Graphs and Networks: From the Genome to the Internet, ISBN 3-527-40336-1.