Network immunization under limited budget using graph spectra

R. Zahedi () and M. Khansari
Additional contact information
R. Zahedi: Department of Science and Engineering, Sharif University of Technology, Amir Kabir Square, Kish Island, Iran
M. Khansari: #x2020;Faculty of New Sciences and Technologies, University of Tehran, Amir Abad, North Kargar Street, Tehran 14395-1374, Iran

International Journal of Modern Physics C (IJMPC), 2016, vol. 27, issue 08, 1-10

Abstract: In this paper, we propose a new algorithm that minimizes the worst expected growth of an epidemic by reducing the size of the largest connected component (LCC) of the underlying contact network. The proposed algorithm is applicable to any level of available resources and, despite the greedy approaches of most immunization strategies, selects nodes simultaneously. In each iteration, the proposed method partitions the LCC into two groups. These are the best candidates for communities in that component, and the available resources are sufficient to separate them. Using Laplacian spectral partitioning, the proposed method performs community detection inference with a time complexity that rivals that of the best previous methods. Experiments show that our method outperforms targeted immunization approaches in both real and synthetic networks.

Keywords: Community; complex networks; graph spectra; immunization (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183116500960
Access to full text is restricted to subscribers

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:wsi:ijmpcx:v:27:y:2016:i:08:n:s0129183116500960

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183116500960

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().