# Identifying Super-Spreader Nodes in Complex Networks

Authors: Yu-Hsiang Fu; Chung-Yuan Huang; Chuen-Tsai Sun
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Identifying the most influential individuals spreading information or infectious diseases can assist or hinder information dissemination, product exposure, and contagious disease detection. Hub nodes, high betweenness nodes, high closeness nodes, and highk-shell nodes have been identified as good initial spreaders, but efforts to use node diversity within network structures to measure spreading ability are few. Here we describe a two-step framework that combines global diversity and local features to identify the most influential network nodes. Results from susceptible-infected-recovered epidemic simulations indicate that our proposed method performs well and stably in single initial spreader scenarios associated with various complex network datasets.


---

## Body

## 1. Introduction

Network-spreading studies range from information diffusion via online social media sites, to viral marketing, to epidemic disease identification and control, among many others [1–9]. Key spreader identification strategies are being established and tested to accelerate information dissemination, increase product exposure, detect contagious disease outbreaks, and execute early intervention strategies [10]. Topological structure is a core concept in this identification process [1, 2, 11–15].Centrality measures for identifying influential social network nodes are broadly categorized as local or global [3, 7, 16]. Degree centrality (the number of nodes that a focal node is connected to) measures node involvement in a network. However, most network node researchers fail to consider global topological structures. Betweenness (which assesses the degree to which a node lies on the shortest path between two other nodes) and closeness (the inverse sum of the shortest distances from a focal node to all other nodes) are the two most widely used measures for overcoming these limitations. Influence is tied to advantageous network positions, including high degree, high closeness, and high betweenness. In simple network structures, these advantages tend to vary; in complex networks, significant disjunctures can emerge among position characteristics, so that a spreader’s location may be simultaneously advantageous and disadvantageous.Results fromk-shell decomposition analyses indicate that network nodes in core layers are capable of spreading throughout much broader areas compared to those in peripheral layers [1, 2]. Although spreading capability differs among nodes, those with similar k-shell values are perceived as having equal importance. To rank spreaders, a method called mixed degree decomposition adds otherwise ignored degree nodes to the decomposition process [3, 6, 8, 17]. Still, researchers have tended to overlook the importance of network topology and node diversity, despite their positive correlations with events such as community economic development [18].We used the concept of entropy to develop a robust and reliable method for measuring the spreading capability of nodes and identifying super-spreader nodes in complex networks. It can be used to analyze numbers of global network topological layers and local neighborhood nodes affected by specific individual nodes. Our assumption is thatk-shell decomposition [1, 2] can be used for global analysis, with high global diversity/high local centrality nodes capable of penetrating multiple global layers and influencing large numbers of neighbors in local layers of complex networks.To measure node influence, we propose a two-step framework for acquiring global and local node information within complex networks. Global node information is initially obtained using algorithms (e.g., a community detection algorithm for complex networks [5, 19, 20] or a k-shell decomposition algorithm for core/periphery network layers), after which entropy is used to evaluate network node global diversity. Next, local node information is acquired using various types of local centrality. Last, global diversity and local features are combined to determine node influence. In our experiments, spreading ability equaled the total number of recovered nodes over time. We used a susceptible-infective-recovered (SIR) epidemic simulation with various social network datasets [21–25] to compare the spreading capabilities of our proposed measure and social network local/global centralities [2, 26, 27].


## 2. Background

To represent a complex network, let an undirected graphG=V,E, where V is the network node set and E the edge set. n=V indicates the number of network nodes and m=E the number of edges. Network structure is represented as an adjacency matrix A=aij and aij∈Rn, where aij=1 if a link exists between nodes i and j, otherwise aij=0.Degree (or local) centrality is a simple yet effective method for measuring node influence in a complex network. LetCdi denote node i degree centrality. Higher values indicate larger numbers of connections between a node and its neighbors. NBhi denotes the set of node i neighbors at a h-hop distance. Node i degree centrality is therefore defined as(1)Cdi=NBhi=∑j=1naij,where NBhi is the number of node i neighbors at a h-hop distance; in most cases, h=1 [7].Betweenness centrality or dependency measures the proportion of shortest paths going through a node in a complex network.Cbi denotes node i betweenness centrality. Higher values indicate that a complex network node is located along an important communication path. Accordingly, node i betweenness centrality is defined as(2)Cbi=∑s≠t≠v∈VQstiQst,where Qsti is the number of shortest paths from node s to node t through node i and Qst is the total number of shortest paths from node s to node t [3, 7, 16].Closeness (or global) centrality measures the average length of the shortest paths from one node to other nodes. LetCli denote node i closeness centrality. Higher values indicate node location in the center of a complex network, with a shorter average distance from that node to other nodes. Node i closeness centrality is thus defined as (3)Cli=1li,li=1n·∑j=1ndij,where li is the average length of the shortest paths from node i to the other nodes and dij is the distance from node i to node j [16].k-shell decomposition [1, 2] iteratively assigns k-shell layer values to all nodes in a complex network. During the first step, let k=1 and remove all nodes where Cdn=k=1. Following removal, some remaining network node degrees may be k=1. Nodes are continuously pruned until there are no k=1 nodes. All removed nodes are assigned a k-shell value of 1. The next step is similar: let k=2, prune nodes, and assign a k-shell value of 2 to all removed nodes. Repeat the procedure until all network nodes are removed and assigned k-shell indexes. This method reveals the significant features of a complex network—for example, all Internet nodes can be classified as nuclei, peer-connected components, or isolated components [1].The SIR epidemic model [2, 26, 27] is used in many fields to study the spreading processes of information, rumors, biological diseases, and other phenomena. The model consists of three states: susceptible (S), infective (I), and recovered (R). S nodes are susceptible to information or diseases, I nodes are capable of infecting neighbors, and R nodes are immune and cannot be reinfected. Initially, almost all network nodes are in the S set, with a small number of infected nodes acting as spreaders. During each time step, I nodes infect their neighbors at a preestablished infection rate, after which they become recovered nodes at a recovery rate of γ. The total number of nodes in an SIR model is S(t)+It+Rt=n, with S(t) denoting the number of susceptible nodes at time t, I(t) the number of infected nodes at time t, R(t)the number of recovered nodes at time t, and ρt=R(t)/N the proportion of immune nodes.


## 3. The Proposed Measure

Our two-step method for obtaining global and local node information in a complex network is illustrated in the following steps. In step 1, global algorithms (e.g., community detection, graph clustering, andk-shell decomposition) are used to analyze the global features of nodes, and results are used to compute their global diversity. In step 2, degree centrality is used to measure local node features. Global diversity and local features are then combined to determine the influence of complex network nodes.In step 1,k-shell decomposition was used as an example for obtaining global node information in a complex network, with Shannon’s entropy [28] used to calculate node k-shell values and to determine how many network layers are affected by a node. According to (4), maximum entropy indicates a case in which a node is capable of connecting with all layers of a complex network, and minimum entropy (0) indicates a case in which all node connections are in the same network layer. The k-shell entropy of node i, which ensures that its neighbors’ k-shell values are significantly more diverse, is defined as(4)EiXi=-∑j=1ksmaxpixj·log2⁡pixj,(5)pixj=xj∑j=1ksmaxxj,(6)E^iXi=EiXilog2⁡ksmax,where Xi=1,2,…,ksmax are the k-shell values of the neighbors of node i, pixj the probability of the xj-core layer of neighbors, xj the number of nodes in the xj-core layer of the complex network, and E^iXi the normalized k-core entropy required for the case under consideration.In step 2, the node’s degree centrality is used to analyze the value of local features in the complex network; the degree centralities of neighbors are also considered. High influence values indicate high degree centralities of a node and its neighbors, meaning that the node is capable of reaching the widest possible local range. The local feature of nodei is defined as(7)Lii=log2⁡∑j∈NBh=1iCdj,where Cdj is the degree centrality of neighbor j and NBh=1i is the node i neighbor set at a h-hop distance. Lii can be extended to become a “neighbor’s neighbor” version, meaning that all node i neighbors with a 2-hop distance are considered.Finally,Ei and Li are combined to denote IFi, the final influence of node i, defined as(8)IFi=Ei·Li.


## 4. Results and Discussion

Basic complex network properties and results from a network GCC structure analysis are shown in Table1. We used three network dataset classifications: scientific collaboration, traditional social, and “other.” Measures were degree, betweenness, and closeness centralities; k-shell decomposition; neighbor’s core (also known ascoreness) [29]; PageRank [30]; and our proposed method. Spreading experiment and SIR epidemic model parameters were 1,000 simulations for each dataset, 50 time steps per simulation, and with the top-1 node for each measure serving as the initial spreader. β infection rates are shown in Table 1. According to at least one study, a large infection rate makes no difference in terms of spreading measures [2]. To assign a suitable infection rate for each network dataset, rates were determined by comparing the theoretical epidemic threshold βthd with the number used in referenced studies [29]. Recovery rate was always γ=1, meaning that every node in set I entered set R immediately after infecting its neighbors.Table 1
Properties of the real-world networks used in this project. We considered only the largest connected network components when the original network was disconnected.
Network type
Network
Description
N
E
〈
c
〉
k
max
⁡
〈
k
〉
k
s
max
⁡
〈
k
s
〉
H
r
β
thd
β
Collaboration
ca-AstroPh
Coauthorship in astro-ph of arxiv.org.
17903
196972
0.63
504
22.00
56
13.11
2.99
0.20
0.02
0.02
ca-CondMat
Coauthorship in cond-mat category.
21363
91286
0.64
279
8.55
25
5.12
2.63
0.13
0.04
0.05
ca-GrQc
Coauthorship in gr-qc category.
4158
13422
0.56
81
6.46
43
4.58
2.79
0.64
0.06
0.15
ca-HepPh
Coauthorship in hep-ph category.
11204
117619
0.62
491
21.00
238
15.93
6.23
0.63
0.01
0.05
ca-HepTh
Coauthorship in hep-th category.
8638
24806
0.48
65
5.74
31
3.41
2.26
0.24
0.08
0.12
Social
Jazz-Musicians
Collaborations among 1920’s Jazz musicians.
198
2742
0.62
100
27.70
29
17.27
1.40
0.02
0.03
0.04
Email-Contacts
Email contacts in the Computer Science Department     of the University College, London.
12625
20362
0.11
576
3.23
23
1.65
34.25
−0.39
0.01
0.05
Email-Enron
Enron email dataset.
33696
180811
0.51
1383
10.73
43
5.73
13.27
−0.12
0.01
0.05
Other
CelegansNeural
Neural network of the C. Elegans nematode.
297
2148
0.29
134
14.46
10
7.98
1.80
−0.16
0.04
0.06
Dolphins
Frequent associations between 62 Dolphins.
62
159
0.26
12
5.13
4
3.16
1.33
−0.04
0.15
0.15
LesMis
Les miserables network.
77
254
0.57
36
6.60
9
4.73
1.83
−0.17
0.08
0.08
NetScience
Network science collaborations.
379
914
0.74
34
4.82
8
3.47
1.66
−0.08
0.12
0.20
PolBlogs
Political blogs.
1222
16714
0.32
351
27.36
36
14.82
2.97
−0.22
0.01
0.02
H
=
〈
k
2
〉
/
〈
k
〉
2, degree heterogeneity [32].
β
thd
=
〈
k
〉
/
〈
k
2
〉, theoretical epidemic threshold [33].Experimental results and details are shown in Figure1 and Table 2. We found that the leading group could be defined as the spreading result of measures that are larger than the maximum result minus an inaccuracy factor of 1%:(9)LG=m∣pmt≥pmaxt-err∗pmaxt,kkllllllm∈Manderr∈0,1pmaxt-err∗pmaxt,where M is the set of measures used in the experiment, pmaxt is the maximum result at time t, err is the inaccuracy rate (0.01), and time step t=50.Table 2
Comparison of simulation results from different measures (including our proposed method) in experiments using the real-world networks shown in Table1.
Network nameGiant connected component (GCC)
ρ
(
t
) and t = 50
Degree
Betweenness
Closeness
k-core
Neighbor-core
PageRank
Proposed
ca-AstroPh
0.152
1
3
0.149
9
5
0.152
1
3
0.1205
7
0.152
2
2
0.152
3
1
0.148
0
6
ca-CondMat*
0.048
6
5
0.048
7
4
0.048
0
6
0.0278
7
0.052
0
2
0.048
8
3
0.052
7
1
ca-GrQc*
0.147
1
2
0.1178
5
0.1169
6
0.145
6
4
0.147
7
1
0.0761
7
0.146
4
3
ca-HepPh
0.195
3
1
0.194
0
7
0.195
2
2
0.195
1
3
0.195
0
5
0.195
1
3
0.194
3
6
ca-HepTh*
0.1131
3
0.1063
5
0.136
9
1
0.0658
7
0.0690
6
0.1119
4
0.135
9
2
Jazz-Musicians
0.3037
5
0.305
0
4
0.3014
6
0.2191
7
0.314
9
1
0.305
5
3
0.313
9
2
Email-Contacts*
0.0487
6
0.053
3
5
0.053
8
2
0.053
5
4
0.053
8
2
0.0136
7
0.054
1
1
Email-Enron
0.1011
5
0.1009
6
0.162
0
1
0.161
8
4
0.162
0
1
0.1003
7
0.161
9
3
CelegansNeural
0.193
9
3
0.191
9
5
0.191
1
6
0.0644
7
0.192
6
4
0.201
1
1
0.197
5
2
Dolphins
0.110
7
1
0.0754
6
0.0795
5
0.0702
7
0.101
9
3
0.108
9
2
0.0897
4
LesMis
0.088
5
4
0.089
0
3
0.089
3
2
0.0792
6
0.0753
7
0.087
8
5
0.090
5
1
NetScience*
0.079
6
4
0.0483
5
0.0473
6
0.081
6
1
0.080
7
3
0.0472
7
0.081
4
2
PolBlogs*
0.134
0
3
0.0990
5
0.133
9
4
0.0871
7
0.134
7
2
0.0989
6
0.135
4
1
Inside leading group number:
9
7
9
5
11
7
12
Average rank:
3.4615
5.0000
3.8461
5.4615
3.0
4.6923
2.6153
∗Network result shown in Figure 1.
Bold: measurement result is inside the leading network group.
Subscript: rank of network in the measurement.Figure 1
Spreading dynamic results for different networks. Measurements shown are betweenness (gray), closeness (orange), degree (yellow),k-core (blue), proposed method (cyan), neighbor-core (magenta) and PageRank (red).
(a)
ca-CondMat
(b)
ca-GrQc
(c)
ca-HepTh
(d)
Email-Contacts
(e)
NetScience
(f)
PolBlogsThe number of recovered nodesρt was used to measure and rank the spreading capability of various measures. The leading group can help determine measure stability for identifying the influence of nodes in different networks. Measures inside the leading group had approximately the same spreading capability. The average rank shown in Table 2 was used to interpret the expected rank in different networks: a measure with a lower average rank was viewed as having better discrimination in terms of identifying good spreaders.According to the inside leading group number (a measure stability indicator), our proposed method performed well in terms of identifying the most influential network nodes and thus is capable of identifying nodes that serve as good spreaders with global diversity in a complex network. In addition to being within the leading group, the method also had a better ranking compared to other measures within that group. The identified influence spreaders were capable of reaching large numbers of network nodes through their diverse global connections, of affecting network layers, and of exerting a maximum spreading effect. Our results also indicate that the degree centrality of a node and its neighbors can be used to maintain the number of contact nodes in the local layer of a complex network. However, important differences were noted among measures. For example, the closeness measure performed well in the top-1 position of the ca-HepTh and Email-Enron networks (Figure1, Table 2), but not in the ca-GrQc, jazz_musician, or NetScience networks. Since the characteristic the measure wanted to capture may not have been sufficiently strong in those networks, the most influential spreaders could not be identified.Although our proposed method underscores the robustness and stability of identifying the most influential nodes, we acknowledge two limitations. First, in cases of global node diversity and lower node degree centrality, the spreading capability of nodes is constrained and dependent on the degree centrality of their neighbors. The influence of a node is limited to the local layer of a complex network when the degree centrality of its neighbors is lower. The spreading range is also limited when a node’s connected neighbors are located in the network’s peripheral layer. However, the spreading range of nodes may be wide when the node’s neighbors are located near the hub and within the core network layers and when information and ideas can still be spread to infect a large number of nodes throughout the network.Second, maximumk-shell values are lower and network sizes are considerably smaller in the absence of global diversity in a complex network. As shown in Table 2, nodes with high global diversity in the Dolphins network could not be identified. In that case, the spreading ability of nodes identified by our proposed method decreased to the degree centrality (ignoring the first term), and the influence of nodes was limited to local network layers. In the absence of global diversity, (8) becomes IFi≈Li, which favors local network layers (i.e., degree centrality). The spreading ranges of nodes were also limited to local network layers when nodes were located in peripheral layers or inside local and dense clusters. However, broad spreading ranges were observed for nodes located in the network’s core layers [2]. In addition, the E^iXi normalized global diversity values produced by our proposed method are similar to the participation coefficients reported by Teitelbaum et al. [31], and the high global diversity values of nodes that we observed are similar to those of connector hubs and kinless hubs, both of which have distinct participation coefficients.


## 5. Conclusion

Our plans are to add considerable detail to our analysis, to introduce a sophisticated method for evaluating spreading ability, and to clarify how the proposed method is affected by network structure. For example, global algorithms such as community detection algorithms can be used to analyze and obtain global information on community network structures and to determine how factors such as position and node role [31] affect the degree to which spreaders distribute information or diseases throughout a complex network. We also plan to study strategies associated with multiple initial spreaders in networks. Since overlapping infected areas for selected spreaders must be minimized [2], a multiple initial spreader scenario may either accelerate or hinder spreading within a complex network.



---

*Source: 675713-2015-06-08.xml*