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 (ER) and scale-free (SF) 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.

arXiv commentsubmitted to PRE

References in corpus (18)

• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Attack vulnerability of complex networks
• Self-similarity of complex networks
• Breakdown of the Internet under intentional attack
• Immunization of complex networks
• Growing Scale-Free Networks with Small World Behavior
• Percolation Critical Exponents in Scale-Free Networks
• Optimization of Robustness of Complex Networks
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Structure of a large social network
• Two-Peak and Three-Peak Optimal Complex Networks
• Uncorrelated Random Networks
• Resilience of Complex Networks to Random Breakdown

Cited by in corpus (5)

• Understanding the spreading patterns of mobile phone viruses
• A weighted configuration model and inhomogeneous epidemics
• Graph Partitioning Induced Phase Transitions
• Fragmentation of Random Trees
• New generation of mobile phone viruses and corresponding countermeasures