Fragmenting networks by targeting collective influencers at a mesoscopic level

Teruyoshi Kobayashi and Naoki Masuda
Additional contact information
Naoki Masuda: Department of Engineering Mathematics, University of Bristol

No 1616, Discussion Papers from Graduate School of Economics, Kobe University

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.

Keywords: network; community structure; epidemics (search for similar items in EconPapers)
Pages: 58 pages
Date: 2016-06
New Economics Papers: this item is included in nep-cmp, nep-hea and nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.econ.kobe-u.ac.jp/RePEc/koe/wpaper/2016/1616-6.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:koe:wpaper:1616

Access Statistics for this paper

More papers in Discussion Papers from Graduate School of Economics, Kobe University Contact information at EDIRC.
Bibliographic data for series maintained by Kimiaki Shirahama ( this e-mail address is bad, please contact ).