%0 Journal Article %1 Chen2007 %A Chen, Yiping %A Paul, Gerald %A Cohen, Reuven %A Havlin, Shlomo %A Borgatti, Stephen P. %A Liljeros, Fredrik %A Stanley, H. Eugene %D 2007 %I American Physical Society %J Physical Review E %K fragmentation graphs networks percolation social-networks %N 4 %P 046107 %R 10.1103/PhysRevE.75.046107 %T Percolation theory applied to measures of fragmentation in social networks %V 75 %X We apply percolation theory to a recently proposed measure of fragmentation F for social networks. The measure F is defined as the ratio between the number of pairs of nodes that are not connected in the fragmented network after removing a fraction q of nodes and the total number of pairs in the original fully connected network. We compare F with the traditional measure used in percolation theory, P∞, the fraction of nodes in the largest cluster relative to the total number of nodes. Using both analytical and numerical methods from percolation, we study Erd\Hos-Rényi and scale-free networks under various types of node removal strategies. The removal strategies are random removal, high degree removal, and high betweenness centrality removal. We find that for a network obtained after removal (all strategies) of a fraction q of nodes above percolation threshold, P∞≈(1−F)1∕2. For fixed P∞ and close to percolation threshold (q=qc), we show that 1−F better reflects the actual fragmentation. Close to qc, for a given P∞, 1−F has a broad distribution and it is thus possible to improve the fragmentation of the network. We also study and compare the fragmentation measure F and the percolation measure P∞ for a real social network of workplaces linked by the households of the employees and find similar results.

@article{Chen2007, abstract = {We apply percolation theory to a recently proposed measure of fragmentation F for social networks. The measure F is defined as the ratio between the number of pairs of nodes that are not connected in the fragmented network after removing a fraction q of nodes and the total number of pairs in the original fully connected network. We compare F with the traditional measure used in percolation theory, P∞, the fraction of nodes in the largest cluster relative to the total number of nodes. Using both analytical and numerical methods from percolation, we study {Erd\H{o}s-R\'{e}nyi} and scale-free networks under various types of node removal strategies. The removal strategies are random removal, high degree removal, and high betweenness centrality removal. We find that for a network obtained after removal (all strategies) of a fraction q of nodes above percolation threshold, {P∞≈(1−F})1∕2. For fixed P∞ and close to percolation threshold (q=qc), we show that {1−F} better reflects the actual fragmentation. Close to qc, for a given P∞, {1−F} has a broad distribution and it is thus possible to improve the fragmentation of the network. We also study and compare the fragmentation measure F and the percolation measure P∞ for a real social network of workplaces linked by the households of the employees and find similar results.}, added-at = {2011-04-20T14:28:03.000+0200}, author = {Chen, Yiping and Paul, Gerald and Cohen, Reuven and Havlin, Shlomo and Borgatti, Stephen P. and Liljeros, Fredrik and Stanley, H. Eugene}, biburl = {https://www.bibsonomy.org/bibtex/2b50e287e578e97f829d6e2ceda09022b/rincedd}, doi = {10.1103/PhysRevE.75.046107}, interhash = {68dd4480ba6942fb18f57e50d4ed2c05}, intrahash = {b50e287e578e97f829d6e2ceda09022b}, journal = {Physical Review E}, keywords = {fragmentation graphs networks percolation social-networks}, number = 4, pages = 046107, publisher = {American Physical Society}, timestamp = {2011-04-20T14:28:03.000+0200}, title = {Percolation theory applied to measures of fragmentation in social networks}, volume = 75, year = 2007 }