Distribution of shortest path lengths on trees of a given size in subcritical Erdos-Rényi networks.

In the subcritical regime Erdos-Rényi (ER) networks consist of finite tree components, which are nonextensive in the network size. The distribution of shortest path lengths (DSPL) of subcritical ER networks was recently calculated using a topological expansion [E. Katzav, O. Biham, and A. K. Hartmann, Phys. Rev. E 98, 012301 (2018)2470-004510.1103/PhysRevE.98.012301]. The DSPL, which accounts for the distance ℓ between any pair of nodes that reside on the same finite tree component, was found to follow a geometric distribution of the form P(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where 0

Distribution of the number of cycles in directed and undirected random regular graphs of degree 2.

We present analytical results for the distribution of the number of cycles in directed and undirected random 2-regular graphs (2-RRGs) consisting of N nodes. In directed 2-RRGs each node has one inbound link and one outbound link, while in undirected 2-RRGs each node has two undirected links. Since all the nodes are of degree k=2, the resulting networks consist of cycles. These cycles exhibit a broad spectrum of lengths, where the average length of the shortest cycle in a random network instance scales with lnN, while the length of the longest cycle scales with N. The number of cycles varies between different network instances in the ensemble, where the mean number of cycles 〈S〉 scales with lnN. Here we present exact analytical results for the distribution P_{N}(S=s) of the number of cycles s in ensembles of directed and undirected 2-RRGs, expressed in terms of the Stirling numbers of the first kind. In both cases the distributions converge to a Poisson distribution in the large N limit. The moments and cumulants of P_{N}(S=s) are also calculated. The statistical properties of directed 2-RRGs are equivalent to the combinatorics of cycles in random permutations of N objects. In this context our results recover and extend known results. In contrast, the statistical properties of cycles in undirected 2-RRGs have not been studied before.

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.

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

Statistical analysis of edges and bredges in configuration model networks.

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks, or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability P[over ̂](e∈B) that a random edge e in a configuration model network with degree distribution P(k) is a bredge (B). We also calculate the joint degree distribution P[over ̂](k,k^{'}|B) of the end-nodes i and i^{'} of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability P[over ̂](e∈B|GC) that a random edge on the giant component is a bredge. We also calculate the joint degree distribution P[over ̂](k,k^{'}|B,GC) of the end-nodes of bredges and the joint degree distribution P[over ̂](k,k^{'}|NB,GC) of the end-nodes of nonbredge edges on the giant component. Surprisingly, it is found that the degrees k and k^{'} of the end-nodes of bredges are correlated, while the degrees of the end-nodes of nonbredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance Γ(B,GC) of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdos-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

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 Erdos-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).

Convergence towards an Erdos-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 Erdos-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.

Distribution of shortest path lengths in subcritical Erdos-Rényi networks.

Networks that are fragmented into small disconnected components are prevalent in a large variety of systems. These include the secure communication networks of commercial enterprises, government agencies, and illicit organizations, as well as networks that suffered multiple failures, attacks, or epidemics. The structural and statistical properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are nonextensive. Surprisingly, such networks do not exhibit the small-world property that is typical in supercritical random networks, where the mean distance between pairs of nodes scales logarithmically with the network size. Unlike supercritical networks whose structure has been studied extensively, subcritical networks have attracted relatively little attention. A special feature of these networks is that the statistical and geometric properties vary between different components and depend on their sizes and topologies. The overall statistics of the network can be obtained by a summation over all the components with suitable weights. We use a topological expansion to perform a systematic analysis of the degree distribution and the distribution of shortest path lengths (DSPL) on components of given sizes and topologies in subcritical Erdos-Rényi (ER) networks. From this expansion we obtain an exact analytical expression for the DSPL of the entire subcritical network, in the asymptotic limit. The DSPL, which accounts for all the pairs of nodes that reside on the same finite component (FC), is found to follow a geometric distribution of the form P_{FC}(L=ℓ|L<∞)=(1-c)c^{ℓ-1}, where c<1 is the mean degree. Using computer simulations we calculate the DSPL in subcritical ER networks of increasing sizes and confirm the convergence to this asymptotic result. We also obtain exact asymptotic results for the mean distance, 〈L〉_{FC}, and for the standard deviation of the DSPL, σ_{L,FC}, and show that the simulation results converge to these asymptotic results. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the nongiant components of ER networks above the percolation transition.

Revealing the microstructure of the giant component in random graph ensembles.

The microstructure of the giant component of the Erdos-Rényi network and other configuration model networks is analyzed using generating function methods. While configuration model networks are uncorrelated, the giant component exhibits a degree distribution which is different from the overall degree distribution of the network and includes degree-degree correlations of all orders. We present exact analytical results for the degree distributions as well as higher-order degree-degree correlations on the giant components of configuration model networks. We show that the degree-degree correlations are essential for the integrity of the giant component, in the sense that the degree distribution alone cannot guarantee that it will consist of a single connected component. To demonstrate the importance and broad applicability of these results, we apply them to the study of the distribution of shortest path lengths on the giant component, percolation on the giant component, and spectra of sparse matrices defined on the giant component. We show that by using the degree distribution on the giant component one obtains high quality results for these properties, which can be further improved by taking the degree-degree correlations into account. This suggests that many existing methods, currently used for the analysis of the whole network, can be adapted in a straightforward fashion to yield results conditioned on the giant component.

Distribution of shortest path lengths in a class of node duplication network models.

We present analytical results for the distribution of shortest path lengths (DSPL) in a network growth model which evolves by node duplication (ND). The model captures essential properties of the structure and growth dynamics of social networks, acquaintance networks, and scientific citation networks, where duplication mechanisms play a major role. Starting from an initial seed network, at each time step a random node, referred to as a mother node, is selected for duplication. Its daughter node is added to the network, forming a link to the mother node, and with probability p to each one of its neighbors. The degree distribution of the resulting network turns out to follow a power-law distribution, thus the ND network is a scale-free network. To calculate the DSPL we derive a master equation for the time evolution of the probability P_{t}(L=ℓ), ℓ=1,2,⋯, where L is the distance between a pair of nodes and t is the time. Finding an exact analytical solution of the master equation, we obtain a closed form expression for P_{t}(L=ℓ). The mean distance 〈L〉_{t} and the diameter Δ_{t} are found to scale like lnt, namely, the ND network is a small-world network. The variance of the DSPL is also found to scale like lnt. Interestingly, the mean distance and the diameter exhibit properties of a small-world network, rather than the ultrasmall-world network behavior observed in other scale-free networks, in which 〈L〉_{t}∼lnlnt.

Distribution of shortest cycle lengths in random networks.

We present analytical results for the distribution of shortest cycle lengths (DSCL) in random networks. The approach is based on the relation between the DSCL and the distribution of shortest path lengths (DSPL). We apply this approach to configuration model networks, for which analytical results for the DSPL were obtained before. We first calculate the fraction of nodes in the network which reside on at least one cycle. Conditioning on being on a cycle, we provide the DSCL over ensembles of configuration model networks with degree distributions which follow a Poisson distribution (Erdos-Rényi network), degenerate distribution (random regular graph), and a power-law distribution (scale-free network). The mean and variance of the DSCL are calculated. The analytical results are found to be in very good agreement with the results of computer simulations.

Distance distribution in configuration-model networks.

We present analytical results for the distribution of shortest path lengths between random pairs of nodes in configuration model networks. The results, which are based on recursion equations, are shown to be in good agreement with numerical simulations for networks with degenerate, binomial, and power-law degree distributions. The mean, mode, and variance of the distribution of shortest path lengths are also evaluated. These results provide expressions for central measures and dispersion measures of the distribution of shortest path lengths in terms of moments of the degree distribution, illuminating the connection between the two distributions.

Stochastic analysis of bistability in coherent mixed feedback loops combining transcriptional and posttranscriptional regulations.

Mixed feedback loops combining transcriptional and posttranscriptional regulations are common in cellular regulatory networks. They consist of two genes, encoding a transcription factor and a small noncoding RNA (sRNA), which mutually regulate each other's expression. We present a theoretical and numerical study of coherent mixed feedback loops of this type, in which both regulations are negative. Under suitable conditions, these feedback loops are expected to exhibit bistability, namely, two stable states, one dominated by the transcriptional repressor and the other dominated by the sRNA. We use deterministic methods based on rate equation models, in order to identify the range of parameters in which bistability takes place. However, the deterministic models do not account for the finite lifetimes of the bistable states and the spontaneous, fluctuation-driven transitions between them. Therefore, we use stochastic methods to calculate the average lifetimes of the two states. It is found that these lifetimes strongly depend on rate coefficients such as the transcription rates of the transcriptional repressor and the sRNA. In particular, we show that the fraction of time the system spends in the sRNA-dominated state follows a monotonically decreasing sigmoid function of the transcriptional repressor transcription rate. The biological relevance of these results is discussed in the context of such mixed feedback loops in Escherichia coli. It is shown that the fluctuation-driven transitions and the dependence of some rate coefficients on the biological conditions enable the cells to switch to the state which is better suited for the existing conditions and to remain in that state as long as these conditions persist.

A defense-offense multi-layered regulatory switch in a pathogenic bacterium.

Cells adapt to environmental changes by efficiently adjusting gene expression programs. Staphylococcus aureus, an opportunistic pathogenic bacterium, switches between defensive and offensive modes in response to quorum sensing signal. We identified and studied the structural characteristics and dynamic properties of the core regulatory circuit governing this switch by deterministic and stochastic computational methods, as well as experimentally. This module, termed here Double Selector Switch (DSS), comprises the RNA regulator RNAIII and the transcription factor Rot, defining a double-layered switch involving both transcriptional and post-transcriptional regulations. It coordinates the inverse expression of two sets of target genes, immuno-modulators and exotoxins, expressed during the defensive and offensive modes, respectively. Our computational and experimental analyses show that the DSS guarantees fine-tuned coordination of the inverse expression of its two gene sets, tight regulation, and filtering of noisy signals. We also identified variants of this circuit in other bacterial systems, suggesting it is used as a molecular switch in various cellular contexts and offering its use as a template for an effective switching device in synthetic biology studies.

Interactions between distant ceRNAs in regulatory networks.

Competing endogenous RNAs (ceRNAs) were recently introduced as RNA transcripts that affect each other's expression level through competition for their microRNA (miRNA) coregulators. This stems from the bidirectional effects between miRNAs and their target RNAs, where a change in the expression level of one target affects the level of the miRNA regulator, which in turn affects the level of other targets. By the same logic, miRNAs that share targets compete over binding to their common targets and therefore also exhibit ceRNA-like behavior. Taken together, perturbation effects could propagate in the posttranscriptional regulatory network through a path of coregulated targets and miRNAs that share targets, suggesting the existence of distant ceRNAs. Here we study the prevalence of distant ceRNAs and their effect in cellular networks. Analyzing the network of miRNA-target interactions deciphered experimentally in HEK293 cells, we show that it is a dense, intertwined network, suggesting that many nodes can act as distant ceRNAs of one another. Indeed, using gene expression data from a perturbation experiment, we demonstrate small, yet statistically significant, changes in gene expression caused by distant ceRNAs in that network. We further characterize the magnitude of the propagated perturbation effect and the parameters affecting it by mathematical modeling and simulations. Our results show that the magnitude of the effect depends on the generation and degradation rates of involved miRNAs and targets, their interaction rates, the distance between the ceRNAs and the topology of the network. Although demonstrated for a miRNA-mRNA regulatory network, our results offer what to our knowledge is a new view on various posttranscriptional cellular networks, expanding the concept of ceRNAs and implying possible distant cross talk within the network, with consequences for the interpretation of indirect effects of gene perturbation.

Global regulation of transcription by a small RNA: a quantitative view.

Small RNAs are integral regulators of bacterial gene expression, the majority of which act posttranscriptionally by basepairing with target mRNAs, altering translation or mRNA stability. 6S RNA, however, is a small RNA that is a transcriptional regulator, acting by binding directly to σ(70)-RNA polymerase (σ(70)-RNAP) and preventing its binding to gene promoters. At the transition from exponential to stationary phase, 6S RNA accumulates and globally downregulates the transcription of hundreds of genes. At the transition from stationary to exponential phase (outgrowth), 6S RNA is released from σ(70)-RNAP, resulting in a fast increase in free σ(70)-RNAP and transcription of many genes. The transition from stationary to exponential phase is sharp, and is thus accessible for experimental study. However, the transition from exponential to stationary phase is gradual and complicated by changes in other factors, making it more difficult to isolate 6S RNA effects experimentally at this transition. Here, we use mathematical modeling and simulation to study the dynamics of 6S RNA-dependent regulation, focusing on transitions in growth mediated by altered nutrient availability. We first show that our model reproduces the sharp increase in σ(70)-RNAP at outgrowth, as well as the behavior of two experimentally tested mutants, thus justifying its use for characterizing the less accessible dynamics of the transition from exponential to stationary phase. We characterize the dynamics of the two transitions for Escherichia coli wild-type, as well as for mutants with various 6S RNA-RNAP affinities, demonstrating that the 6S RNA regulation mechanism is generally robust to a wide range of such mutations, although the level of regulation at single promoters and their resulting expression fold change will be altered with changes in affinity. Our results provide insight into the potential advantage of transcription regulation by 6S RNA, as it enables storage and efficient release of σ(70)-RNAP during transitions in nutrient availability, which is likely to give a competitive advantage to cells encountering diverse environmental conditions.

Stochastic analysis of complex reaction networks using binomial moment equations.

The stochastic analysis of complex reaction networks is a difficult problem because the number of microscopic states in such systems increases exponentially with the number of reactive species. Direct integration of the master equation is thus infeasible and is most often replaced by Monte Carlo simulations. While Monte Carlo simulations are a highly effective tool, equation-based formulations are more amenable to analytical treatment and may provide deeper insight into the dynamics of the network. Here, we present a highly efficient equation-based method for the analysis of stochastic reaction networks. The method is based on the recently introduced binomial moment equations [Barzel and Biham, Phys. Rev. Lett. 106, 150602 (2011)]. The binomial moments are linear combinations of the ordinary moments of the probability distribution function of the population sizes of the interacting species. They capture the essential combinatorics of the reaction processes reflecting their stoichiometric structure. This leads to a simple and transparent form of the equations, and allows a highly efficient and surprisingly simple truncation scheme. Unlike ordinary moment equations, in which the inclusion of high order moments is prohibitively complicated, the binomial moment equations can be easily constructed up to any desired order. The result is a set of equations that enables the stochastic analysis of complex reaction networks under a broad range of conditions. The number of equations is dramatically reduced from the exponential proliferation of the master equation to a polynomial (and often quadratic) dependence on the number of reactive species in the binomial moment equations. The aim of this paper is twofold: to present a complete derivation of the binomial moment equations; to demonstrate the applicability of the moment equations for a representative set of example networks, in which stochastic effects play an important role.

Competition between small RNAs: a quantitative view.

Two major classes of small regulatory RNAs--small interfering RNAs (siRNAs) and microRNA (miRNAs)--are involved in a common RNA interference processing pathway. Small RNAs within each of these families were found to compete for limiting amounts of shared components, required for their biogenesis and processing. Association with Argonaute (Ago), the catalytic component of the RNA silencing complex, was suggested as the central mechanistic point in RNA interference machinery competition. Aiming to better understand the competition between small RNAs in the cell, we present a mathematical model and characterize a range of specific cell and experimental parameters affecting the competition. We apply the model to competition between miRNAs and study the change in the expression level of their target genes under a variety of conditions. We show quantitatively that the amount of Ago and miRNAs in the cell are dominant factors contributing greatly to the competition. Interestingly, we observe what to our knowledge is a novel type of competition that takes place when Ago is abundant, by which miRNAs with shared targets compete over them. Furthermore, we use the model to examine different interaction mechanisms that might operate in establishing the miRNA-Ago complexes, mainly those related to their stability and recycling. Our model provides a mathematical framework for future studies of competition effects in regulation mechanisms involving small RNAs.

Binomial moment equations for stochastic reaction systems.

A highly efficient formulation of moment equations for stochastic reaction networks is introduced. It is based on a set of binomial moments that capture the combinatorics of the reaction processes. The resulting set of equations can be easily truncated to include moments up to any desired order. The number of equations is dramatically reduced compared to the master equation. This formulation enables the simulation of complex reaction networks, involving a large number of reactive species much beyond the feasibility limit of any existing method. It provides an equation-based paradigm to the analysis of stochastic networks, complementing the commonly used Monte Carlo simulations.