Complex network

from Wikipedia, the free encyclopedia

In the context of network research or graph theory, a complex network is a network ( graph ) with non-trivial topological properties, i. H. with properties that do not appear in simple networks such as grids or random graphs. The investigation of complex networks is a young and active area in current scientific research, which is mainly inspired by empirical studies of real networks such as computer networks or social networks .

definition

Random vs. scale-free network

Many social, biological and computer networks have essential non-trivial topological properties, i.e. the connections ( edges ) between their elements ( nodes ) are neither purely regular nor purely random. Instead, such networks are characterized by special distributions in the occurrence of its elements ( grade distribution , English: degree distribution ), by a high cluster coefficient , a particular community structure ( community structure ) or a strong hierarchical structure . Many previously studied mathematical models of networks or graphs, however, do not show any of these properties.

Two typical classes of complex networks have been studied intensively in the past: scale-free networks , and the so-called small world networks, the discovery and definition of which are canonical case studies in this area.

In scale-free networks , the nodes do not have a typical number of connections, but the distribution of the connections per node follows a power law .

In small-world networks, however, there are many very short connections between all elements and they have a high cluster coefficient . Due to the rapid progress in current research on complex networks, other important new aspects and findings have also been found, such as networks that change over time: These networks can change over time (so-called 'evolving networks'), whereby nodes and edges with the Time can arise or even disappear. This creates a complex dynamic that can lead to self-organization and stable states. Another important aspect here is the occurrence of synchronization .

Research into complex networks is a lively and very topical field of research and combines various disciplines such as mathematics, physics, biology, climate research, computer science, sociology, epidemiology and many more. The concepts from network theory have found their way into the analysis of metabolic and regulatory networks, into the design of robust and scalable communication networks, into the development of vaccination strategies or into the analysis of climate phenomena. Corresponding research results are regularly published in some of the most famous scientific journals, are the subject of special conferences and have also led to some popular scientific articles and books.

From researching complex networks, important statements can be learned about information and material flows and their optimization as well as about critical behavior and stability of the overall system. As an example, reference is made to the exchange of banknotes , which Dirk Brockmann investigated with the help of the theory of complex networks, which received worldwide attention.

Analytical methods

To a network resp. To analyze a graph, the importance of the nodes is of interest in many cases. In addition to naive metrics such as analysis of the nodal degree , more complex methods have also been proposed. A well-known example is PageRank , the method that forms the basis for modern search engines. It is closely related to the eigenvector - centrality .

Further measures for graphs are:

  • Degree ( degree centrality ) - An early, simple measure to measure the centrality of a node is to examine the set of all incident edges.
  • Close ( close centrality ) - The distance of a node to all other is the basis for this measurement. This allows nodes to be identified (automatically) which are located in the "center" of a network. Normally, the reciprocal value of the sum of all distances to other nodes is taken in order to achieve that the higher the perceived centrality of the node, the higher the value.
Betweenness graph
  • Betweenness centrality ( betweenness centrality ) - A node that has a high betweenness value if this node part of a high number of shortest paths and the respective pairs have few other shortest ways in which the node is not included. For each pair of nodes, therefore, the fraction of shortest paths between them that contain v is calculated. These proportions are added up for all pairs of nodes in order to calculate the betweenness centrality of v.
  • Eigenvector centrality - According to the eigenvector centrality method, the more important its neighboring nodes are, the more important a node is.

See also

literature

  • Füllsack, Manfred (Ed.): Networking Networks. Origins, Applications, Experiments. Proceedings of the multi-disciplinary network for the Simulation of Complex Systems - Research in the Von-Neumann-Galaxy. Turia + Kant: Vienna / Berlin 2014, ISBN 978-3-85132-725-0 .

Individual evidence

  1. ^ A b S. H. Strogatz : Exploring Complex Networks . In: Nature . 410, 2001, pp. 268-276.
  2. ↑ R. Albert, A.-L. Barabási : Statistical mechanics of complex networks . In: Reviews of Modern Physics . 74, 2002, p. 47.
  3. ^ A b M. EJ Newman: The structure and function of complex networks . In: SIAM Review . 45, 2003, pp. 167-256.
  4. ↑ a b p Boccaletti et al .: Complex Networks: Structure and Dynamics . In: Physics Reports . 424, 2006, pp. 175-308.
  5. ↑ A.-L. Barabási , E. Bonabeau: Scale-Free Networks . In: Scientific American . May, 2003, pp. 50-59.
  6. ^ A b D. J. Watts , SH Strogatz : Collective dynamics of 'small-world' networks . In: Nature . 393, 1998, pp. 440-442.
  7. ↑ SN Dorogovtsev, JFF Mendes: Evolution of Networks . In: Advances in Physics . 51, 2002, p. 1079.
  8. ↑ R. Albert, A.-L. Barabási : Topology of evolving networks: local events and universality . In: Physical Review Letters . 85, 2000, pp. 5234-5237.
  9. ^ A. Arenas, A. Díaz-Guilera, J. Kurths , Y. Moreno, C. Zhou: Synchronization in complex networks . In: Physics Reports . 469, 2008, pp. 93-153.
  10. ↑ a b Brockmann et al .: The scaling laws of human travel . In: Nature . 439, 2006, pp. 462-465.
  11. ^ DJ Watts : Six Degrees: The Science of a Connected Age . WW Norton & Company, 2003, ISBN 0-393-04142-5 .
  12. ↑ A.-L. Barabási , Eric Bonabeau: Scale Free Networks . In: Spectrum of Science . July, 2004, pp. 62-69.
  13. ↑ Malte Landwehr: Graph centrality in author-quotation networks. Graph centralities as alternatives to h-index and PageRank in the evaluation of scientists . GRIN Verlag, Munich 2011, ISBN 978-3-656-00775-3 , urn : nbn: de: 101: 1-201109192114 .
  14. ^ Money-Circulation Science (English) , The New York Times Magazine - The 6th Annual Year in Ideas. Retrieved December 10, 2006.