TY - JOUR

T1 - Percolation theory applied to measures of fragmentation in social networks

AU - Chen, Yiping

AU - Paul, Gerald

AU - Cohen, Reuven

AU - Havlin, Shlomo

AU - Borgatti, Stephen P.

AU - Liljeros, Fredrik

AU - Stanley, H. Eugene

PY - 2007/4/13

Y1 - 2007/4/13

N2 - 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 Erdos-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)12. 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.

AB - 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 Erdos-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)12. 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.

UR - http://www.scopus.com/inward/record.url?scp=34247173579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247173579&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.75.046107

DO - 10.1103/PhysRevE.75.046107

M3 - Article

AN - SCOPUS:34247173579

SN - 1539-3755

VL - 75

JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

IS - 4

M1 - 046107

ER -