%0 Journal Article %1 Paul2007Graph %A Paul, Gerald %A Cohen, Reuven %A Sreenivasan, Sameet %A Havlin, Shlomo %A Stanley, Eugene H. %D 2007 %I APS %J Physical Review Letters %K partition %N 11 %R 10.1103/PhysRevLett.99.115701 %T Graph Partitioning Induced Phase Transitions %U http://dx.doi.org/10.1103/PhysRevLett.99.115701 %V 99 %X 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 nonoptimal) that partitions the graph into essentially equal sized connected components (clusters), the system undergoes a percolation phase transition at f=fc=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Ñ0.4 where S is the size of the clusters and Ñ0.25 where is their diameter. Also, we find that S undergoes multiple nonpercolation transitions for f<fc.

@article{Paul2007Graph, 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 nonoptimal) that partitions the graph into essentially equal sized connected components (clusters), the system undergoes a percolation phase transition at f=fc=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\~{}N0.4 where S is the size of the clusters and \~{}N0.25 where is their diameter. Also, we find that S undergoes multiple nonpercolation transitions for f\<fc.}, added-at = {2009-09-24T14:55:30.000+0200}, author = {Paul, Gerald and Cohen, Reuven and Sreenivasan, Sameet and Havlin, Shlomo and Stanley, Eugene H.}, biburl = {https://www.bibsonomy.org/bibtex/29267998655f039dbab4b246bbc2cd33e/andreacapocci}, citeulike-article-id = {1693240}, citeulike-linkout-0 = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=PRLTAO000099000011115701000001\&idtype=cvips\&gifs=yes}, citeulike-linkout-1 = {http://link.aps.org/abstract/PRL/v99/e115701}, citeulike-linkout-2 = {http://dx.doi.org/10.1103/PhysRevLett.99.115701}, doi = {10.1103/PhysRevLett.99.115701}, interhash = {dc63a2d27667ee37e77b4e2a7fc46e45}, intrahash = {9267998655f039dbab4b246bbc2cd33e}, journal = {Physical Review Letters}, keywords = {partition}, number = 11, posted-at = {2007-09-25 16:25:22}, priority = {5}, publisher = {APS}, timestamp = {2009-09-24T14:55:35.000+0200}, title = {Graph Partitioning Induced Phase Transitions}, url = {http://dx.doi.org/10.1103/PhysRevLett.99.115701}, volume = 99, year = 2007 }