Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure

Understanding how the network topology affects the spread of an epidemic is a main concern in order to develop efficient immunization strategies. While there is a great deal of work dealing with the macroscopic topological properties of the networks, few

PDF / 384,271 Bytes
12 Pages / 439.37 x 666.142 pts Page_size
107 Downloads / 226 Views

DOWNLOAD

REPORT

Depatment of Computer Science and Engineering, National Institute of Technology, New Delhi 110040, Delhi, India {debayan.chakraborty,anuragsg}@nitdelhi.ac.in 2 Le2i UMR CNRS 6306, University of Burgundy, Dijon, France [email protected]

Abstract. Understanding how the network topology aﬀects the spread of an epidemic is a main concern in order to develop eﬃcient immunization strategies. While there is a great deal of work dealing with the macroscopic topological properties of the networks, few studies have been devoted to the inﬂuence of the community structure. Furthermore, while in many real-world networks communities may overlap, in these studies non-overlapping community structures are considered. In order to gain insight about the inﬂuence of the overlapping nodes in the epidemic process we conduct an empirical evaluation of basic deterministic immunization strategies based on the overlapping nodes. Using the classical SIR model on a real-world network with ground truth overlapping community structure we analyse how immunization based on the membership number of overlapping nodes (which is the number of communities the node belongs to) aﬀect the largest connected component size. Comparison with random immunization strategies designed for networks with non-overlapping community structure show that overlapping nodes play a major role in the epidemic process. Keywords: Immunization · Diﬀusion ping community · Membership number

1

·

Complex networks

·

Overlap-

Introduction

The eﬀect of network structure on the spread of diseases is a widely studied topic, and much research has gone into this ﬁeld [1–8]. The topological feature of network have been used for immunization within network [9–15]. These works have mainly studied the various immunization strategies and their eﬀect on epidemic outbreak within a social network or contact network. The study of networks according to the degree distribution, and further the inﬂuence of immunization on degree distribution and targeted attacks has been explored by scholars in recent past [16–18]. But the community-based study of the network has not received much attention. In this level of abstraction, which has c Springer International Publishing Switzerland 2016 H.T. Nguyen and V. Snasel (Eds.): CSoNet 2016, LNCS 9795, pp. 62–73, 2016. DOI: 10.1007/978-3-319-42345-6 6

Immunization Strategies Based on the Overlapping Nodes in Networks

63

been termed as the mesoscopic level, the concern lies with the properties of the communities. Communities are sets of nodes which show more level of interconnectivity amongst themselves, than with the rest of the network. We can distinguish two type of community structure in the literature depending on the fact that they share some nodes or not. Non-overlapping communities are standalone groups where a node belongs to a single community while in overlapping communities a node can belongs to more than one community. Recent research and analysis of real-world networks have revealed that a signiﬁcant portion of nodes lies within

Data Loading...