# 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

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

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