Statistical mechanics of complex networks
By Réka Albert, Albert-László Barabási. 2001
20,002 citations recorded by the source corpus.
The emergence of order in natural systems is a constant source of inspiration for both physical and biological sciences. While the spatial order characterizing for example the crystals has been the basis of many advances in contemporary physics, most complex systems in nature do not offer such high degree of order. Many of these systems form complex networks whose nodes are the elements of the system and edges represent the interactions between them. Traditionally complex networks have been described by the random graph theory founded in 1959 by Paul Erdohs and Alfred Renyi. One of the defining features of random graphs is that they are statistically homogeneous, and their degree distribution (characterizing the spread in the number of edges starting from a node) is a Poisson distribution. In contrast, recent empirical studies, including the work of our group, indicate that the topology of real networks is much richer than that of random graphs. In particular, the degree distribution of real networks is a power-law, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network. The scale-free topology of real networks has very important consequences on their functioning. For example, we have discovered that scale-free networks are extremely resilient to the random disruption of their nodes. On the other hand, the selective removal of the nodes with highest degree induces a rapid breakdown of the network to isolated subparts that cannot communicate with each other. The non-trivial scaling of the degree distribution of real networks is also an indication of their assembly and evolution. Indeed, our modeling studies have shown us that there are general principles governing the evolution of networks. Most networks start from a small seed and grow by the addition of new nodes which attach to the nodes already in the system. This process obeys preferential attachment: the new nodes are more likely to connect to nodes with already high degree. We have proposed a simple model based on these two principles wich was able to reproduce the power-law degree distribution of real networks. Perhaps even more importantly, this model paved the way to a new paradigm of network modeling, trying to capture the evolution of networks, not just their static topology.
Subfields: Experimental and Cognitive Psychology, Statistical and Nonlinear Physics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Experimental and Cognitive Psychology
- D. Bassett
- E. Bullmore
- Olaf Sporns
- Mark Newman
- Cornelis J. Stam
- Santo Fortunato
- Alex Fornito
- Andrew Zalesky
In Statistical and Nonlinear Physics
- Mark Newman
- Santo Fortunato
- Jure Leskovec
- Olaf Sporns
- M. A. Porter
- Albert-László Barabási
- Alex Arenas
- Remco van der Hofstad
Citations in the corpus
- Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “For the MVC and MAXCUT problems, we generate Erd˝os-Renyi (ER) [11] and Barabasi-Albert (BA) [1] graphs which have been used to model many real-world networks.”
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models (2018, methodology): “Following Li et al. 2018 we compare against the Erd˝os-R´enyi model (E-R) (Erd˝os & R´enyi, 1959) and the Barab´asi-Albert (B-A) model (Albert & Barab´asi, 2002).”
- Exploring Randomly Wired Neural Networks for Image Recognition (2019, methodology): “To reduce bias from us—the authors of this paper—on the generators, we use three classical families of random graph models in graph theory [52]: the Erdős-Rényi (ER) [7], Barabási-Albert (BA) [1], and Watts-Strogatz (WS) [51] models.”
- Community detection in graphs (2009, methodology): “The need to deal with such a large number of units has produced a deep change in the way graphs are approached (Albert and Barabási, 2002; Barrat et al., 2008; Boccaletti et al., 2006; Mendes and Dorogovtsev, 2003; Newman, 2003; Pastor-Satorras and Vespignani, 2004).”
- Random graphs (2006, background): “The small world model [4] of Watts and strogatz(1998) and the preferential attachment model [5] of Barabási and Albert (1999) [1] have led to an explosion of research [8].”
- Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, background): “…applications, such as drug design (Du-venaud et al., 2015; Gómez-Bombarelli et al., 2018; Li et al., 2018a), creating computation graphs for architecture search (Xie et al., 2019), as well as research in network science (Watts and Strogatz, 1998; Albert and Barabási, 2002; Leskovec et al., 2010).”
- Graph-based Neural Multi-Document Summarization (2017, methodology): “Graph-based MDS models have traditionally employed surface level (Erkan and Radev, 2004; Mi-halcea and Tarau, 2005; Wan and Yang, 2006) or deep level (Pardo et al., 2006; Antiqueira et al., 2009) approaches based on topological features and the number of nodes (Albert and Barab´asi, 2002).”
- Communication Efficiency and Congestion of Signal Traffic in Large-Scale Brain Networks (2014, neutral): “The structural topology of cortical networks can be represented and formally studied using the graph model [1–3], whereby the brain is spatially parcellated into a set of grey matter nodes interconnected by a set of white matter edges [4,5].”
- Structural reducibility of multilayer networks (2014, methodology): “For the sake of simplicity, and without loss of generality, we assume that the reduced configuration C′ is obtained by aggregating layers C [1] and C [2] into a new layer C [1] +C .”
- The Structure of Social Networks (2006, methodology): “However, over the past 10 years it has been shown that many complex systems exhibit similar topological features in the way their underlying elements are arranged (Albert and Barabási 2002).”
- Default Contagion in Financial Networks (2016, methodology): “Moreover, following [1] and [2], some considerations about systemic risk and risk contagion in banking network are discussed; in Section III, the major mathematical results related to the Erdős-Rény model, the Barabási-Albert model, and those concerning the evolving network theory, are collected, ma”
- A Survey of Statistical Network Models (2009, background): “The preferential attachment model of Barabási and Albert results in a network with a power law degree distribution whose exponent is empirically determined to be γBA = 42 2.9 ± 0.1, whereas the Erdös-Rényi-Gilbert model has a Poisson degree distribution.”
- Epidemics and immunization in scale‐free networks (2002, background): “In this perspective scale-free (SF) networks [4, 5, 6] represents a very interesting cases since they exhibit a power-law connectivity distribution for the probability P ( k ) that a node of the network has k connections to other nodes.”