Graph Partitioning Induced Phase Transitions

Simple item page
dc.creatorPaul, Gerald
dc.creatorCohen, Reuven
dc.creatorSreenivasan, Sameet
dc.creatorHavlin, Shlomo
dc.creatorStanley, H. Eugene
dc.date2007-02-17
dc.date.accessioned2026-07-07T08:34:14Z
dc.date.available2026-07-07T08:34:14Z
dc.descriptionWe 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$.
dc.identifierhttps://arxiv.org/abs/cond-mat/0702417
dc.identifierhttp://arxiv.org/abs/cond-mat/0702417
dc.identifierPhys. Rev. Lett. 99, 115701 (2007)
dc.identifierdoi:10.1103/PhysRevLett.99.115701
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/139366
dc.subjectStatistical Mechanics
dc.subjectDisordered Systems and Neural Networks
dc.titleGraph Partitioning Induced Phase Transitions
dc.typetext

Files

Collections

arXiv