Percolation theory and fragmentation measures in social networks

We study the statistical properties of a recently proposed social networks measure of fragmentation F after removal of a fraction q of nodes or links from the network. The measure F is defined as the ratio of the number of pairs of nodes that are not connected in the fragmented network to the total number of pairs in the original fully connected network. We compare this measure with the one traditionally 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, we study Erdo{combining double acute accent}s-Rényi (ER) and scale-free (SF) networks under various node removal strategies. We find that for a network obtained after removal of a fraction q of nodes above criticality, P_∞ ≈ (1 - F)^{1 / 2}. For fixed P_∞ and close to criticality, we show that 1 - F better reflects the actual fragmentation. For a given P_∞, 1 - F has a broad distribution and thus one can improve significantly the fragmentation of the network. We also study and compare the fragmentation measure F and the percolation measure P_∞ for a real national social network of workplaces linked by the households of the employees and find similar results.