European Survey of Information Society


Home   Structure of ESIS   Background to the ESIS Project   Project Management Contacts   Lead and local Contractors   History of ESIS
Complex network

In the context of network theory, a complex network is a graph (network) with non-trivial topological features´features that do not occur in simple networks such as lattices or random graphs but often occur in graphs modelling of real systems. The study of complex networks is a young and active area of scientific research (since 2000) inspired largely by the empirical study of real-world networks such as computer networks, technological networks, brain networks and social networks.
Two well-known and much studied classes of complex networks are scale-free networks and small-world networks, whose discovery and definition are canonical case-studies in the field. Both are characterized by specific structural features—power-law 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, electric power systems, biology, climate, computer science, sociology, epidemiology, and others. Ideas from network science and engineering have been applied to the analysis of metabolic and genetic regulatory networks; the study of ecosystem stability and robustness; clinical science; the modeling and design of scalable communication networks such as the generation and visualization of complex wireless networks; the development of vaccination strategies for the control of disease; and a broad range of other practical issues. Research on networks are regularly published in the most visible scientific journals and obtain vigorous funding in many countries. Network theory was found recently useful to identify bottlenecks in city traffic. Network science is the topic of many conferences in a variety of different fields, and has been the subject of numerous books both for the lay person and for the expert.
Interest in scale-free networks began in the late 1990s with the reporting of discoveries of power-law degree distributions in real world networks such as the World Wide Web, the network of Autonomous systems (ASs), some networks of Internet routers, protein interaction networks, email networks, etc. Most of these reported "power laws" fail when challenged with rigorous statistical testing, but the more general idea of heavy-tailed degree distributions—which many of these networks do genuinely exhibit (before finite-size effects occur) -- are very different from what one would expect if edges existed independently and at random (i.e., if they followed a Poisson distribution). 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 A. Simon, the Matthew effect, cumulative advantage and, preferential attachment by Barabási and Albert for power-law degree distributions. Recently, Hyperbolic Geometric Graphs have been suggested as yet another way of constructing scale-free networks.
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.