Agglomerative percolation on bipartite networks: nonuniversal behavior due to spontaneous symmetry breaking at the percolation threshold.

Ordinary bond percolation (OP) can be viewed as a process where clusters grow by joining them pairwise, adding links chosen randomly one by one from a set of predefined virtual links. In contrast, in agglomerative percolation (AP) clusters grow by choosing randomly a target cluster and joining it with all its neighbors, as defined by the same set of virtual links. Previous studies showed that AP is in different universality classes from OP for several types of (virtual) networks (linear chains, trees, Erdös-Rényi networks), but most surprising were the results for two-dimensional (2D) lattices: While AP on the triangular lattice was found to be in the OP universality class, it behaved completely differently on the square lattice. In the present paper we explain this striking violation of universality by invoking bipartivity. While the square lattice is a bipartite graph, the triangular lattice is not. In conformity with this we show that AP on the honeycomb and simple cubic (3D) lattices--both of which are bipartite--are also not in the OP universality classes. More precisely, we claim that this violation of universality is basically due to a Z(2) symmetry that is spontaneously broken at the percolation threshold. We also discuss AP on bipartite random networks and suitable generalizations of AP on k-partite graphs.

Discontinuous percolation transitions in epidemic processes, surface depinning in random media, and Hamiltonian random graphs.

Discontinuous percolation transitions and the associated tricritical points are manifest in a wide range of both equilibrium and nonequilibrium cooperative phenomena. To demonstrate this, we present and relate the continuous and first-order behaviors in two different classes of models: The first are generalized epidemic processes that describe in their spatially embedded version--either on or off a regular lattice--compact or fractal cluster growth in random media at zero temperature. A random graph version of these processes is mapped onto a model previously proposed for complex social contagion. We compute detailed phase diagrams and compare our numerical results at the tricritical point in d = 3 with field theory predictions of Janssen et al. [Phys. Rev. E 70, 026114 (2004)]. The second class consists of exponential ("Hamiltonian," i.e., formally equilibrium) random graph models and includes the Strauss and the two-star model, where "chemical potentials" control the densities of links, triangles, or two-stars. When the chemical potentials in either graph model are O(logN), the percolation transition can coincide with a first-order phase transition in the density of links, making the former also discontinuous. Hysteresis loops can then be of mixed order, with second-order behavior for decreasing link fugacity, and a jump (first order) when it increases.

Exact solutions for mass-dependent irreversible aggregations.

We consider the mass-dependent aggregation process (k+1)X→X, given a fixed number of unit mass particles in the initial state. One cluster is chosen proportional to its mass and is merged into one, either with k neighbors in one dimension, or--in the well-mixed case--with k other clusters picked randomly. We find the same combinatorial exact solutions for the probability to find any given configuration of particles on a ring or line, and in the well-mixed case. The mass distribution of a single cluster exhibits scaling laws and the finite-size scaling form is given. The relation to the classical sum kernel of irreversible aggregation is discussed.

Percolation transitions are not always sharpened by making networks interdependent.

We study a model for coupled networks introduced recently by Buldyrev et al., [Nature (London) 464, 1025 (2010)], where each node has to be connected to others via two types of links to be viable. Removing a critical fraction of nodes leads to a percolation transition that has been claimed to be more abrupt than that for uncoupled networks. Indeed, it was found to be discontinuous in all cases studied. Using an efficient new algorithm we verify that the transition is discontinuous for coupled Erdös-Rényi networks, but find it to be continuous for fully interdependent diluted lattices. In 2 and 3 dimensions, the order parameter exponent ß is larger than in ordinary percolation, showing that the transition is less sharp, i.e., further from discontinuity, than for isolated networks. Possible consequences for spatially embedded networks are discussed.

Explosive percolation is continuous, but with unusual finite size behavior.

We study four Achlioptas-type processes with "explosive" percolation transitions. All transitions are clearly continuous, but their finite size scaling functions are not entirely holomorphic. The distributions of the order parameter, i.e., the relative size s(max)/N of the largest cluster, are double humped. But-in contrast to first-order phase transitions-the distance between the two peaks decreases with system size N as N(-η) with η>0. We find different positive values of ß (defined via (s(max)/N)∼(p-p(c))ß for infinite systems) for each model, showing that they are all in different universality classes. In contrast, the exponent Θ (defined such that observables are homogeneous functions of (p-p(c))N(Θ)) is close to-or even equal to-1/2 for all models.

Random sequential renormalization of networks: application to critical trees.

We introduce the concept of random sequential renormalization (RSR) for arbitrary networks. RSR is a graph renormalization procedure that locally aggregates nodes to produce a coarse grained network. It is analogous to the (quasi)parallel renormalization schemes introduced by C. Song et al. [C. Song et al., Nature (London) 433, 392 (2005)] and studied by F. Radicchi et al. [F. Radicchi et al., Phys. Rev. Lett. 101, 148701 (2008)], but much simpler and easier to implement. Here we apply RSR to critical trees and derive analytical results consistent with numerical simulations. Critical trees exhibit three regimes in their evolution under RSR. (i) For N0{ν}≲N

Sequence alignment, mutual information, and dissimilarity measures for constructing phylogenies.

BACKGROUND: Existing sequence alignment algorithms use heuristic scoring schemes based on biological expertise, which cannot be used as objective distance metrics. As a result one relies on crude measures, like the p- or log-det distances, or makes explicit, and often too simplistic, a priori assumptions about sequence evolution. Information theory provides an alternative, in the form of mutual information (MI). MI is, in principle, an objective and model independent similarity measure, but it is not widely used in this context and no algorithm for extracting MI from a given alignment (without assuming an evolutionary model) is known. MI can be estimated without alignments, by concatenating and zipping sequences, but so far this has only produced estimates with uncontrolled errors, despite the fact that the normalized compression distance based on it has shown promising results. RESULTS: We describe a simple approach to get robust estimates of MI from global pairwise alignments. Our main result uses algorithmic (Kolmogorov) information theory, but we show that similar results can also be obtained from Shannon theory. For animal mitochondrial DNA our approach uses the alignments made by popular global alignment algorithms to produce MI estimates that are strikingly close to estimates obtained from the alignment free methods mentioned above. We point out that, due to the fact that it is not additive, normalized compression distance is not an optimal metric for phylogenetics but we propose a simple modification that overcomes the issue of additivity. We test several versions of our MI based distance measures on a large number of randomly chosen quartets and demonstrate that they all perform better than traditional measures like the Kimura or log-det (resp. paralinear) distances. CONCLUSIONS: Several versions of MI based distances outperform conventional distances in distance-based phylogeny. Even a simplified version based on single letter Shannon entropies, which can be easily incorporated in existing software packages, gave superior results throughout the entire animal kingdom. But we see the main virtue of our approach in a more general way. For example, it can also help to judge the relative merits of different alignment algorithms, by estimating the significance of specific alignments. It strongly suggests that information theory concepts can be exploited further in sequence analysis.

Random sequential renormalization and agglomerative percolation in networks: application to Erdös-Rényi and scale-free graphs.

We study the statistical behavior under random sequential renormalization (RSR) of several network models including Erdös-Rényi (ER) graphs, scale-free networks, and an annealed model related to ER graphs. In RSR the network is locally coarse grained by choosing at each renormalization step a node at random and joining it to all its neighbors. Compared to previous (quasi-)parallel renormalization methods [Song et al., Nature (London) 433, 392 (2005)], RSR allows a more fine-grained analysis of the renormalization group (RG) flow and unravels new features that were not discussed in the previous analyses. In particular, we find that all networks exhibit a second-order transition in their RG flow. This phase transition is associated with the emergence of a giant hub and can be viewed as a new variant of percolation, called agglomerative percolation. We claim that this transition exists also in previous graph renormalization schemes and explains some of the scaling behavior seen there. For critical trees it happens as N/N(0) → 0 in the limit of large systems (where N(0) is the initial size of the graph and N its size at a given RSR step). In contrast, it happens at finite N/N(0) in sparse ER graphs and in the annealed model, while it happens for N/N(0) → 1 on scale-free networks. Critical exponents seem to depend on the type of the graph but not on the average degree and obey usual scaling relations for percolation phenomena. For the annealed model they agree with the exponents obtained from a mean-field theory. At late times, the networks exhibit a starlike structure in agreement with the results of Radicchi et al. [Phys. Rev. Lett. 101, 148701 (2008)]. While degree distributions are of main interest when regarding the scheme as network renormalization, mass distributions (which are more relevant when considering "supernodes" as clusters) are much easier to study using the fast Newman-Ziff algorithm for percolation, allowing us to obtain very high statistics.

Clustering drives assortativity and community structure in ensembles of networks.

Clustering, assortativity, and communities are key features of complex networks. We probe dependencies between these features and find that ensembles of networks with high clustering display both high assortativity by degree and prominent community structure, while ensembles with high assortativity show much less enhancement of the clustering or community structure. Further, clustering can amplify a small homophilic bias for trait assortativity in network ensembles. This marked asymmetry suggests that transitivity could play a larger role than homophily in determining the structure of many complex networks.

Communities, clustering phase transitions, and hysteresis: pitfalls in constructing network ensembles.

Ensembles of networks are used as null models in many applications. However, simple null models often show much less clustering than their real-world counterparts. In this paper, we study a "biased rewiring model" where clustering is enhanced by means of a fugacity as in the Strauss (or "triangle") model, but where the number of links attached to each node is strictly preserved. Similar models have been proposed previously in Milo [Science 298, 824 (2002)]. Our model exhibits phase transitions as the fugacity is changed. For regular graphs (identical degrees for all nodes) with degree k>2 we find a single first order transition. For all nonregular networks that we studied (including Erdös-Rényi, scale-free, and several real-world networks) multiple jumps resembling first order transitions appear. The jumps coincide with the sudden emergence of "cluster cores:" groups of highly interconnected nodes with higher than average degrees, where each edge participates in many triangles. Hence, clustering is not smoothly distributed throughout the network. Once formed, the cluster cores are difficult to remove, leading to strong hysteresis. To study the cluster cores visually, we introduce q-clique adjacency plots. Cluster cores constitute robust communities that emerge spontaneously from the triangle generating process, rather than being put explicitly into the definition of the model. All the quantities we measured including the modularity, assortativity, clustering and number of four and five-cliques exhibit simultaneous jumps and are equivalent order parameters. Finally, we point out that cluster cores produce pitfalls when using the present (and similar) models as null models for strongly clustered networks, due to strong hysteresis which leads to broken ergodicity on realistic sampling time scales.

Edge direction and the structure of networks.

Directed networks are ubiquitous and are necessary to represent complex systems with asymmetric interactions--from food webs to the World Wide Web. Despite the importance of edge direction for detecting local and community structure, it has been disregarded in studying a basic type of global diversity in networks: the tendency of nodes with similar numbers of edges to connect. This tendency, called assortativity, affects crucial structural and dynamic properties of real-world networks, such as error tolerance or epidemic spreading. Here we demonstrate that edge direction has profound effects on assortativity. We define a set of four directed assortativity measures and assign statistical significance by comparison to randomized networks. We apply these measures to three network classes--online/social networks, food webs, and word-adjacency networks. Our measures (i) reveal patterns common to each class, (ii) separate networks that have been previously classified together, and (iii) expose limitations of several existing theoretical models. We reject the standard classification of directed networks as purely assortative or disassortative. Many display a class-specific mixture, likely reflecting functional or historical constraints, contingencies, and forces guiding the system's evolution.

Activity-dependent branching ratios in stocks, solar x-ray flux, and the Bak-Tang-Wiesenfeld sandpile model.

We define an activity-dependent branching ratio that allows comparison of different time series X(t). The branching ratio b(x) is defined as b(x)=E[xi(x)/x]. The random variable xi(x) is the value of the next signal given that the previous one is equal to x, so xi(x)=[X(t+1) | X(t)=x]. If b(x)>1, the process is on average supercritical when the signal is equal to x, while if b(x)<1, it is subcritical. For stock prices we find b(x)=1 within statistical uncertainty, for all x, consistent with an "efficient market hypothesis." For stock volumes, solar x-ray flux intensities, and the Bak-Tang-Wiesenfeld (BTW) sandpile model, b(x) is supercritical for small values of activity and subcritical for the largest ones, indicating a tendency to return to a typical value. For stock volumes this tendency has an approximate power-law behavior. For solar x-ray flux and the BTW model, there is a broad regime of activity where b(x) approximately equal 1, which we interpret as an indicator of critical behavior. This is true despite different underlying probability distributions for X(t) and for xi(x). For the BTW model the distribution of xi(x) is Gaussian, for x sufficiently larger than 1, and its variance grows linearly with x. Hence, the activity in the BTW model obeys a central limit theorem when sampling over past histories. The broad region of activity where b(x) is close to one disappears once bulk dissipation is introduced in the BTW model-supporting our hypothesis that it is an indicator of criticality.

Attractor and basin entropies of random Boolean networks under asynchronous stochastic update.

We introduce a method to study random Boolean networks with asynchronous stochastic update. Each node in the state space network starts with equal occupation probability, which then evolves to a steady state. Attractors and the sizes of their basins are determined by the nodes left occupied at late times. As for synchronous update, the basin entropy grows with system size only for critical networks. We determine analytically the distribution for the number of attractors and basin sizes for networks with connectivity K=1 . These differ from the case of synchronous update for all K .

Interacting branching process as a simple model of innovation.

We describe innovation in terms of a generalized branching process. Each new invention pairs with any existing one to produce a number of offspring, which is Poisson distributed with mean p. Existing inventions die with probability p/τ at each generation. In contrast with mean field results, no phase transition occurs; the chance for survival is finite for all p > 0. For τ = ∞, surviving processes exhibit a bottleneck before exploding superexponentially-a growth consistent with a law of accelerating returns. This behavior persists for finite τ. We analyze, in detail, the asymptotic behavior as p→0.

Networks of recurrent events, a theory of records, and an application to finding causal signatures in seismicity.

We propose a method to search for signs of causal structure in spatiotemporal data making minimal a priori assumptions about the underlying dynamics. To this end, we generalize the elementary concept of recurrence for a point process in time to recurrent events in space and time. An event is defined to be a recurrence of any previous event if it is closer to it in space than all the intervening events. As such, each sequence of recurrences for a given event is a record breaking process. This definition provides a strictly data driven technique to search for structure. Defining events to be nodes, and linking each event to its recurrences, generates a network of recurrent events. Significant deviations in statistical properties of that network compared to networks arising from (acausal) random processes allows one to infer attributes of the causal dynamics that generate observable correlations in the patterns. We derive analytically a number of properties for the network of recurrent events composed by a random process in space and time. We extend the theory of records to treat not only the variable where records happen, but also time as continuous. In this way, we construct a fully symmetric theory of records leading to a number of results. Those analytic results are compared in detail to the properties of a network synthesized from time series of epicenter locations for earthquakes in Southern California. Significant disparities from the ensemble of acausal networks that can be plausibly attributed to the causal structure of seismicity are as follows. (1) Invariance of network statistics with the time span of the events considered. (2) The appearance of a fundamental length scale for recurrences, independent of the time span of the catalog, which is consistent with observations of the "rupture length." (3) Hierarchy in the distances and times of subsequent recurrences. As expected, almost all of the statistical properties of a network constructed from a surrogate in which the original magnitudes and locations of earthquake epicenters are randomly "shuffled" are completely consistent with predictions from the acausal null model.

Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequences.

The simplest null models for networks, used to distinguish significant features of a particular network from a priori expected features, are random ensembles with the degree sequence fixed by the specific network of interest. These "fixed degree sequence" (FDS) ensembles are, however, famously resistant to analytic attack. In this paper we introduce ensembles with partially-fixed degree sequences (PFDS) and compare analytic results obtained for them with Monte Carlo results for the FDS ensemble. These results include link likelihoods, subgraph likelihoods, and degree correlations. We find that local structural features in the FDS ensemble can be reasonably well estimated by simultaneously fixing only the degrees of a few nodes, in addition to the total number of nodes and links. As test cases we use two protein interaction networks (Escherichia coli, Saccharomyces cerevisiae), the internet on the autonomous system (AS) level, and the World Wide Web. Fixing just the degrees of two nodes gives the mean neighbor degree as a function of node degree, k;{'}_{k} , in agreement with results explicitly obtained from rewiring. For power law degree distributions, we derive the disassortativity analytically. In the PFDS ensemble the partition function can be expanded diagrammatically. We obtain an explicit expression for the link likelihood to lowest order, which reduces in the limit of large, sparse undirected networks with L links and with k_{max}L to the simple formula P(k,k;{'})=kk;{'}(2L+kk;{'}) . In a similar limit, the probability for three nodes to be linked into a triangle reduces to the factorized expression P_{Delta}(k_{1},k_{2},k_{3})=P(k_{1},k_{2})P(k_{1},k_{3})P(k_{2},k_{3}) .

Graph animals, subgraph sampling, and motif search in large networks.

We generalize a sampling algorithm for lattice animals (connected clusters on a regular lattice) to a Monte Carlo algorithm for "graph animals," i.e., connected subgraphs in arbitrary networks. As with the algorithm in [N. Kashtan et al., Bioinformatics 20, 1746 (2004)], it provides a weighted sample, but the computation of the weights is much faster (linear in the size of subgraphs, instead of superexponential). This allows subgraphs with up to ten or more nodes to be sampled with very high statistics, from arbitrarily large networks. Using this together with a heuristic algorithm for rapidly classifying isomorphic graphs, we present results for two protein interaction networks obtained using the tandem affinity purification (TAP) method: one of Escherichia coli with 230 nodes and 695 links, and one for yeast (Saccharomyces cerevisiae) with roughly ten times more nodes and links. We find in both cases that most connected subgraphs are strong motifs (Z scores >10) or antimotifs (Z scores <-10) when the null model is the ensemble of networks with fixed degree sequence. Strong differences appear between the two networks, with dominant motifs in E. coli being (nearly) bipartite graphs and having many pairs of nodes that connect to the same neighbors, while dominant motifs in yeast tend towards completeness or contain large cliques. We also explore a number of methods that do not rely on measurements of Z scores or comparisons with null models. For instance, we discuss the influence of specific complexes like the 26S proteasome in yeast, where a small number of complexes dominate the k cores with large k and have a decisive effect on the strongest motifs with 6-8 nodes. We also present Zipf plots of counts versus rank. They show broad distributions that are not power laws, in contrast to the case when disconnected subgraphs are included.

Network analysis of the state space of discrete dynamical systems.

We study networks representing the dynamics of elementary 1D cellular automata (CA) on finite lattices. We analyze scaling behaviors of both local and global network properties as a function of system size. The scaling of the largest node in-degree is obtained analytically for a variety of CA including rules 22, 54, and 110. We further define the path diversity as a global network measure. The coappearance of nontrivial scaling in both the hub size and the path diversity separates simple dynamics from the more complex behaviors typically found in Wolfram's class IV and some class III CA.