Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure

Structure of networks that evolve under a combination of growth and contraction

We present analytical results for the emerging structure of networks that evolve via a combination of growth (by node addition and random attachment) and contraction (by random node deletion). To this end we consider a network model in which at each time step a node addition and random attachment step takes place with probability P_{add} and a random node deletion step takes place with probability P_{del}=1-P_{add}. The balance between the growth and contraction processes is captured by the parameter η=P_{add}-P_{del}. The case of pure network growth is described by η=1. In the case that 0<η<1, the rate of node addition exceeds the rate of node deletion and the overall process is of network growth. In the opposite case, where -1<η<0, the overall process is of network contraction, while in the special case of η=0 the expected size of the network remains fixed, apart from fluctuations. Using the master equation and the generating function formalism, we obtain a closed-form expression for the time-dependent degree distribution P_{t}(k). The degree distribution P_{t}(k) includes a term that depends on the initial degree distribution P_{0}(k), which decays as time evolves, and an asymptotic distribution P_{st}(k) which is independent of the initial condition. In the case of pure network growth (η=1), the asymptotic distribution P_{st}(k) follows an exponential distribution, while for -1<η<1 it consists of a sum of Poisson-like terms and exhibits a Poisson-like tail. In the case of overall network growth (0<η<1) the degree distribution P_{t}(k) eventually converges to P_{st}(k). In the case of overall network contraction (-1<η<0) we identify two different regimes. For -1/3<η<0 the degree distribution P_{t}(k) quickly converges towards P_{st}(k). In contrast, for -1<η<-1/3 the convergence of P_{t}(k) is initially very slow and it gets closer to P_{st}(k) only shortly before the network vanishes. Thus, the model exhibits three phase transitions: a structural transition between two functional forms of P_{st}(k) at η=1, a transition between an overall growth and overall contraction at η=0, and a dynamical transition between fast and slow convergence towards P_{st}(k) at η=-1/3. The analytical results are found to be in very good agreement with the results obtained from computer simulations.

Statistical physics of exchangeable sparse simple networks, multiplex networks, and simplicial complexes

Exchangeability is a desired statistical property of network ensembles requiring their invariance upon relabeling of the nodes. However, combining sparsity of network ensembles with exchangeability is challenging. Here we propose a statistical physics framework and a Metropolis-Hastings algorithm defining exchangeable sparse network ensembles. The model generates networks with heterogeneous degree distributions by enforcing only global constraints while existing (nonexchangeable) exponential random graphs enforce an extensive number of local constraints. This very general theoretical framework to describe exchangeable networks is here first formulated for uncorrelated simple networks and then it is extended to treat simple networks with degree correlations, directed networks, bipartite networks, and generalized network structures including multiplex networks and simplicial complexes. In particular here we formulate and treat both uncorrelated and correlated exchangeable ensembles of simplicial complexes using statistical mechanics approaches.

Analytic solution of the two-star model with correlated degrees

Exponential random graphs are important to model the structure of real-world complex networks. Here we solve the two-star model with degree-degree correlations in the sparse regime. The model constraints the average correlation between the degrees of adjacent nodes (nearest neighbors) and between the degrees at the end-points of two-stars (next nearest neighbors). We compute exactly the network free energy and show that this model undergoes a first-order transition to a condensed phase. For non-negative degree correlations between next nearest neighbors, the degree distribution inside the condensed phase has a single peak at the largest degree, while for negative degree correlations between next nearest neighbors the condensed phase is characterized by a bimodal degree distribution. We calculate the degree assortativities and show they are nonmonotonic functions of the model parameters, with a discontinuous behavior at the first-order transition. The first-order critical line terminates at a second-order critical point, whose location in the phase diagram can be accurately determined. Our results can help to develop more detailed models of complex networks with correlated degrees.

Maximal modularity and the optimal size of parliaments

An important question in representative democracies is how to determine the optimal parliament size of a given country. According to an old conjecture, known as the cubic root law, there is a fairly universal power-law relation, with an exponent equal to 1/3, between the size of an elected parliament and the country's population. Empirical data in modern European countries support such universality but are consistent with a larger exponent. In this work, we analyse this intriguing regularity using tools from complex networks theory. We model the population of a democratic country as a random network, drawn from a growth model, where each node is assigned a constituency membership sampled from an available set of size D. We calculate analytically the modularity of the population and find that its functional relation with the number of constituencies is strongly non-monotonic, exhibiting a maximum that depends on the population size. The criterion of maximal modularity allows us to predict that the number of representatives should scale as a power-law in the size of the population, a finding that is qualitatively confirmed by the empirical analysis of real-world data.

Fate of articulation points and bredges in percolation

We investigate the statistics of articulation points and bredges (bridge edges) in complex networks in which bonds are randomly removed in a percolation process. Because of the heterogeneous structure of a complex network, the probability of a node to be an articulation point or the probability of an edge to be a bredge will not be homogeneous across the network. We therefore analyze full distributions of articulation point probabilities as well as bredge probabilities, using a message-passing or cavity approach to the problem. Our methods allow us to obtain these distributions both for large single instances of networks and for ensembles of networks in the configuration model class in the thermodynamic limit, through a single unified approach. We also evaluate deconvolutions of these distributions according to degrees of the node or the degrees of both adjacent nodes in the case of bredges. We obtain closed form expressions for the large mean degree limit of Erdős-Rényi networks. Moreover, we reveal and are able to rationalize a significant amount of structure in the evolution of articulation point and bredge probabilities in response to random bond removal. We find that full distributions of articulation point and bredge probabilities in real networks and in their randomized counterparts may exhibit significant differences even where average articulation point and bredge probabilities do not. We argue that our results could be exploited in a variety of applications, including approaches to network dismantling or to vaccination and islanding strategies to prevent the spread of epidemics or of blackouts in process networks.

Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy

We present analytical results for the structural evolution of random networks undergoing contraction processes via generic node deletion scenarios, namely, random deletion, preferential deletion, and propagating deletion. Focusing on configuration model networks, which exhibit a given degree distribution P_{0}(k) and no correlations, we show using a rigorous argument that upon contraction the degree distributions of these networks converge towards a Poisson distribution. To this end, we use the relative entropy S_{t}=S[P_{t}(k)||π(k|〈K〉_{t})] of the degree distribution P_{t}(k) of the contracting network at time t with respect to the corresponding Poisson distribution π(k|〈K〉_{t}) with the same mean degree 〈K〉_{t} as a distance measure between P_{t}(k) and Poisson. The relative entropy is suitable as a distance measure since it satisfies S_{t}≥0 for any degree distribution P_{t}(k), while equality is obtained only for P_{t}(k)=π(k|〈K〉_{t}). We derive an equation for the time derivative dS_{t}/dt during network contraction and show that the relative entropy decreases monotonically to zero during the contraction process. We thus conclude that the degree distributions of contracting configuration model networks converge towards a Poisson distribution. Since the contracting networks remain uncorrelated, this means that their structures converge towards an Erdős-Rényi (ER) graph structure, substantiating earlier results obtained using direct integration of the master equation and computer simulations [Tishby et al., Phys. Rev. E 100, 032314 (2019)2470-004510.1103/PhysRevE.100.032314]. We demonstrate the convergence for configuration model networks with degenerate degree distributions (random regular graphs), exponential degree distributions, and power-law degree distributions (scale-free networks).

Estimating degree-degree correlation and network cores from the connectivity of high-degree nodes in complex networks

Many of the structural characteristics of a network depend on the connectivity with and within the hubs. These dependencies can be related to the degree of a node and the number of links that a node shares with nodes of higher degree. In here we revise and present new results showing how to construct network ensembles which give a good approximation to the degree-degree correlations, and hence to the projections of this correlation like the assortativity coefficient or the average neighbours degree. We present a new bound for the structural cut-off degree based on the connectivity within the hubs. Also we show that the connections with and within the hubs can be used to define different networks cores. Two of these cores are related to the spectral properties and walks of length one and two which contain at least on hub node, and they are related to the eigenvector centrality. We introduce a new centrality measured based on the connectivity with the hubs. In addition, as the ensembles and cores are related by the connectivity of the hubs, we show several examples how changes in the hubs linkage effects the degree-degree correlations and core properties.

Convergence towards an Erdős-Rényi graph structure in network contraction processes

In a highly influential paper twenty years ago, Barabási and Albert [Science 286, 509 (1999)SCIEAS0036-807510.1126/science.286.5439.509] showed that networks undergoing generic growth processes with preferential attachment evolve towards scale-free structures. In any finite system, the growth eventually stalls and is likely to be followed by a phase of network contraction due to node failures, attacks, or epidemics. Using the master equation formulation and computer simulations, we analyze the structural evolution of networks subjected to contraction processes via random, preferential, and propagating node deletions. We show that the contracting networks converge towards an Erdős-Rényi network structure whose mean degree continues to decrease as the contraction proceeds. This is manifested by the convergence of the degree distribution towards a Poisson distribution and the loss of degree-degree correlations.

Generating random networks that consist of a single connected component with a given degree distribution

We present a method for the construction of ensembles of random networks that consist of a single connected component with a given degree distribution. This approach extends the construction toolbox of random networks beyond the configuration model framework, in which one controls the degree distribution but not the number of components and their sizes. Unlike configuration model networks, which are completely uncorrelated, the resulting single-component networks exhibit degree-degree correlations. Moreover, they are found to be disassortative, namely, high-degree nodes tend to connect to low-degree nodes and vice versa. We demonstrate the method for single-component networks with ternary, exponential, and power-law degree distributions.

Role of adjacency-matrix degeneracy in maximum-entropy-weighted network models

Complex network null models based on entropy maximization are becoming a powerful tool to characterize and analyze data from real systems. However, it is not easy to extract good and unbiased information from these models: A proper understanding of the nature of the underlying events represented in them is crucial. In this paper we emphasize this fact stressing how an accurate counting of configurations compatible with given constraints is fundamental to build good null models for the case of networks with integer-valued adjacency matrices constructed from an aggregation of one or multiple layers. We show how different assumptions about the elements from which the networks are built give rise to distinctively different statistics, even when considering the same observables to match those of real data. We illustrate our findings by applying the formalism to three data sets using an open-source software package accompanying the present work and demonstrate how such differences are clearly seen when measuring network observables.

Quantifying randomness in real networks

Represented as graphs, real networks are intricate combinations of order and disorder. Fixing some of the structural properties of network models to their values observed in real networks, many other properties appear as statistical consequences of these fixed observables, plus randomness in other respects. Here we employ the dk-series, a complete set of basic characteristics of the network structure, to study the statistical dependencies between different network properties. We consider six real networks--the Internet, US airport network, human protein interactions, technosocial web of trust, English word network, and an fMRI map of the human brain--and find that many important local and global structural properties of these networks are closely reproduced by dk-random graphs whose degree distributions, degree correlations and clustering are as in the corresponding real network. We discuss important conceptual, methodological, and practical implications of this evaluation of network randomness, and release software to generate dk-random graphs.

Bridging topological and functional information in protein interaction networks by short loops profiling

Protein-protein interaction networks (PPINs) have been employed to identify potential novel interconnections between proteins as well as crucial cellular functions. In this study we identify fundamental principles of PPIN topologies by analysing network motifs of short loops, which are small cyclic interactions of between 3 and 6 proteins. We compared 30 PPINs with corresponding randomised null models and examined the occurrence of common biological functions in loops extracted from a cross-validated high-confidence dataset of 622 human protein complexes. We demonstrate that loops are an intrinsic feature of PPINs and that specific cell functions are predominantly performed by loops of different lengths. Topologically, we find that loops are strongly related to the accuracy of PPINs and define a core of interactions with high resilience. The identification of this core and the analysis of loop composition are promising tools to assess PPIN quality and to uncover possible biases from experimental detection methods. More than 96% of loops share at least one biological function, with enrichment of cellular functions related to mRNA metabolic processing and the cell cycle. Our analyses suggest that these motifs can be used in the design of targeted experiments for functional phenotype detection.

Correlations between weights and overlap in ensembles of weighted multiplex networks

Multiplex networks describe a large number of systems ranging from social networks to the brain. These multilayer structure encode information in their structure. This information can be extracted by measuring the correlations present in the multiplex networks structure, such as the overlap of the links in different layers. Many multiplex networks are also weighted, and the weights of the links can be strongly correlated with the structural properties of the multiplex network. For example, in multiplex network formed by the citation and collaboration networks between PRE scientists it was found that the statistical properties of citations to coauthors differ from the one of citations to noncoauthors, i.e., the weights depend on the overlap of the links. Here we present a theoretical framework for modeling multiplex weighted networks with different types of correlations between weights and overlap. To this end, we use the framework of canonical network ensembles, and the recently introduced concept of multilinks, showing that null models of a large variety of network structures can be constructed in this way. In order to provide a concrete example of how this framework apply to real data we consider a multiplex constructed from gene expression data of healthy and cancer tissues.

Statistical mechanics of multiedge networks

Statistical properties of binary complex networks are well understood and recently many attempts have been made to extend this knowledge to weighted ones. There are, however, subtle yet important considerations to be made regarding the nature of the weights used in this generalization. Weights can be either continuous or discrete magnitudes, and in the latter case, they can additionally have undistinguishable or distinguishable nature. This fact has not been addressed in the literature insofar and has deep implications on the network statistics. In this work we face this problem introducing multiedge networks as graphs where multiple (distinguishable) connections between nodes are considered. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and nonlinear constraints including those depending both on the number of multiedges per link and their binary projection. The latter case is particularly interesting as we show that binary projections can be understood from multiedge processes. The implications of these results are important as many real-agent-based problems mapped onto graphs require this treatment for a proper characterization of their collective behavior.

Duality between equilibrium and growing networks

In statistical physics any given system can be either at an equilibrium or away from it. Networks are not an exception. Most network models can be classified as either equilibrium or growing. Here we show that under certain conditions there exists an equilibrium formulation for any growing network model, and vice versa. The equivalence between the equilibrium and nonequilibrium formulations is exact not only asymptotically, but even for any finite system size. The required conditions are satisfied in random geometric graphs in general and causal sets in particular, and to a large extent in some real networks.

Statistical mechanics of multiplex networks: entropy and overlap

There is growing interest in multiplex networks where individual nodes take part in several layers of networks simultaneously. This is the case, for example, in social networks where each individual node has different kinds of social ties or transportation systems where each location is connected to another location by different types of transport. Many of these multiplexes are characterized by a significant overlap of the links in different layers. In this paper we introduce a statistical mechanics framework to describe multiplex ensembles. A multiplex is a system formed by N nodes and M layers of interactions where each node belongs to the M layers at the same time. Each layer α is formed by a network G^{α}. Here we introduce the concept of correlated multiplex ensembles in which the existence of a link in one layer is correlated with the existence of a link in another layer. This implies that a typical multiplex of the ensemble can have a significant overlap of the links in the different layers. Moreover, we characterize microcanonical and canonical multiplex ensembles satisfying respectively hard and soft constraints and we discuss how to construct multiplexes in these ensembles. Finally, we provide the expression for the entropy of these ensembles that can be useful to address different inference problems involving multiplexes.

Statistical assessment of crosstalk enrichment between gene groups in biological networks

Motivation

Analyzing groups of functionally coupled genes or proteins in the context of global interaction networks has become an important aspect of bioinformatic investigations. Assessing the statistical significance of crosstalk enrichment between or within groups of genes can be a valuable tool for functional annotation of experimental gene sets.

Results

Here we present CrossTalkZ, a statistical method and software to assess the significance of crosstalk enrichment between pairs of gene or protein groups in large biological networks. We demonstrate that the standard z-score is generally an appropriate and unbiased statistic. We further evaluate the ability of four different methods to reliably recover crosstalk within known biological pathways. We conclude that the methods preserving the second-order topological network properties perform best. Finally, we show how CrossTalkZ can be used to annotate experimental gene sets using known pathway annotations and that its performance at this task is superior to gene enrichment analysis (GEA).

Availability and Implementation

CrossTalkZ (available at http://sonnhammer.sbc.su.se/download/software/CrossTalkZ/) is implemented in C++, easy to use, fast, accepts various input file formats, and produces a number of statistics. These include z-score, p-value, false discovery rate, and a test of normality for the null distributions.

Unbiased degree-preserving randomization of directed binary networks

Randomizing networks using a naive "accept-all" edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with nontrivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in and out degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desired measure on the space of directed graphs in order to generate graphs with more sophisticated topological features. This is demonstrated by defining a process tailored to the production of directed graphs with specified degree-degree correlation functions. The theory is implemented numerically and tested on synthetic and biological network examples.

Entropy rate of nonequilibrium growing networks

New entropy measures have been recently introduced for the quantification of the complexity of networks. Most of these entropy measures apply to static networks or to dynamical processes defined on static complex networks. In this paper we define the entropy rate of growing network models. This entropy rate quantifies how many labeled networks are typically generated by the growing network models. We analytically evaluate the difference between the entropy rate of growing tree network models and the entropy of tree networks that have the same asymptotic degree distribution. We find that the growing networks with linear preferential attachment generated by dynamical models are exponentially less than the static networks with the same degree distribution for a large variety of relevant growing network models. We study the entropy rate for growing network models showing structural phase transitions including models with nonlinear preferential attachment. Finally, we bring numerical evidence that the entropy rate above and below the structural phase transitions follows a different scaling with the network size.

What you see is not what you get: how sampling affects macroscopic features of biological networks

We use mathematical methods from the theory of tailored random graphs to study systematically the effects of sampling on topological features of large biological signalling networks. Our aim in doing so is to increase our quantitative understanding of the relation between true biological networks and the imperfect and often biased samples of these networks that are reported in public data repositories and used by biomedical scientists. We derive exact explicit formulae for degree distributions and degree correlation kernels of sampled networks, in terms of the degree distributions and degree correlation kernels of the underlying true network, for a broad family of sampling protocols that include random and connectivity-dependent node and/or link undersampling as well as random and connectivity-dependent link oversampling. Our predictions are in excellent agreement with numerical simulations.

Shannon and von Neumann entropy of random networks with heterogeneous expected degree

Entropic measures of complexity are able to quantify the information encoded in complex network structures. Several entropic measures have been proposed in this respect. Here we study the relation between the Shannon entropy and the von Neumann entropy of networks with given expected degree sequence. We find in different examples of network topologies that when the degree distribution contains some heterogeneity, an intriguing correlation emerges between the two entropic quantities. This results seems to suggest that heterogeneity in the expected degree distribution is implying an equivalence between a quantum and a classical description of networks, which respectively corresponds to the von Neumann and the Shannon entropy.

Protein networks reveal detection bias and species consistency when analysed by information-theoretic methods

We apply our recently developed information-theoretic measures for the characterisation and comparison of protein–protein interaction networks. These measures are used to quantify topological network features via macroscopic statistical properties. Network differences are assessed based on these macroscopic properties as opposed to microscopic overlap, homology information or motif occurrences. We present the results of a large–scale analysis of protein–protein interaction networks. Precise null models are used in our analyses, allowing for reliable interpretation of the results. By quantifying the methodological biases of the experimental data, we can define an information threshold above which networks may be deemed to comprise consistent macroscopic topological properties, despite their small microscopic overlaps. Based on this rationale, data from yeast–two–hybrid methods are sufficiently consistent to allow for intra–species comparisons (between different experiments) and inter–species comparisons, while data from affinity–purification mass–spectrometry methods show large differences even within intra–species comparisons.