A local immunization strategy for networks with overlapping community structure

Highlights

• A network-based local immunization method is proposed.

• It is a random-walk based selection of overlapping nodes among communities.

• It is more effective for networks with stronger community structure.

• It is more effective for networks with higher overlapping membership of nodes.

Abstract

Since full coverage treatment is not feasible due to limited resources, we need to utilize an immunization strategy to effectively distribute the available vaccines. On the other hand, the structure of contact network among people has a significant impact on epidemics of infectious diseases (such as SARS and influenza) in a population. Therefore, network-based immunization strategies aim to reduce the spreading rate by removing the vaccinated nodes from contact network. Such strategies try to identify more important nodes in epidemics spreading over a network. In this paper, we address the effect of overlapping nodes among communities on epidemics spreading. The proposed strategy is an optimized random-walk based selection of these nodes. The whole process is local, i.e. it requires contact network information in the level of nodes. Thus, it is applicable to large-scale and unknown networks in which the global methods usually are unrealizable. Our simulation results on different synthetic and real networks show that the proposed method outperforms the existing local methods in most cases. In particular, for networks with strong community structures, high overlapping membership of nodes or small size communities, the proposed method shows better performance.

Introduction

Understanding the behavior of an infectious disease is essential because the disease can turn to a crucial situation if it is not completely eradicated on time  [1], [2], [3]. The process of disease diffusion can be modeled by a network representation of people and interactions among them  [4]. An infection spreads from one individual to another in the network, and therefore immunization or vaccination of each person excludes him/her from the process of spreading  [5].

An important goal in epidemiology is to find a way to stop or at least slow down the speed of contagion  [6], [7]. Simplifying by mass-action approximation, elimination of a disease requires a specific amount of immunization coverage  [5]. This quantity of coverage is impossible to be reached due to the constraints of time, vaccine supply, etc.  [8], [9], [10]. For stopping epidemics in social networks, finding influential spreaders is a significant target  [3], [11], [12]. Consequently, investigating efficient immunization methods is still a particularly interesting area for researchers  [10].

Using centrality measures, like degree  [13] and betweenness  [14] methods is believed to be effective for immunization. These methods are classified as global immunization methods. Assuming the knowledge of the whole network, they rank all nodes according to their centrality and then pick the highest central nodes for immunization. As it is obvious, this process is impractical in large-scale networks. In fact, computation of the whole network becomes impossible as the network size grows. Moreover, the whole structure of real-world networks are often unknown. Another group of immunization methods is the group of local methods  [8], [15], [9], [16], [17], [18], in which the target nodes are found via local search. Of course, it is unreasonable to expect local methods to outperform global methods, because of the limited amount of knowledge they use, but some properties make local methods interesting: first, they do not need to know the complete structure of the contact network, and second, they find target nodes faster than global methods. These properties make local methods applicable in large-scale and especially real-world social networks where the topologies are usually unknown.

The structure of networks influences epidemic spreading patterns. Many real-world networks consist of communities  [19], i.e. structures that exhibit denser connections between nodes of the same group compared to nodes of different groups  [20]. Bridge nodes connect different communities to each other and create a pathway of spreading disease. The effect of bridge nodes on epidemics has been investigated in the previous works  [9], [17]. In community structures, we meet the concept of overlapping nodes that belong to more than one community  [21], [22]. In social networks, the existence of overlapping nodes is undeniable and communities are not completely separated from each other. Hebert et al.  [18] immunized these nodes by the order of their community membership. As mentioned before, the main drawback of local methods is their final result which is far from global methods, while their most valuable benefits are being independent of the whole knowledge of the network and lower time complexity.

In this paper, we propose an immunization method by focusing on overlapping community structure of networks. Our general idea is to utilize the role of overlapping nodes in epidemic dynamics. This method is local, so it does not require detailed information of the contact network. We also compared our method with different global and local immunization methods in both synthetic and real networks. Simulation results show that:

• Proposed method usually achieves the least epidemic size among other local methods and in some cases, outperforms global methods.

• Its’ performance enhances by increasing the community structure and the membership degree of overlapping nodes. Particularly, in networks with small-size communities, it is a highly effective method.

• Selecting overlapping nodes in an order different from what membership method uses, the only method which immunizes overlapping nodes, results in better performance and less time complexity.