# Ranking Spreaders in Complex Networks Based on the Most Influential Neighbors

Authors: Zelong Yi; Xiaokun Wu; Fan Li
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

Identifying influential spreaders in complex networks is crucial for containing virus spread, accelerating information diffusion, and promoting new products. In this paper, inspired by the effect of leaders on social ties, we propose the most influential neighbors’k-shell index that is the weighted sum of the products between k-core values of itself and the node with the maximum k-shell values. We apply the classical Susceptible-Infected-Recovered (SIR) model to verify the performance of our method. The experimental results on both real and artificial networks show that the proposed method can quantify the node influence more accurately than degree centrality, betweenness centrality, closeness centrality, and k-shell decomposition method.


---

## Body

## 1. Introduction

Identifying influential spreaders is of theoretical and practical significance in understating the dynamics of spreading in a complex network. It is conducive to containing epidemic spread, studying information dissemination, and controlling virus diffusion [1–14]. In this view, researchers have developed various methods, such as degree centrality (DC) [15], betweenness centrality (BC) [16], closeness centrality (CC) [17], and semilocal centrality [18] to identify the most influential spreaders in a network.Kitsak et al. [1] argue that the most efficient spreaders are located at the core of a network. By using the k-shell decomposition (KS) analysis [19–21], the location of each node is defined as an integer index, k-shell value, according to successive layers in a network. A small k-shell value represents the periphery of the network while a large k-core value defines the most influential neighbors; however, many nodes with an identical k-core value have different spreading influence. In other words, the k-shell method manifests a relatively low performance of monotonicity. To address the issue, many other methods have been proposed to improve the effectiveness of the k-shell method. For example, Zeng et al. designed a mixed degree decomposition method [22] to rank spreaders according to the links connecting to both the remaining nodes and the removed nodes. Bae et al. [23] defined a coreness centrality index by summing all neighbors’ k-shell values and subsequently found that this method provides a more monotonic ranking list than other ranking methods. Ma et al. [24] proposed a gravity model by considering the k-shell value of each node as its mass and the shortest distance between two nodes in a network as their distance.In this paper, we propose a novel influence measure, the most influential neighbors’k-shell (MINK) method to quantify the spreading capability of a node. Here, we refer to the nodes with the largest k-shell value as the most influential neighbors. Inspired by the effect of the leaders on social ties, we identify a spreader’s influence by focusing on its interaction with the most influential neighbors. By using the k-shell method to define the most influential neighbors, our proposal also takes into account a node’s complex integration with other nodes in the network. It is worth noting that, compared with the gravity model that considers the interaction with a node’s neighbors within a given distance valuer, MINK is unacted on the influence of subjective parameters. According to structural holes theory [25], structural equivalence occurs among a node’s neighbors in networks that are lacking in structural holes (“structural holes” are network gaps between unconnected nodes, creating opportunities for unique information access and control), which is to say that the neighbors tend to have strong ties with each other and bring redundant information to the node. The MINK index originates from the idea that generally an influential neighbor has more unique information and therefore exerts more influence on a node’s spreading capacity than other neighbors. In this case, the MINK index, which excludes repeated information from its less influential neighbors, is more refined and less costly in computation.The rest of this paper is organized as follows. We briefly review previous studies and present our method in Section2. In Section 3, we apply the Susceptible-Infected-Recovered (SIR) model to evaluate the performance of our proposed method in both real and synthetic example networks. Conclusion is provided in Section 4.


## 2. The MINK Index

Normally, a networkG=(N,E) with N nodes and E edges can be described by an adjacent matrix A=(aij)N×N, where aij=1 if node i is connected to node j, and aij=0 otherwise. For the sake of simplicity, G is viewed as an undirected, unweighted, and simple network.The degree centrality, based on local information, defines the influence of a node as the number of its adjacent vertices. The degree of a node can be expressed as follows:(1)DCi=∑j=1naij.The betweenness centrality measures the fraction of all shortest paths between each node pair which passes through the considered node i. It can be described as (2)BCi=∑s≠t≠instinst,where nst denotes the total number of shortest paths between vertexs and vertex t and nst(i) stands for the number of shortest paths from s to t travelling through vertex i. The higher the score ranked by the method is, the more likely a node is a hub vertex, which is an information transfer station in a network.The closeness centrality is introduced to measure how long the information possessed by a node will propagate in a network. The closeness centrality of nodei is defined as the reciprocal of the average of shortest distances to all the other nodes:(3)CCi=N∑j=1ndij,where N is the number of all nodes and dij stands for the geodesic distance between vertex i and vertex j.Bao et al. [18] put forward a semilocal centrality by including the effects of shortest distance, the number of shortest paths, and the transmission rate simultaneously, which is defined as(4)SPi=∑j∈ψinij1kdij,where nij is the number of shortest paths between nodes i and j, 〈k〉 denotes the average degree of the network, and ψi is the neighborhood set whose distance to node i is less than or equal to a coverage radius r. Specifically, r=3 is set in literature [18].Thek-shell decomposition method [1] endows all nodes with a corresponding k-shell value by removing nodes iteratively as follows. First, we start with removing all nodes with degree DC=1 and continue dropping the remaining nodes until no node with DC=1 exists in the network. All nodes removed are assigned with k-shell valueKS=1. Secondly, we iteratively remove all nodes with degree DC=2 until no node withDC=2 exists in the network. All of these removed nodes are assigned with KS=2. Next, we repeat this process until all nodes are removed and assigned with a corresponding k-shell value. In the end, each node is defined by the KS index, according to its relative topological location in the network.However, by using thek-shell decomposition, too many nodes with different spreading influences turn out to be assigned to the identical KS index. To improve the monotonicity of the k-shell decomposition, we propose most influential neighbors’ k-shell (MINK) index, which is inspired by the effect of the leaders on the social ties. Specifically, leaders in social networks share information, provide advice, assign work, and collaborate with other members in the networks. The influence of other members on the network is highly determined by their connection to the leaders. Therefore, we measure the spreading ability of a node based on the interaction of its influential neighbors characterized by the largest k-shell values. On one hand, a node will have a greater influence if its most influencing neighbor or itself has a higher value of KS; on the other hand, the effect increases as their distance shortens. In this way, the influence of node i is measured by(5)MINKi=∑j∈ΛiKSiKSjdij2,where dij is the shortest path distances between node i and node j and Λi is the set of spreaders with the maximum k-shell value.


## 3. Empirical Results

Susceptible-Infected-Recovered (SIR) model [26] is a simulation process to mimic the epidemic spreading. It is widely used in identifying the spreading capacity of nodes by scholars and adopted in the study of vaccination strategy and infection control [27–29] as well. In principle, the SIR model detects the influential vertices due to the fact that key nodes are more likely to play an indispensable role in information and viral transmission, and thereby an effective ranking is supposed to stand the test of real spreading coverage.Therefore, we employ the standard SIR model herein to evaluate the performance of our proposed model. It starts from setting a node as an infected node and the remaining nodes as suspected nodes. At each step, the infected node will infect its susceptible neighbors at the spreading rateα and then it will recover with probability μ. The process continues until all infected nodes are recovered with no infected nodes left in the network. The spreading influence of a node can be obtained by calculating the number of infected nodes at the end of the process. In the paper, we set μ=1 and α∈(0,0.1]. By using this relatively small infection probability, we avoid the situation where most nodes of a network will be inflected easily so that the different influence of each node cannot be detected.To check the performance of our proposed method, six real networks are introduced in this paper, including Dolphins (friendship) [30], USAir97 (US air flights network), C.elegans (neural) [31], Email (communication) [32], PGP (an encrypted communication network) [33], and Internet (router level). For simplicity, we view these networks as simple undirected and unweighted networks. The statistical properties of the six real networks are listed in Table 1, including the number of nodes N, edges E, the degree heterogeneity H, the degree assortativity r, the clustering coefficient C, and the average shortest path length L.Table 1
Structural properties of the six real networks, including the number of nodesN, edges E, the degree heterogeneity H, the degree assortativity r, the clustering coefficient C and the average shortest path length L.
Networks N E H r C L Dolphins 62 159 1.3268 -0.0436 0.2590 3.3570 C.elegans 297 2148 1.8008 -0.1632 0.2924 2.4553 USAir97 332 2126 3.4639 -0.2079 0.6252 2.7381 Email 1133 5451 1.9418 0.0782 0.2202 3.6060 PGP 10680 24316 4.1465 0.2382 0.2659 7.4855 Internet 22963 48436 61.9778 -0.1984 0.2304 3.8424Next, applying these real networks, we compare the effectiveness of our proposed method with degree centrality, thek-shell method, betweenness centrality, and closeness centrality. Both the resolution and correctness of these different ranking methods are studied, respectively.First, following the literature [24], we define the monotonicity index M(x) to quantify the resolution of different ranking methods, as follows: (6)Mx=1-∑c∈VNcNc-1NN-12,where N is the size of the network and NC is the number of the nodes with the same ranking result c when implementing an algorithm. By definition, a ranking method with the monotonicity index closer to 1 has a higher resolution to distinguish nodes’ different influence. If M(x)=1, the ranking method is perfectly monotonic, and each node is identified by a different index value. The monotonicity indexes for different ranking methods are summarized in Table 2. The results suggest that our proposed method can generate higher resolution values than degree centrality, the k-shell method, and betweenness centrality do in all six of the real networks. M(x) is close to 1 in networks C.elegans, Dolphins, and Internet. In addition, we find out that although the k-shell method may identify the most influential spreaders, its resolution is relatively low in these six networks, implying that the different influences of spreaders are not classified. This means that it is necessary to develop alternative methods to overcome the disadvantage of the k-shell method.Table 2
The value ofM(.)is the monotonicity of the corresponding measures.
Networks M ( D C ) M ( K S ) M ( B C ) M ( C C ) M ( M I N K ) Dolphins 0.8312 0.3769 0.9623 0.9737 0.9968 C.elegans 0.9217 0.6094 0.9931 0.9893 0.9965 USAir97 0.8906 0.8114 0.697 0.9892 0.964 Email 0.8874 0.8088 0.9400 0.9988 0.9804 PGP 0.6193 0.4806 0.5099 0.9996 0.9858 Internet 0.4807 0.4261 0.5330 0.9973 0.9926Secondly, Kendall’s tau rank correlation coefficient(τ) [34] is used to quantify the correctness of the ranking methods. Let (xi,yi) and (xj,yj) be a pair of joint observations that are randomly selected from ranking lists X and Y. The observations (xi,yi) and (xj,yj) are concordant, if both xi>xj and yi>yj or if both xi<xj and yi<yj. They are said to be discordant, if xi>xj and yi<yj or if xi<xj and yi<yj. If xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s tau coefficient is defined as (7)τ=N1-N20.5NN-1,where N1 is the number of concordant pairs, N2 is the number of discordant pairs, and N is the size of a network. Kendall’s tau τ is within [-1,1], and the large values imply a higher level of correlation between the SIR model and the compared method. Kendall’s tau τ is affected by the network infection rate. In this paper, we set the infection rate α∈(0,0.1] to derive Kendall’s tau τ different under infection rates. Note that the inflection rate cannot be too large, because, with a large α, the whole network will be easily infected so that the influences of different notes cannot be distinguished. The average values of Kendall’s tau τ under α∈(0,0.1] for different ranking methods are summarized in Table 3. The results indicate that our proposed model outperforms existing models generally and it is effective especially in networks USAir97 and C.elegans.Table 3
τ ( . ) is the average value of the Kendall’s tau τ under different infection rates.
Networks τ ( K S ) τ ( D C ) τ ( B C ) τ ( C C ) τ ( M I N K ) Dolphins 0.5936 0.8661 0.5967 0.5491 0.7532 C.elegans 0.6947 0.7795 0.6091 0.6413 0.8372 USAir97 0.7737 0.7569 0.5275 0.7815 0.8836 Email 0.6096 0.6704 0.6384 0.7898 0.7523 PGP 0.4670 0.5236 0.3405 0.5794 0.6376 Internet 0.4328 0.4095 0.2166 0.7296 0.7173We also show how Kendall’s tauτ changes in the infection rate α for different methods in Figure 1. As described in Figure 1, in most cases, our proposed method achieves a better performance than other methods. As the infection rate increases, Kendall’s tau τ using the k-shell method is positively correlated with the τ value using our method generally, but the former τ is less than the latter τ. This implies that our method yields higher correctness than does the k-shell method.Figure 1
Kendall’s tau rank correlation coefficients under different infection ratesα for real networks.Besides real networks, we also check the effectiveness of our methods on a typical synthetic network using the Barabási-Albert (BA) model [35]. Creating the BA network starts with a network with m0 nodes. Then, at each step, a new node is added to the network and connected to existing m(m<m0) nodes according to the preferential attachment mechanism. In this paper, we set m=3and m0=1000.For the BA network, we calculate Kendall’s tau rank correlation coefficients for DC, CC, BC, and our proposed model. Figure2 shows that MINK performs better than CC and much better than DC and BC. Note that all nodes in the BA network are assigned with the same k-shell value, so we do not consider the k-shell method in our comparison. The average tau values using different methods are listed in Table 4. The results indicate that our model outperforms existing models.Table 4
τ ( . ) is the average value of the Kendall’s tau τ under different infection rates for the BA network.
Networks τ ( D C ) τ ( B C ) τ ( C C ) τ ( M I N K ) BA 0.3052 0.3833 0.7123 0.7354Figure 2
Kendall’s tau rank correlation coefficients under different infection ratesα for the BA network.


## 4. Conclusion

In this paper, we propose the MINK index to measure the ability of spreaders in complex networks using the neighbors with the largestk-shell values. Our method is based on the facts that a node's spreading ability is proportional to the k-shell values of itself and its most influential neighbors and decreases with the distances between itself and these neighbors. By using real networks and a synthetic network using the BA model, we compare our method with the degree centrality, the betweenness centrality, the closeness centrality, and the k-shell decomposition method. The empirical results suggest that our method produces a more monotonic ranking than the degree centrality, the k-shell method, and the betweenness centrality in all six real networks. Moreover, in most cases, the ranking result of our method is highly correlated with the epidemic spreading range compared with other well-known methods.Some limitations of our method need to be addressed. First, we only investigated the performance of our method in some typical networks and the classical SIR model was used to mimic the epidemic spreading process. In practice, the structure of a network and spreading dynamic can be different. Thus, the effectiveness of this method needs to be tested more generally. Second, our MINK index is weighted by the distance between a node and its most influential neighbors, but this distance cannot be calculated if these nodes are not connected. Therefore, our method is not appropriate in identifying spreaders’ influence in an unconnected network.



---

*Source: 3649079-2018-08-23.xml*