Graph Partitioning Induced Phase Transitions

Abstract

We study the percolation properties of graph partitioning on random regular graphs with N vertices of degree $k$. Optimal graph partitioning is directly related to optimal attack and immunization of complex networks. We find that for any partitioning process (even if non-optimal) that partitions the graph into equal sized connected components (clusters), the system undergoes a percolation phase transition at $f=f_c=1-2/k$ where $f$ is the fraction of edges removed to partition the graph. For optimal partitioning, at the percolation threshold, we find $S\sim N^{0.4}$ where $S$ is the size of the clusters and $\ell \sim N^{0.25}$ where $\ell$ is their diameter. Additionally, we find that $S$ undergoes multiple non-percolation transitions for $f<f_c$.

References in corpus (5)

• Resilience of the Internet to random breakdowns
• Attack vulnerability of complex networks
• Extremal Optimization for Graph Partitioning
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Percolation theory applied to measures of fragmentation in social networks

Cited by in corpus (5)

• Critical phenomena in complex networks
• Vital nodes identification in complex networks
• Percolation on complex networks: Theory and application
• Generalized theory for node disruption in finite size complex networks
• Optimal shattering of complex networks