Fragmenting networks by targeting collective influencers at a mesoscopic level

Teruyoshi Kobayashi, Naoki Masuda*

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

9 Citations (Scopus)
300 Downloads (Pure)


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.

Original languageEnglish
Article number37778
Number of pages12
JournalScientific Reports
Publication statusPublished - 25 Nov 2016


  • network
  • community structure
  • epidemics


Dive into the research topics of 'Fragmenting networks by targeting collective influencers at a mesoscopic level'. Together they form a unique fingerprint.

Cite this