Minimizing outbreak through targeted blocking for disease control: a community-based approach using super-spreader node identification – Scientific Reports

August 30, 2023

14

One method that proves useful in problem-solving across various fields involves creating a small sample that represents the problem at hand. This approach is equally applicable to the challenge of identifying individuals within a network who can control the spread of an entire community when blocked. In order to illustrate this method, we will utilize a small network depicted in Fig. 1.

Figure 1

A small example of a graph modeled society.

As illustrated in Fig. 1, the network can be divided into distinct communities based on their characteristics. By doing so, we can then focus on seeking the desired nodes within each community. These nodes possess the capability to effectively control the spread of entire community when they are blocked. In the subsequent sections, we will delve into the comprehensive examination of the general steps involved in this proposed method, along with the individual components comprising each step.

Our proposed method for selecting super-blockers to Control Infectious Diffusion (SBCID) is depicted in Fig. 2. In the following sections, we will delve into the general steps of the proposed method, providing a comprehensive examination of each component.

Input network

As shown in Fig. 2, the first step in the proposed method is to read the input network. Considering that in most existing networks, the information is in the form of a list of available edges. Therefore, the data of input network (Fig. 1), is in the Table 2.

Table 2 Part of the input data set of the proposed method.

According to Table 2, generally, the data sets used are in csv format (data separated by commas), in which the first number indicates the source node number and the second number indicates the destination node number.

Extracting network communities

Complex networks, including social networks, possess unique characteristics that differentiate them from other networks. One important characteristic is the tendency of nodes to establish stronger connections with specific nodes in the network. These connections form what we refer to as “communities,” which are regions of the network that exhibit a higher density of edges compared to other areas. Identifying and utilizing these communities can significantly enhance the effectiveness of our proposed method. Given that many diseases spread through interpersonal contact, and considering the increased communication and interaction within society, these communities become particularly relevant in understanding and controlling epidemics.

To accomplish this, in paper, we utilize a method introduced in³² for extracting communities from the input graph. The method consists of two phases:

(1)

Initially, nodes are individually assigned to communities. Nodes are then repositioned to neighboring communities if it enhances modularity. This process is repeated until no further improvements are achievable.
(2)

In the second phase, a new network is constructed using the communities from the first phase. The links between the new nodes are weighted based on the links between nodes in the corresponding communities. This generates a hierarchical structure of communities, progressively reducing the meta-communities with each iteration until the maximum modularity is attained.

The results of applying the community detection algorithm to our sample graph are depicted in Fig. 3. The method successfully identifies four distinct communities:

Community C1: Consisting of nodes 1 to 11;
Community C2: Consisting of nodes 12 to 19;
Community C3: Consisting of nodes 20 to 25;
Community C4: Consisting of nodes 26 to 30.

Selection of community connectors

By examining the communities depicted in Fig. 3, it becomes apparent that certain nodes within these communities could potentially belong to different communities. For instance, node 5, initially placed in community C1, has connections with nodes 26 and 27 in community C4. Similarly, node 4 has connections with node 13 in community C2 and node 23 in community C3. The presence of these nodes and their diverse connections can facilitate the rapid spread of diseases throughout the network. Therefore, in this phase, these nodes are identified. Each node’s set of neighbors is locally checked, and if a neighbor from another community is found within this set, the node is identified as a connector. The nodes identified as connectors are visually differentiated by a distinct color, as shown in Fig. 4. The selection steps of these nodes are as follows:

In the sample network, nodes 4, 5, 12, 13, 22, 23, 26 and 27 play the role of connecting communities C1 to C4. The existence of these nodes can cause the spread of disease from one community to another. Therefore, in order to isolate the communities, in the first step, it is necessary to completely cut off the communication between them. For this purpose, these connecting nodes are specified as the initial set and an effort is made to determine the minimum node that, by removing them, the communities will be completely separated. By considering Fig. 5, it can be seen that by removing node 5, the connection between C1 community and C4 is disconnect. By removing node 4, the connection between C1 community and C2 and C3 communities will be cut off. By removing node 12, the connection between C2 community and C3 is cut off, and finally, by removing node 23, the connection between C3 and C4 communities is cut off. The result is shown in Fig. 5.

The steps for arbitrary networks are given in Algorithm 2. In this algorithm, which receives connecting nodes as input; First, it sorts these nodes in descending order of the number of their friends in different communities. For example, node 4 of community C1 has two friends in communities C2 and C3, which will be removed from the set of connectors of node 13 by selecting and removing it. Because it no longer connects societies. By repeating this procedure, the isolating nodes are specified one after the other and the connectors set is empty. In this way, the minimum number of nodes that can completely separate each society from other societies are determined. Obviously, if the number of members of a society is very small, they can be omitted or they can be made a part of a larger society.

Determining the top spreaders in each community to be blocked

After separating each society and removing the nodes that are communication between the nodes of one society and other societies. It is necessary to specify the nodes that should be selected for blocking in each community. Considering that a lot of contact and communication can be the main cause of the spread of respiratory diseases. Firstly, the communication edges between the nodes of the society, which represent the contact and mutual relations between the nodes, were weighted. For this purpose, due to the lack of real communication between network nodes, the concept of number of common neighbors and also the degree of two-headed nodes are used to measure the communication weight. In the other words, the probability of communication between two nodes that have more common neighbors increases. Also, the edge between two nodes that connects more neighbors is more important. Eq. (1) is used to calculate the number of common neighbors of edge nodes,

$$\begin{aligned} CN(u,w)=|N(u)\cap N(w)|, \end{aligned}$$

(1)

where N(u) and N(w) represents the set of neighbors of nodes v and w and Eq. (2) is used to weight the communication edges between the nodes of each community.

$$\begin{aligned} W_{v,w}=(CN(u,w)+1)(deg(v)+deg(w)) \end{aligned}$$

(2)

In Eq. (2), the value of the common neighbor is added to one so that if the two end vertices of the edge do not have a common neighbor, the weight of the edge is not zero. Fig. 6 shows the result of weighting edges between nodes of community C1.

After weighting the edges between the nodes of each community, it is necessary to calculate the outbreak power of the nodes of each community and select the nodes with higher power to be blockaded. For this purpose, a semi-local method is presented, in which not only the weight of the edges of each node with its neighbors is considered, but also the weight of the edges between the neighbors and the neighboring neighbors is considered. Therefore, Eq. (3) has been used to compute the outbreak of each node u:

$$\begin{aligned} SP(u)=ks(u)+\sum _{\begin{array}{c} v\in N(u)\\ v \ is \ not\ blocked \end{array}}\sum _{\begin{array}{c} s\in N(v)\\ \ s\ is \ not \ blocked \end{array}}W_{v,s} \end{aligned}$$

(3)

In Eq. (3), ks is the k-shell number in which the node is located, and the weight of the edges of the node with neighbors of level 1 and 2 is also considered. It should be mentioned, to reduce the overlap of edge weight towards the previously blocked nodes, we do not consider it.

In community C1 shown in Fig. 7, nodes 8, 9, 10 and 11 are located in k-shell 1 and nodes 1 to 7 are located in k-shell number 2. That is, $ks_1 = \{8, 9, 10, 11\}$ and $ks_2 = \{1, 2, 3, 4, 5, 6, 7\}$. The results obtained from the outbreak of the nodes of this community are shown in descending order in Fig. 7.

The obtained results show that nodes 2, 6 and 7 are nodes that can infect more nodes in case of contamination or disease. Therefore, depending on the amount of vaccine available, these nodes can be selected as the main candidates for blocking. This procedure has been implemented in other identified communities and in each community, a number of nodes with the highest outbreak are selected for primary blocking. In this way, the network can be protected with a much smaller number of doses and the outbreak can be controlled in the very initial steps. The general procedure of the proposed method is given in Algorithm 3.

Time complexity of the proposed method

To evaluate the time complexity of the proposed algorithm, we analyze each step:

(1)

The community detection Algorithm 1 used in the method has a time complexity of O(nlogn) when applied to a graph with n nodes.
(2)

Identifying set of Connectors (Algorithm 1 ): The time complexity is approximately $O(|V| * d)$, where |V| is the number of nodes in the graph G, and d is the average node degree.
(3)

Specify the minimum connectors set (Algorithm 2 ): The time complexity depends on the number of connectors, assumed to be c.
(4)

DescendingSort(SP): Sorting the SP list in descending order takes $O(c * log(c))$ time.
(5)

Calculations within loops involving CN(v, w) and W(v, w) take constant time, O(1).
(6)

Nested loops iterating through communities and edges take linear time in the worst case.
(7)

SP(v) calculation involves nested summations, resulting in $O(d^2)$ time in the worst case.
(8)

Subsequent sorting of SP takes $O(d^2 * log(d^2))$ time.
(9)

Calculating nvb involves division and multiplication, taking constant time, O(1).
(10)

Adding the top nvc elements from the SP list to the blocked-set takes O(nvc) time.

Overall, the time complexity of the algorithm is given by:

$T(n) = O(nlogn) + O(|V| * d) + O(c * log(c)) + O(d^2 * log(d^2)) + O(nvc).$

Since the community detection algorithm (O(nlogn)) dominates the time complexity, we can approximate it as: $T(n) \approx O(nlogn)$. Therefore, the overall time complexity of the algorithm is approximately O(nlogn), where n is the number of nodes in the graph.

Source link