Agglomerative Percolation on Bipartite Networks: A Novel Type of Spontaneous Symmetry Breaking

Abstract

Ordinary bond percolation (OP) can be viewed as a process where clusters grow by joining them pairwise, by 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, Erdos-Renyi networks), but most surprising were the results for 2-d 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 (3-d) 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.

arXiv comment11 pages, including 18 figures

References in corpus (15)

• Catastrophic cascade of failures in interdependent networks
• Network robustness and fragility: Percolation on random graphs
• Self-similarity of complex networks
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• A fast Monte Carlo algorithm for site or bond percolation
• "Explosive Percolation" Transition is Actually Continuous
• Percolation Theory on Interdependent Networks Based on Epidemic Spreading
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Ordinary Percolation with Discontinuous Transitions
• Are Percolation Transitions always Sharpened by Making Networks Interdependent?
• Renormalization flows in complex networks
• Irreversible Aggregation and Network Renormalization
• Random Sequential Renormalization of Networks I: Application to Critical Trees
• Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
• Exact solutions for mass-dependent irreversible aggregations

Cited by in corpus (5)

• Optimal interdependence between networks for the evolution of cooperation
• Recent advances and open challenges in percolation
• Phase Transitions in Cooperative Coinfections: Simulation Results for Networks and Lattices
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Percolation in Media with Columnar Disorder