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.
5 figures, 3 tables, and SI included
References in corpus (11)
- Fast unfolding of communities in large networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Efficient Immunization Strategies for Computer Networks and Populations
- Mitigation of Malicious Attacks on Networks
- Extracting the hierarchical organization of complex systems
- Percolation on sparse networks
- Characterizing the community structure of complex networks
- Improving immunization strategies
- Weighted percolation on directed networks