Graph Partitioning Induced Phase Transitions

Details Graph Partitioning Induced Phase Transitions Graph Partitioning Induced Phase Transitions

2007-02-17

arxiv.org/abs/cond-mat/0702417v1

Phys. Rev. Lett. 99, 115701 (2007)

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1103/PhysRevLett.99.115701

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

Affiliated with

Also associated with

No associations

Rating

Graph Partitioning Induced Phase Transitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Partitioning Induced Phase Transitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Partitioning Induced Phase Transitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-591397