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.

Figure 1

Effective critical cluster densities for AP on finite 2D lattices versus $L^{-3/4}$, where $L$ is the lattice size. For ordinary percolation, where $n_c\left(L\right)-n_c\sim L^{-1/\nu }$ with $\nu =4/3$, this should give straight lines. For each lattice type (triangular: upper pair of curves; square: lower pair of curves) we show results obtained with two different operational definitions for the critical point: (i) Maximal range of the power law $P_n\left(m\right)\sim m^{-\tau }$, and (ii) the probability to have a cluster that wraps around a lattice with helical boundary conditions is equal to 1/2. The corresponding values of $n_c\left(L\right)$ are called $n_{c,\tau }\left(L\right)$ and $n_{c,\mathrm{wrap}}\left(L\right)$ (from Ref. [13]).

Figure 2

Wrapping probability density $d{p}_{\mathrm{wrap}}/dn$ for 2D square lattices with different boundary condition (B.C.), and with sizes differing by just one unit, compared to similar results for triangular lattices. All curves for square lattices have peaks at smaller values than for triangular lattices and have more heavy left hand tails, but this is most pronounced for strictly periodic B.C. with even $L$.

Figure 3

Black triangles: Cluster densities $n$ at which $p_{\mathrm{wrap}}\left(n\right)=1/2$, plotted against $L$, for square lattices with periodic B.C. The upper curve is for odd sizes, and the lower curve is for even sizes. Red dots: Analogous results for a slightly modified model, where each neighboring cluster agglomerates with the target cluster only with probability $q<1$. In the present case $q=0.999$.

Figure 4

The five panels of this figure correspond to (a) square lattices with $q=1$, (b) honeycomb lattices, (c) triangular lattices, (d) square lattices with $q=0.999$, and (e) cubic lattices. In all cases, periodic B.C.s were used. In all cases except case (d), $q=1$.

Figure 5

Plot of $S/{(n_c-n)}^{\beta }$ against $(n_c-n)L^{1/\nu }$, using the exponents of ordinary 3D percolation. Each curve is for one value of $L$, with the highest curve corresponding to the smallest lattices ($L=64$) and the lowest curve to the largest. According to the FSS ansatz, these curves should collapse and should be horizontal in the limit where we first take $L\to \infty$ and then $n\to n_c$. This seems not to be the case.

Figure 6

Analogous to the previous plot, but using $\beta =0.435,D_f=2.5220$, and $\nu =0.91$.

Figure 7

Plot of $S{L}^{\beta /\nu }=m_{\max }/L^{D_f}$ versus $(n-n_c)L^{1/\nu }$ for AP on the simple cubic lattice, using $n_c=0.411$ and the exponents given in Eq. (5).

Figure 8

Part of a square lattice with cluster boundaries indicated by black lines. Plaquettes correspond to nodes of the graph. Nine clusters are labeled with letters A–I. Six of them (A, B, D–F) are single nodes, one (C) has five nodes, and two (H, I) are very large. Three of them (D, H, I) are blue, the other six are white. If cluster D is chosen as target, it merges with C, E, F, and G and the new cluster is white. If, however, F is chosen as target, the new blue cluster would consist of D, H, and I.

Figure 9

A configuration with three large clusters at $n\approx 0.03$ and $L=128$. For clusters of mass $>1$ the two colors are red and blue, with the larger clusters more bright and the smaller ones more dark. Blue singletons are colored white for better visibility and in order to distinguish them from red singletons which actually are indicated by black squares. Notice that no two clusters of the same color ever touch in this figure. Wherever they seem to touch, there is indeed a small cluster of the opposite color intervening. In spite of the size of the largest clusters, none of them has yet wrapped in the vertical direction.

Figure 10

Cluster mass distributions for simple cubic lattices with $L=32$. The curve for $n=0.4323$ is subcritical, while the other curves are supercritical. In contrast to the case of OP, where the mass distribution develops a single peak in the supercritical phase, now (i.e., for AP) we see two peaks. They correspond to clusters of opposite colors. The right-hand peak is strongest for the smallest value of $n$ (0.1419) and is absent for the the largest $n$. Notice that the curves are ranked for $m<100$ so that they rise with increasing $n$.

Figure 11

Average size of the second-largest cluster on simple cubic lattices with even size. In contrast to OP, where $m_{\max ,2}$ peaks near the percolation transition and decreases fast when one goes into the supercritical phase, here the second-largest cluster continues to grow far beyond the percolation transition $n_c\approx 0.411$.

Figure 12

Probabilities $c_s\left(n\right)$ of color patterns $s=(-++),(-+-),(--+),$ and $(---)$ for the largest three clusters, plotted against $n$. The first index (here always –) gives the color of the largest cluster, while the other two are for the second and third largest. The data are for square lattices of size $L=512$.

Figure 13

Probabilities that the two largest clusters have the same color. According to our theory, these probabilities should vanish in the supercritical phase, if $L\to \infty$. Panel (a) is for the square lattice, panel (b) for the cubic. The upper inset in panel (b) shows the region close to the critical point. The lower inset shows a data collapse plot, $c_{--}\left(n\right)$ against $(n-n_c)L^{1/\nu }$ with $n_c=0.4109$ and $\nu =1.01$.

Figure 14

Fraction of nodes in the largest cluster $\langle m_{\max }\rangle /N$ for random bipartite networks.

Figure 15

Scaling collapse for $\langle m_{\max }\rangle$ in the critical region for random bipartite networks.

Figure 16

Probabilities $c_{--}\left(n\right)$ for the largest two clusters in a random bipartite network to have the same color, for different system sizes. As also seen from the inset, these curves cross near the estimated critical point $n_c\approx 0.696$.

Figure 17

Part of a triangular lattice where sites (hexagons) are colored red, green, and blue. The colors are arranged such that no two sites with the same color are adjacent (i.e., if neighbors are connected by bonds the lattice is tripartite). A modified AP process is defined such that a target with color R can join only with neighbors of color G, G can join only with B, and B can join only with R. This is indicated by the arrows and is denoted by $\text{R}\to \text{G}\to \text{B}\to \text{R}$. When node A is chosen as target, it agglomerates with all G neighbors and becomes itself G, so that the new cluster is all G on its surface.

Figure 18

Each circle represents a color (i.e., an element of a partition of a $k$-partite network. An arrow from partition A to partition B means that a target with color A joins with all nodes of color B. Solid arrows indicate cycles that are followed at each agglomeration step, while dotted arrows indicate random AP rules where different colors are chosen at different time steps.