Foundations of complex networks
M. Ángeles Serrano and Marián Boguñá
A wide class of real systems of many interacting elements can be mapped into graphs or networks. Under this approach, vertices or nodes of the network represent the elements of the system whereas edges or links among them stand for interactions between different elements. This mapping has triggered a huge number of works and a surge of interest in the field of complex networks that has lead to a general framework within which to analyze their topology as well as the dynamical processes running on top of them.
In many cases, these dynamical processes are directly related to functionality and involve some kind of transport or traffic flow. Furthermore, the very existence of those networks could be naturally explained as a direct consequence of the communication need among its constituents. The Internet or the World Wide Web are clear examples. In order to preserve functionality, networks characterized by transport processes must be connected, that is, a path must exist between any pair of nodes, or, at least, there must exist a macroscopic portion of vertices --or giant component-- able to communicate. In this context, percolation theory appears as an indispensable tool to analyze the conditions under which such connected structures emerge in large networks.
Our research in this field is focused towards the study of structural properties of networks and new percolation phenomena, such as percolation in random directed networks with one and two points degree correlations, bidirectional connections and clustering. These are ubiquitous properties in the networks of the real life which have strong implications in their percolation properties.
Relevant references
Benchmarking seeding strategies for spreading processes in social networks: an interplay between influencers, topologies and sizes
Montes, F.; Jaramillo, A.M.; Meisel, J.D.; Diaz-Guilera, A.; Valdivia, J.A.; Sarmiento, O.L.; Zarama, R.
Scientific Reports
(2020)
abstract
The explosion of network science has permitted an understanding of how the structure of social networks affects the dynamics of social contagion. In community-based interventions with spill-over effects, identifying influential spreaders may be harnessed to increase the spreading efficiency of social contagion, in terms of time needed to spread all the largest connected component of the network. Several strategies have been proved to be efficient using only data and simulation-based models in specific network topologies without a consensus of an overall result. Hence, the purpose of this paper is to benchmark the spreading efficiency of seeding strategies related to network structural properties and sizes. We simulate spreading processes on empirical and simulated social networks within a wide range of densities, clustering coefficients, and sizes. We also propose three new decentralized seeding strategies that are structurally different from well-known strategies: community hubs, ambassadors, and random hubs. We observe that the efficiency ranking of strategies varies with the network structure. In general, for sparse networks with community structure, decentralized influencers are suitable for increasing the spreading efficiency. By contrast, when the networks are denser, centralized influencers outperform. These results provide a framework for selecting efficient strategies according to different contexts in which social networks emerge.
Assessing diversity in multiplex networks
Laura C. Carpi, Tiago A. Schieber, Panos M. Pardalos, Gemma Marfany, Cristina Masoller, Albert Díaz-Guilera and Martín G. Ravetti
Scientific Reports
(2019)
abstract
Diversity, understood as the variety of different elements or configurations that an extensive system has, is a crucial property that allows maintaining the system’s functionality in a changing environment, where failures, random events or malicious attacks are often unavoidable. Despite the relevance of preserving diversity in the context of ecology, biology, transport, finances, etc., the elements or configurations that more contribute to the diversity are often unknown, and thus, they can not be protected against failures or environmental crises. This is due to the fact that there is no generic framework that allows identifying which elements or configurations have crucial roles in preserving the diversity of the system. Existing methods treat the level of heterogeneity of a system as a measure of its diversity, being unsuitable when systems are composed of a large number of elements with different attributes and types of interactions. Besides, with limited resources, one needs to find the best preservation policy, i.e., one needs to solve an optimization problem. Here we aim to bridge this gap by developing a metric between labeled graphs to compute the diversity of the system, which allows identifying the most relevant components, based on their contribution to a global diversity value. The proposed framework is suitable for large multiplex structures, which are constituted by a set of elements represented as nodes, which have different types of interactions, represented as layers. The proposed method allows us to find, in a genetic network (HIV-1), the elements with the highest diversity values, while in a European airline network, we systematically identify the companies that maximize (and those that less compromise) the variety of options for routes connecting different airports.
A Complex Network Framework to Model Cognition: Unveiling Correlation Structures from Connectivity
Gemma Rosell-Tarragó, Emanuele Cozzo, Albert Díaz-Guilera
Complexity
(2018)
abstract
Several approaches to cognition and intelligence research rely on statistics-based model testing, namely, factor analysis. In the present work, we exploit the emerging dynamical system perspective putting the focus on the role of the network topology underlying the relationships between cognitive processes. We go through a couple of models of distinct cognitive phenomena and yet find the conditions for them to be mathematically equivalent. We find a nontrivial attractor of the system that corresponds to the exact definition of a well-known network centrality and hence stresses the interplay between the dynamics and the underlying network connectivity, showing that both of the two are relevant. Correlation matrices evince there must be a meaningful structure underlying real data. Nevertheless, the true architecture regarding the connectivity between cognitive processes is still a burning issue of research. Regardless of the network considered, it is always possible to recover a positive manifold of correlations. Furthermore, we show that different network topologies lead to different plausible statistical models concerning the correlation structure, ranging from one to multiple factor models and richer correlation structures.
Quantification of network structural dissimilarities
Tiago A. Schieber, Laura Carpi, Albert Díaz-Guilera, Panos M. Pardalos, Cristina Masoller & Martín G. Ravetti
Nature Communications
(2017)
abstract
Identifying and quantifying dissimilarities among graphs is a fundamental and challenging problem of practical importance in many fields of science. Current methods of network comparison are limited to extract only partial information or are computationally very demanding. Here we propose an efficient and precise measure for network comparison, which is based on quantifying differences among distance probability distributions extracted from the networks. Extensive experiments on synthetic and real-world networks show that this measure returns non-zero values only when the graphs are non-isomorphic. Most importantly, the measure proposed here can identify and quantify structural topological differences that have a practical impact on the information flow through the network, such as the presence or absence of critical links that connect or disconnect connected components.
Noise-induced polarization switching in complex networks
Jan O. Haerter, Albert Díaz-Guilera, and Maria Ángeles Serrano
Phys. Rev. E
(2017)
abstract
The combination of bistability and noise is ubiquitous in complex systems, from biology to social interactions, and has important implications for their functioning and resilience. Here we use a simple three-state dynamical process, in which nodes go from one pole to another through an intermediate state, to show that noise can induce polarization switching in bistable systems if dynamical correlations are significant. In large, fully connected networks, where dynamical correlations can be neglected, increasing noise yields a collapse of bistability to an unpolarized configuration where the three possible states of the nodes are equally likely. In contrast, increased noise induces abrupt and irreversible polarization switching in sparsely connected networks. In multiplexes, where each layer can have a different polarization tendency, one layer is dominant and progressively imposes its polarization state on the other, offsetting or promoting the ability of noise to switch its polarization. Overall, we show that the interplay of noise and dynamical correlations can yield discontinuous transitions between extremes, which cannot be explained by a simple mean-field description.
Stationary patterns in star networks of bistable units: Theory and application to chemical reactions
Nikos E. Kouvaris, Michael Sebek, Albert Iribarne, Albert Díaz-Guilera, and István Z. Kiss
Phys. Rev. E
(2017)
abstract
We present theoretical and experimental studies on pattern formation with bistable dynamical units coupled in a star network configuration. By applying a localized perturbation to the central or the peripheral elements, we demonstrate the subsequent spreading, pinning, or retraction of the activations; such analysis enables the characterization of the formation of stationary patterns of localized activity. The results are interpreted with a theoretical analysis of a simplified bistable reaction-diffusion model. Weak coupling results in trivial pinned states where the activation cannot propagate. At strong coupling, a uniform state is expected with active or inactive elements at small or large degree networks, respectively. A nontrivial stationary spatial pattern, corresponding to an activation pinning, is predicted to occur at an intermediate number of peripheral elements and at intermediate coupling strengths, where the central activation of the network is pinned, but the peripheral activation propagates toward the center. The results are confirmed in experiments with star networks of bistable electrochemical reactions. The experiments confirm the existence of the stationary spatial patterns and the dependence of coupling strength on the number of peripheral elements for transitions between pinned and retreating or spreading fronts in forced network configurations (where the central or periphery elements are forced to maintain their states).
Escaping the avalanche collapse in self-similar multiplexes
M. Angeles Serrano, Lubos Buzna, Marian Boguña,
NEW JOURNAL OF PHYSICS
(2015)
abstract
We deduce and discuss the implications of self-similarity for the robustness to failure of multiplexes, depending on interlayer degree correlations. First, we define self-similarity of multiplexes and we illustrate the concept in practice using the configuration model ensemble. Circumscribing robustness to survival of the mutually percolated state, we find a new explanation based on self-similarity both for the observed fragility of interconnected systems of networks and for their robustness to failure when interlayer degree correlations are present. Extending the self-similarity arguments, we show that interlayer degree correlations can change completely the global connectivity properties of self-similar multiplexes, so that they can even recover a zero percolation threshold and a continuous transition in the thermodynamic limit, qualitatively exhibiting thus the ordinary percolation properties of noninteracting networks. We confirm these results with numerical simulations.
Double Percolation Phase Transition in Clustered Complex Networks
Pol Colomer-de-Simon, Marian Boguña,
PHYSICAL REVIEW X
(2014)
abstract
The internal organization of complex networks often has striking consequences on either their response to external perturbations or on their dynamical properties. In addition to small-world and scale-free properties, clustering is the most common topological characteristic observed in many real networked systems. In this paper, we report an extensive numerical study on the effects of clustering on the structural properties of complex networks. Strong clustering in heterogeneous networks induces the emergence of a core-periphery organization that has a critical effect on the percolation properties of the networks. We observe a novel double phase transition with an intermediate phase in which only the core of the network is percolated and a final phase in which the periphery percolates regardless of the core. This result implies breaking of the same symmetry at two different values of the control parameter, in stark contrast to the modern theory of continuous phase transitions. Inspired by this core-periphery organization, we introduce a simple model that allows us to analytically prove that such an anomalous phase transition is, in fact, possible.
Deciphering the global organization of clustering in real complex networks
Pol Colomer-de-Simon, M. Angeles Serrano, G. Beiro, J. Ignacio Alvarez-Hamelin, Marian Boguña,
SCIENTIFIC REPORTS
(2013)
abstract
We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.
Clustering of random scale-free networks
Pol Colomer-de-Simon, Marian Boguña,
PHYSICAL REVIEW E
(2012)
abstract
We derive the finite-size dependence of the clustering coefficient of scale-free random graphs generated by the configuration model with degree distribution exponent 2 < gamma < 3. Degree heterogeneity increases the presence of triangles in the network up to levels that compare to those found in many real networks even for extremely large nets. We also find that for values of gamma approximate to 2, clustering is virtually size independent and, at the same time, becomes a de facto non-self-averaging topological property. This implies that a single-instance network is not representative of the ensemble even for very large network sizes.
Correlations in complex networks
M. Ángeles Serrano, M Boguñá, Romualdo Pastor-Satorras, Alessandro Vespignani
Structure and Dynamics of Complex Networks. From Information Technology to Finance and Natural Science
(2007)
abstract
In the following sections, we will focus on the characterization and modeling of correlations in undirected unweighted complex networks. In particular, we will devote our attention to the statistical characterization of these features in large scale networks. In the section, we review some important and useful general analytical results concerning the topological characterization of random networks. In the third section we recall a number of speci
Clustering in complex networks. II. Percolation properties
M. Angeles Serrano, Marian Boguña,
PHYSICAL REVIEW E
(2006)
abstract
The percolation properties of clustered networks are analyzed in detail. In the case of weak clustering, we present an analytical approach that allows us to find the critical threshold and the size of the giant component. Numerical simulations confirm the accuracy of our results. In more general terms, we show that weak clustering hinders the onset of the giant component whereas strong clustering favors its appearance. This is a direct consequence of the differences in the k-core structure of the networks, which are found to be totally different depending on the level of clustering. An empirical analysis of a real social network confirms our predictions.
Clustering in complex networks. I. General formalism
M. Angeles Serrano, Marian Boguña,
PHYSICAL REVIEW E
(2006)
abstract
We develop a full theoretical approach to clustering in complex networks. A key concept is introduced, the edge multiplicity, that measures the number of triangles passing through an edge. This quantity extends the clustering coefficient in that it involves the properties of two-and not just one-vertices. The formalism is completed with the definition of a three-vertex correlation function, which is the fundamental quantity describing the properties of clustered networks. The formalism suggests different metrics that are able to thoroughly characterize transitive relations. A rigorous analysis of several real networks, which makes use of this formalism and the metrics, is also provided. It is also found that clustered networks can be classified into two main groups: the weak and the strong transitivity classes. In the first class, edge multiplicity is small, with triangles being disjoint. In the second class, edge multiplicity is high and so triangles share many edges. As we shall see in the following paper, the class a network belongs to has strong implications in its percolation properties.
Correlations in weighted networks
M. Angeles Serrano, Marian Boguña, Romualdo Pastor-Satorras,
PHYSICAL REVIEW E
(2006)
abstract
We develop a statistical theory to characterize correlations in weighted networks. We define the appropriate metrics quantifying correlations and show that strictly uncorrelated weighted networks do not exist due to the presence of structural constraints. We also introduce an algorithm for generating maximally random weighted networks with arbitrary P(k,s) to be used as null models. The application of our measures to real networks reveals the importance of weights in a correct understanding and modeling of these heterogeneous systems.
Cut-offs and finite size effects in scale-free networks
Marian Boguña, Romualdo Pastor-Satorras, A. Vespignani,
EUROPEAN PHYSICAL JOURNAL B
(2004)
abstract
We analyze the degree distribution's cut-off in finite size scale-free networks. We show that the cut-off behavior with the number of vertices N is ruled by the topological constraints induced by the connectivity structure of the network. Even in the simple case of uncorrelated networks, we obtain an expression of the structural cut-off that is smaller than the natural cut-off obtained by means of extremal theory arguments. The obtained results are explicitly applied in the case of the configuration model to recover the size scaling of tadpoles and multiple edges.
Class of correlated random networks with hidden variables
Marian Boguña, Romualdo Pastor-Satorras,
PHYSICAL REVIEW E
(2003)
abstract
We study a class of models of correlated random networks in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices. We find analytical expressions for the main topological properties of these models as a function of the distribution of hidden variables and the probability of connecting vertices. The expressions obtained are checked by means of numerical simulations in a particular example. The general model is extended to describe a practical algorithm to generate random networks with an a priori specified correlation structure. We also present an extension of the class, to map nonequilibrium growing networks to networks with hidden variables that represent the time at which each vertex was introduced in the system.
