Percolation theory applied to measures of fragmentation in social networks

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_{\infty }$, 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ős-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_{\infty }\approx {(1-F)}^{1∕2}$. For fixed $P_{\infty }$ and close to percolation threshold $(q=q_c)$, we show that $1-F$ better reflects the actual fragmentation. Close to $q_c$, for a given $P_{\infty }$, $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_{\infty }$ for a real social network of workplaces linked by the households of the employees and find similar results.