Fragmenting networks by targeting collective influencers at a mesoscopic level
arXiv:1605.03694 · doi:10.1038/srep37778
Abstract
A practical approach to protecting networks against epidemic processes such as spreading of infectious diseases, malware, and harmful viral information is to remove some influential nodes beforehand to fragment the network into small components. Because determining the optimal order to remove nodes is a computationally hard problem, various approximate algorithms have been proposed to efficiently fragment networks by sequential node removal. Morone and Makse proposed an algorithm employing the non-backtracking matrix of given networks, which outperforms various existing algorithms. In fact, many empirical networks have community structure, compromising the assumption of local tree-like structure on which the original algorithm is based. We develop an immunization algorithm by synergistically combining the Morone-Makse algorithm and coarse graining of the network in which we regard a community as a supernode. In this way, we aim to identify nodes that connect different communities at a reasonable computational cost. The proposed algorithm works more efficiently than the Morone-Makse and other algorithms on networks with community structure.
arXiv comment5 figures, 3 tables, and SI included
References in corpus (32)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Community detection in graphs
- Finding community structure in very large networks
- Error and attack tolerance of complex networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- The diameter of the world wide web
- Near linear time algorithm to detect community structures in large-scale networks
- Network robustness and fragility: Percolation on random graphs
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Attack vulnerability of complex networks
- Breakdown of the Internet under intentional attack
- Influence maximization in complex networks through optimal percolation
- Efficient Immunization Strategies for Computer Networks and Populations
- Intensity and coherence of motifs in weighted complex networks
- Mitigation of Malicious Attacks on Networks
- Scale-free topology of e-mail networks
- The map equation
- Generalizations of the clustering coefficient to weighted complex networks
- Extracting the hierarchical organization of complex systems
- Percolation on sparse networks
- Characterizing the community structure of complex networks
- Identifying optimal targets of network attack by belief propagation
- Suppressing Epidemics with a Limited Amount of Immunization Units
- Improving immunization strategies
- Global efficiency of local immunization on complex networks
- Immunization of networks with community structure
- Complex networks vulnerability to module-based attacks
- Weighted percolation on directed networks
- Beyond the locally tree-like approximation for percolation on real networks