iPedia Free Information Center

Information about Complex Network

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.

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.

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 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 put forward 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.

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!

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), 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 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.

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).

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, 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 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 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.

Researchers and scientists

(with papers on complex networks cited at least 100 times)

External links

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)
  • S. Boccaletti et al., Complex Networks: Structure and Dynamics, Phys. Rep., 424 (2006), 175-308.

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.
Network theory is a subject within applied mathematics and physics, and coincides with graph theory. It has application in a varied range of disciplines including computer science, biology, economics, and sociology.
..... Click the link for more information.
In Graph theory, a network is a digraph with weighted edges. These networks have become an especially useful concept in analysing the interaction between biology and mathematics.
..... Click the link for more information.
graph is the basic object of study in graph theory. Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges.
..... Click the link for more information.
Topology (Greek topos, "place," and logos, "study") is a branch of mathematics that is an extension of geometry. Topology begins with a consideration of the nature of space, investigating both its fine structure and its global structure.
..... Click the link for more information.
Sociology (from Latin: socitus, "companion"; and the suffix -ology, "the study of", from Greek λόγος, lógos, "knowledge") is the systematic and scientific study of society and societal behavior.
..... Click the link for more information.
Biological may refer to:
  • Biology, the study of life
  • Biological tissue
  • Biological process
  • Organism, a biological entity
  • Life, the characteristic state of organisms
  • Consanguinity, being descended from the same ancestor
Materials and substances
..... Click the link for more information.
Editing of this page by unregistered or newly registered users is currently disabled due to vandalism.
If you are prevented from editing this page, and you wish to make a change, please discuss changes on the talk page, request unprotection, log in, or .
..... Click the link for more information.
In general, the term network can refer to any interconnected group or system. Several different types of networks exist, including:

Human network

  • Business network
  • Economic network
  • Entrepreneurial network
  • Old boy network
  • Sexual network

..... Click the link for more information.
social network is a social structure made of nodes (which are generally individuals or organizations) that are tied by one or more specific types of interdependency, such as values, visions, idea, financial exchange, friends, kinship, dislike, conflict, trade, web links, sexual
..... Click the link for more information.
as a college campus, industrial complex, or a military base. A CAN, may be considered a type of MAN (metropolitan area network), but is generally limited to an area that is smaller than a typical MAN.
..... Click the link for more information.
neural network describes a population of physically interconnected neurons or a group of disparate neurons whose inputs or signalling targets define a recognizable circuit. Communication between neurons often involves an electrochemical process.
..... Click the link for more information.
Epidemiology is the 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.
..... Click the link for more information.
In graph theory, degree distribution gives the probability distribution of degrees in a network. Its use originates from the study of random graph by Paul Erdős and Alfréd Rényi [1]
..... Click the link for more information.
clustering coefficient[1] graph measure to determine whether or not a graph is a small-world network.

First, let us define a graph in terms of a set of vertices and a set of edges , where denotes an edge between vertices and .
..... Click the link for more information.
Assortativity refers to a preference for a network's nodes to attach to others that are similar or different in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree [1].
..... Click the link for more information.
Clustering can refer to
  • Computer clustering - the connection of many low-cost computers to be used as one larger computer.
  • In computer science, the undesirable, contiguous grouping of elements in a hash table.

..... Click the link for more information.
hierarchy (in Greek: Ἱεραρχία, derived from ἱερός — hieros, 'sacred', and
..... Click the link for more information.
Lattice may refer to:
  • Latticework an ornamental and/or structural criss-crossed framework, an arrangement of crossing laths or other thin strips of material
  • Kagome lattice

..... Click the link for more information.
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.
..... Click the link for more information.
Similarity is some degree of symmetry in either analogy and resemblance between two or more concepts or objects. The notion of similarity rests either on exact or approximate repetitions of patterns in the compared items.
..... Click the link for more information.
A scale-free network is a noteworthy kind of complex network because many "real-world networks" fall into this category. For purposes of this article, "real-world" refers to any of various observable phenomena that exhibit network theoretic characteristics (see e.g.
..... Click the link for more information.
In mathematics and physics, a small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps.
..... Click the link for more information.
A power law is any polynomial relationship that exhibits the property of scale invariance. The most common power laws relate two variables and have the form



where and are constants, and is of .
..... Click the link for more information.
hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, at right angles to each
..... Click the link for more information.
World Wide Web (commonly shortened to the Web) is a system of interlinked, hypertext documents accessed via the Internet. With a web browser, a user views web pages that may contain text, images, videos, and other multimedia and navigates between them using hyperlinks.
..... Click the link for more information.
In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. See RFC 1930 for additional detail on this updated definition.
..... Click the link for more information.
Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate, and are independent of the time since the last event.
..... Click the link for more information.
Simon is a common name, from Hebrew שִׁמְעוֹן Šimʿon, meaning "he [God] has heard" (compare Ishmael).
..... Click the link for more information.
The Barabási-Albert (BA) model is an algorithm for generating scale-free random graphs. Scale-free networks are very common, and can be found e.g. in social networks, the world-wide web, or networks of proteins reacting with each other in the cell.
..... Click the link for more information.
Albert-László Barabási (born March 30, 1967) is a Romanian-born American scientist. He is the former Emil T. Hofmann professor at the University of Notre Dame and current Distinguished Professor and Director of Northeastern University's Center for Network Science, and is noted for
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter