# Identification of Influential Nodes via Effective Distance-based Centrality Mechanism in Complex Networks

Authors: Aman Ullah; Bin wang; Jinfang Sheng; Jun Long; Nasrullah Khan
Journal: Complexity
 (2021)

---

## Abstract

Efficient identification of influential nodes is one of the essential aspects in the field of complex networks, which has excellent theoretical and practical significance in the real world. A valuable number of approaches have been developed and deployed in these areas where just a few have used centrality measures along with their concerning deficiencies and limitations in their studies. Therefore, to resolve these challenging issues, we propose a novel effective distance-based centrality (EDBC) algorithm for the identification of influential nodes in concerning networks. EDBC algorithm comprises factors such as the power of K-shell, degree nodes, effective distance, and numerous levels of neighbor’s influence or neighborhood potential. The performance of the proposed algorithm is evaluated on nine real-world networks, where a susceptible infected recovered (SIR) epidemic model is employed to examine the spreading dynamics of each node. Simulation results demonstrate that the proposed algorithm outperforms the existing techniques such as eigenvector, betweenness, closeness centralities, hyperlink-induced topic search, H-index, K-shell, page rank, profit leader, and gravity over a valuable margin.


---

## Body

## 1. Introduction

In recent years, complex networks are an attractive and hot research area by virtue of its wide range of practical and theoretical applications in many major fields [1–5]. Several real-world application areas such as management science, chemistry, economics, and financial systems [6, 7], computer science, biological science [8, 9], and many other similar fields can be regarded as complex networks [10, 11]. Finding the most important nodes is helpful to efficiently analyze the entire network, such as controlling the spreading of disease, detecting the most vital node of the disease transmission rapidly can control the spreading of disease, and erecting a new marketing tool [12–15]. Some of the existing commonly used approaches to identify the influential nodes are closeness centrality (CC) [16], degree centrality (DC) [17], betweenness centrality (BC) [18], information centrality (IC) [19], load centrality(LC) [20], eigenvector centrality(EC) [21], page rank (PR) [22], H-index [23], K-shell decomposition, hyperlink-induced topic search (HITS) [24, 25], and so on. Several algorithms are usually not precise, but precise algorithms have comparatively high computational time complexity. For example, DC is a very simple method of finding influential nodes, but it only considers limited information. Therefore, it is not suitable in some cases. Similarly, BC and CC are not applicable in large networks because of their high computation time complexity. PR is based on global information, so it works very well in directed networks but is not suitable for undirected ones [26]. Similarly, the K-shell algorithm takes into account the core or periphery position of the nodes in the networks to investigate influential nodes. It is a straightforward index mechanism for finding the influential nodes; due to its low complexity, it can be applied in large-scale networks, although it cannot differentiate among the key nodes in the same core layer [27–29]. All in all, the above existing approaches have low accuracy of ranking and are ineffective for some networks. There are numerous ranking approaches for influential or key nodes identification, but it is not easy to find all influential nodes. Frequently, two types of models are used to evaluate ranking results of important nodes: (i) SIR model [30] and (ii) Kendall’s correlation coefficient τ [31]. The main job of the SIR model is to choose the top-k ranking node’s results as seed nodes. When the selected seed nodes or vertices of a technique make the flow of network spread faster, then the technique is said to be better than the other techniques. For measurement between two ranking results, Kendall’s correlation coefficient τ is used. If Kendall’s correlation coefficient τ is positive, then it means the two rankings are positively correlated, and if Kendall’s correlation coefficient τ is negative, then the two rankings are negatively correlated. If the coefficient is 1, it means the rankings are the same, and if it is -1, it means the rankings are completely opposite. The technique is said to be more accurate when Kendall’s correlation coefficient τ is higher. From the above discussion, we propose a new, efficient, and effective method termed as EDBC algorithm for key or influential nodes identification in complex networks. EDBC comprises effective distance, K-shell, nodes degree, and many other levels of neighbor influences or neighborhood potential-like factors. We applied EDBC on nine different real-world networks. The simulation results proved that our algorithm is better than other conventional algorithms, including newly developed algorithms such as gravity centrality and profit leader, which were, respectively, developed in 2017 and 2018.The core contribution of the proposed EDBC algorithm is summarized as follows. (1) A new ranking centrality perspective: from the last two decades, several models and algorithms regarding the identification of influential or key nodes have been developed but still it is a challenge. In this regard, we propose a novel effective distance-based centrality algorithm which is comprising of several features to have experimented on unweighted networks and structure to sort out the important nodes. (2) Accuracy: we have compared the proposed algorithm with various ranking methods where experiments have shown that EDBC is comparatively more effective and efficient algorithm. Through rendering comprehensive experiments on nine real-world networks, the EDBC has outperformed various existing algorithms such as BC, CC, EC, PR, HITS, H-index, K-shell, GR, and PL. (3) Parameter-free : the proposed EDBC neither depends on prior knowledge nor relies on adjustments of parameters. It has its own way to quickly and efficiently identifying the key nodes. (4) Applicability: the proposed EDBC reduces the calculation cost as its basis on two-stage neighbor nodes. Therefore, its application is appropriate on any type of networks, i.e., directed or undirected networks.The rest of this paper is organized as follows. In Section2, we present overviews of the related work. In Section 3, we discuss the proposed EDBC algorithm, whereas its performance evolution is discussed in Section 4. Finally, we elaborate conclusion and future recommendations in Section 5.


## 2. Related Work

The criterion of detecting the most important nodes in complex networks is one of the challenging issues from the past few decades. Two types of centrality measures can be used for identification of key nodes, i.e., (i) matrix-based centrality such as random walk matrix [32], Laplacian matrix [33], and adjacency matrix [34] (ii) superficial-based properties such as CC, BC, DC, and motif centrality measurement [35]. Currently, a vast number of studies have been offered regarding the identification of the key nodes, e.g., node removals, profit leader [36], and local neighbor contribution [3]; these studies have their own advantages and disadvantages. Zhong-Kui Bao et al. [37] proposed heuristic clustering (HC) method of detecting the most influential nodes; HC works on the basis of similarity index which categorizes nodes into various clusters; in this way, the center nodes in clusters are taken as multiple spreaders. Hongming Mo et al. [38] proposed an evidential method for the influential node identification, which is based on the Dempster–Shafer evidence theory. Furthermore, Bian and Yong [39] introduced a new evidential centrality (NEC) algorithm, which is the extension of the evidential method. Tian et al. [40] proposed an analytic hierarchy process (AHP), which works on the basis of multiple attribute decision-making (MADM) method; AHP is used to detect the important branch of every decision and choose the best nodes in the entire network. Zeng et al. [41] have proposed a mixed degree decomposition algorithm for finding ranking nodes; however, the limitation of this technique is the high time complexity and high degree peripheral nodes. Lin et al. [42] improve the K-shell decomposition method; they consider the shortest distance among the nodes and set of nodes by high index K-shell. For further improvement of the K-shell decomposition method, Bae et al. [43] suggested neighborhood coreness centrality (cn) and extended neighborhood coreness (cn+) algorithms. In [44], authors proposed a centrality method for influential nodes identification, which is based on gravity formula. In this method, mass is replaced by the K-shell value of each node and the distance is the shortest path between two nodes. According to the authors, the proposed gravity-based method has better results than other existing methods. Liu et al. [45] proposed a weight degree centrality measure method, which considered the degree of nodes, neighborhoods of their nodes, and one tuning parameter. They compared the proposed WDC algorithm with other various algorithms such as BC, DC, K-shell decomposition, neighborhood coreness, and extended neighborhood coreness methods. A neighborhood centrality method was proposed by Liu et al. [46] for influential nodes identification, which cogitates numerous neighbors’ level influence factors that are based on benchmark centrality measures. On the contrary, there were some indexing centrality methods which are based on edges’ potential to enhance the effectiveness of ranking centrality measures [47, 48]. Pei et al. [49] have claimed that the K-shell decomposition algorithm performs well for finding key nodes in the entire real network. In [50], a bio-inspired centrality method was proposed, which combines the K-shell index, with Physarum centrality to identify key nodes. Gomez et al. [51] improve the BC centrality method to take into account explicitly numerous dimensions. Furthermore, Zang et al. [52] proposed an advanced unbiased betweenness centrality method, which considers a reverse propagation algorithm to choose the key nodes in the real network. There have been numerous studies to improve the existing algorithm for influential nodes identification. Though, all these studies have their own advantages and disadvantages. Still, efficient and effective influential nodes identification persists as a nontrivial challenge. Inspired from [44, 53], we proposed an efficient algorithm called EDBC, which effectively identifies the highly influential nodes in various scales of complex networks.


## 3. EDBC Model

In this section, we discuss some basic concepts about the proposed method. The proposed method considers the degree of nodes, effective distance, power of K-shell, and several levels of neighborhood nodes influences. EDBC calculation is presented in Sections3.1 and 3.2.


### 3.1. Preliminaries

Definition 1.
(degreedvi). In graph theory, the degree of a node denotes the number of all connected edges in the node, that is, the sum of all connected edges in the network. In graph G, set A=Aij|i,j=1…N denotes the adjacency matrix of G which is defined as follows:(1)dvi=∑j=1Naij,where represents node degree,vi, and aij indicates the element of A.Definition 2.
(power of K-shellαi,j). We consider the nodes i and j for K-shell (ksi and ksj). We add ksi and ksj in equation (2) for the measurement of power influences:(2)αi,j=ksi+ksj,where ksi and ksj represent the K-shell of node i and node j. Here, we used the square root for normalization of the influence factor for the power of K-shell.Definition 3.
(effective distanceEDi,j, see [54]). Effective distance is an essential parameter in the networks G=N,M spreading process, and we employ this parameter in the EDBC algorithm. For calculating the distance between the nodes, we have not used the existing distance path algorithm such as Dijkstra and the Bellman–Ford algorithm because the time complexities of these algorithms are very high. For this purpose, we propose effective distance between the nodes, which can be calculated through the following formula:(3)EDi,j=1−logPji≥1,where Pji denotes the flow of information ratio from node Vj to Vi: Pji=aji/∑iεΨjaji. As can be seen from the formula, EDi,j≠EDj,i.Definition 4.
(influenceIi,j). Normally, when the neighbors of nodes have high influence, then nodes’ influences will increase automatically. Besides, the influence of nodes on neighbors will be decreased with an increase of shortest distances among them. Inspired from inverse square law, we can compute the influence of node as follows:(4)Ii,j=∑jεηiαi,j+dviEDi,j2.
The sum of node influence on all neighbor nodes, which measure the influence of that node, which can be calculated as follows:(5)EDBCi=∑jεηiIi,j,where ηi is the set of nearest all neighbors node i.
Algorithm1 depicts the working mechanism of our proposed solution.Algorithm 1: EDBC.
Input:G=N,M;(1)
for each node v in G = (N, M) do(2)
calculate the degree of v(3)
calculate the K-shell of v(4)
//Computing the interaction in the most nearest neighbors nodes(5)
for node u in G.neighbors of node vdo(6)
evaluate the power of K-shell (v) using equation (2)(7)
evaluate the power of K-shell (u) using equation (2)(8)
evaluate ED(v,u) using equation (4)(9)
evaluate influence(v,u) using equation (5)(10)
//Computing the interaction in the next-nearest neighbors’ nodes(11)
for node w in G.neighbors of node udo(12)
evaluate the power of K-shell (v) using equation (2)(13)
evaluate the power of K-shell (w) using equation (2)(14)
evaluate ED(v,w) using equation (3)(15)
evaluate influence(v,w) using equation (4)(16)
end for(17)
end for(18)
end for(19)
//Calculate influence I(v) of all neighbours’ nodes(20)
evaluate EDBC(v) using equation (5)(21)
return EDBC(v)Output: Ranked nodes


### 3.2. EDBC Algorithm

The node influence in a network depends on three aspects. (i) The node location in the network when a node is in the center of the network, and the influence will be high. Otherwise, if the node is located on the edge of the network, the influence will definitely be relatively small. (ii) The number of node neighbors: a large number of neighbors will be the greater influence of the node. (iii) The distance between the nodes: the smaller the distance is, there is a greater probability of information transmission between nodes and its neighbors. On this basis, we proposed EDBC algorithm, as described in section1. The proposed EDBC algorithm mainly comprises factors such as the power of K-shell, degree nodes, effective distance, and numerous levels of neighbor influence. At the first stage, it calculates the degree and K-shell of nodes in network, and then, it finds the power of K-shell according to equation (2). Furthermore, it calculates the distance between the nodes (nearest and next-nearest neighbors) through equation (3), and finally, it calculates the influence of each node using equations (4) and (5). To further demonstrate the EDBC algorithm over a specific calculation process, we consider a simple network to provide a clear and detailed picture of the proposed methodology. Figure 1 presents a synthetic network with 16 nodes and 21 edges, where node V16 has a higher influence than other nodes in the network. Moreover, a control flowchart of EDBC algorithm is also presented through Figure 2, where, in the first phase, we have constructed a concerning network; then, we calculate the degree and K-shell of each node; after that, we calculate the power of K-shell as well as effective distance that only considers the nearest and the next-nearest neighbors nodes. At the last step, influence of each node in the entire network is hereby calculated.Figure 1
A simple network with 16 nodes and 21 edges.Figure 2
The flowchart of the proposed EDBC.


#### 3.2.1. Computation of the Power of K-Shellαi,j

For calculating the power of K-shell, here we apply equation (2). For node V16, the K-shell value is 2; first of all, we calculate the K-shell of node i and node j. Table 1 shows the K-shell of given toy network. We have α16,9=2+2=2, α16,7=2+2=2, and α16,2=1+2=1.7320. Similarly, in this way, other K-shell power can be calculated.Table 1
K-shell and degrees of each node in a toy network.
Node17234596161581113121014Degree1611124282313313Core number/K-shell1211122222212212


#### 3.2.2. Calculation of the Effective Distance

ED (between nearest and next-nearest neighbor of nodes) depends on the closeness among the nodes and its neighbors, to calculate effective distance among the neighbors and the next neighbors of V16 by using equation (3):(6)ED16,9=1−logP9,16=1.903,where(7)P9,16=1d16=0.125.Now, to calculate the distance between the next neighbors ofV16, the distance can be(8)ED16,7=ED16,9+ED7,9,ED16,7=1.903+1−logP9,7=1.903+1.7783=3.6813.Similarly,(9)ED16,5=ED16,9+1−logP9,5=1.903+1.301=3.204.


#### 3.2.3. Calculation of the Neighbor Nodes’ Influence

In this context, EDBC algorithm considers only the nearest and the next-nearest neighbor’s nodes. Here, we take V9 as an example of the nearest neighbor node, according to equation (4):(10)I16,9=α16,9+d16ED16,92=2.7614,where d16 is the degree of V16, which is 8. Now, we take the next-nearest neighbor of V9. Therefore, the influence of node V16 to node V7 or node V5 can be computed as follows:(11)I16,7=α16,7+d16ED16,72=0.7379.By this rule, all the nearest and next-nearest neighbor’s nodes of the influence with V16 can be calculated.


#### 3.2.4. Computation of the Influence for Each Node

The computation of the total influence of the nodes in the entire network means the sum of the total number of influence nodes on the nearest and next-nearest neighbor nodes. By using equation (5), we can compute the total influence of the node V16 for a given graph:(12)EDBCV16=∑jεΨI16,j+∑kεi,k≠1I16,k=57.6251,where j and k show the nearest and next-nearest neighbor nodes. Applying all of the above procedure, we get all nodes influence the ranking results of the given toy network, as shown in Table 2.Table 2
The influence ranking results using EDBC of the given toy network.
Node167912814136155101Influence57.645.937.427.226.425.224.718.918.917.815.910.7


### 3.3. Computational Complexity

EDBC takes three components. In the first phase, it calculates the degree and K-shell, so the time complexity becomesOM. In the second phase, it computes the effective distance among the nodes and their adjacent or neighbors. The distance between the nearest and next-nearest neighbors in the entire network is calculated. Therefore, the computational time complexity is O N<K>2, and in the third and fourth phases, the node’s influence of all neighbors will be calculated. Therefore, EDBC algorithm’s total time complexity can become ON<k>2+M, where N and k denote the number of nodes and average degree of nodes in the network, respectively.


## 3.1. Preliminaries

Definition 1.
(degreedvi). In graph theory, the degree of a node denotes the number of all connected edges in the node, that is, the sum of all connected edges in the network. In graph G, set A=Aij|i,j=1…N denotes the adjacency matrix of G which is defined as follows:(1)dvi=∑j=1Naij,where represents node degree,vi, and aij indicates the element of A.Definition 2.
(power of K-shellαi,j). We consider the nodes i and j for K-shell (ksi and ksj). We add ksi and ksj in equation (2) for the measurement of power influences:(2)αi,j=ksi+ksj,where ksi and ksj represent the K-shell of node i and node j. Here, we used the square root for normalization of the influence factor for the power of K-shell.Definition 3.
(effective distanceEDi,j, see [54]). Effective distance is an essential parameter in the networks G=N,M spreading process, and we employ this parameter in the EDBC algorithm. For calculating the distance between the nodes, we have not used the existing distance path algorithm such as Dijkstra and the Bellman–Ford algorithm because the time complexities of these algorithms are very high. For this purpose, we propose effective distance between the nodes, which can be calculated through the following formula:(3)EDi,j=1−logPji≥1,where Pji denotes the flow of information ratio from node Vj to Vi: Pji=aji/∑iεΨjaji. As can be seen from the formula, EDi,j≠EDj,i.Definition 4.
(influenceIi,j). Normally, when the neighbors of nodes have high influence, then nodes’ influences will increase automatically. Besides, the influence of nodes on neighbors will be decreased with an increase of shortest distances among them. Inspired from inverse square law, we can compute the influence of node as follows:(4)Ii,j=∑jεηiαi,j+dviEDi,j2.
The sum of node influence on all neighbor nodes, which measure the influence of that node, which can be calculated as follows:(5)EDBCi=∑jεηiIi,j,where ηi is the set of nearest all neighbors node i.
Algorithm1 depicts the working mechanism of our proposed solution.Algorithm 1: EDBC.
Input:G=N,M;(1)
for each node v in G = (N, M) do(2)
calculate the degree of v(3)
calculate the K-shell of v(4)
//Computing the interaction in the most nearest neighbors nodes(5)
for node u in G.neighbors of node vdo(6)
evaluate the power of K-shell (v) using equation (2)(7)
evaluate the power of K-shell (u) using equation (2)(8)
evaluate ED(v,u) using equation (4)(9)
evaluate influence(v,u) using equation (5)(10)
//Computing the interaction in the next-nearest neighbors’ nodes(11)
for node w in G.neighbors of node udo(12)
evaluate the power of K-shell (v) using equation (2)(13)
evaluate the power of K-shell (w) using equation (2)(14)
evaluate ED(v,w) using equation (3)(15)
evaluate influence(v,w) using equation (4)(16)
end for(17)
end for(18)
end for(19)
//Calculate influence I(v) of all neighbours’ nodes(20)
evaluate EDBC(v) using equation (5)(21)
return EDBC(v)Output: Ranked nodes


## 3.2. EDBC Algorithm

The node influence in a network depends on three aspects. (i) The node location in the network when a node is in the center of the network, and the influence will be high. Otherwise, if the node is located on the edge of the network, the influence will definitely be relatively small. (ii) The number of node neighbors: a large number of neighbors will be the greater influence of the node. (iii) The distance between the nodes: the smaller the distance is, there is a greater probability of information transmission between nodes and its neighbors. On this basis, we proposed EDBC algorithm, as described in section1. The proposed EDBC algorithm mainly comprises factors such as the power of K-shell, degree nodes, effective distance, and numerous levels of neighbor influence. At the first stage, it calculates the degree and K-shell of nodes in network, and then, it finds the power of K-shell according to equation (2). Furthermore, it calculates the distance between the nodes (nearest and next-nearest neighbors) through equation (3), and finally, it calculates the influence of each node using equations (4) and (5). To further demonstrate the EDBC algorithm over a specific calculation process, we consider a simple network to provide a clear and detailed picture of the proposed methodology. Figure 1 presents a synthetic network with 16 nodes and 21 edges, where node V16 has a higher influence than other nodes in the network. Moreover, a control flowchart of EDBC algorithm is also presented through Figure 2, where, in the first phase, we have constructed a concerning network; then, we calculate the degree and K-shell of each node; after that, we calculate the power of K-shell as well as effective distance that only considers the nearest and the next-nearest neighbors nodes. At the last step, influence of each node in the entire network is hereby calculated.Figure 1
A simple network with 16 nodes and 21 edges.Figure 2
The flowchart of the proposed EDBC.


### 3.2.1. Computation of the Power of K-Shellαi,j

For calculating the power of K-shell, here we apply equation (2). For node V16, the K-shell value is 2; first of all, we calculate the K-shell of node i and node j. Table 1 shows the K-shell of given toy network. We have α16,9=2+2=2, α16,7=2+2=2, and α16,2=1+2=1.7320. Similarly, in this way, other K-shell power can be calculated.Table 1
K-shell and degrees of each node in a toy network.
Node17234596161581113121014Degree1611124282313313Core number/K-shell1211122222212212


### 3.2.2. Calculation of the Effective Distance

ED (between nearest and next-nearest neighbor of nodes) depends on the closeness among the nodes and its neighbors, to calculate effective distance among the neighbors and the next neighbors of V16 by using equation (3):(6)ED16,9=1−logP9,16=1.903,where(7)P9,16=1d16=0.125.Now, to calculate the distance between the next neighbors ofV16, the distance can be(8)ED16,7=ED16,9+ED7,9,ED16,7=1.903+1−logP9,7=1.903+1.7783=3.6813.Similarly,(9)ED16,5=ED16,9+1−logP9,5=1.903+1.301=3.204.


### 3.2.3. Calculation of the Neighbor Nodes’ Influence

In this context, EDBC algorithm considers only the nearest and the next-nearest neighbor’s nodes. Here, we take V9 as an example of the nearest neighbor node, according to equation (4):(10)I16,9=α16,9+d16ED16,92=2.7614,where d16 is the degree of V16, which is 8. Now, we take the next-nearest neighbor of V9. Therefore, the influence of node V16 to node V7 or node V5 can be computed as follows:(11)I16,7=α16,7+d16ED16,72=0.7379.By this rule, all the nearest and next-nearest neighbor’s nodes of the influence with V16 can be calculated.


### 3.2.4. Computation of the Influence for Each Node

The computation of the total influence of the nodes in the entire network means the sum of the total number of influence nodes on the nearest and next-nearest neighbor nodes. By using equation (5), we can compute the total influence of the node V16 for a given graph:(12)EDBCV16=∑jεΨI16,j+∑kεi,k≠1I16,k=57.6251,where j and k show the nearest and next-nearest neighbor nodes. Applying all of the above procedure, we get all nodes influence the ranking results of the given toy network, as shown in Table 2.Table 2
The influence ranking results using EDBC of the given toy network.
Node167912814136155101Influence57.645.937.427.226.425.224.718.918.917.815.910.7


## 3.2.1. Computation of the Power of K-Shellαi,j

For calculating the power of K-shell, here we apply equation (2). For node V16, the K-shell value is 2; first of all, we calculate the K-shell of node i and node j. Table 1 shows the K-shell of given toy network. We have α16,9=2+2=2, α16,7=2+2=2, and α16,2=1+2=1.7320. Similarly, in this way, other K-shell power can be calculated.Table 1
K-shell and degrees of each node in a toy network.
Node17234596161581113121014Degree1611124282313313Core number/K-shell1211122222212212


## 3.2.2. Calculation of the Effective Distance

ED (between nearest and next-nearest neighbor of nodes) depends on the closeness among the nodes and its neighbors, to calculate effective distance among the neighbors and the next neighbors of V16 by using equation (3):(6)ED16,9=1−logP9,16=1.903,where(7)P9,16=1d16=0.125.Now, to calculate the distance between the next neighbors ofV16, the distance can be(8)ED16,7=ED16,9+ED7,9,ED16,7=1.903+1−logP9,7=1.903+1.7783=3.6813.Similarly,(9)ED16,5=ED16,9+1−logP9,5=1.903+1.301=3.204.


## 3.2.3. Calculation of the Neighbor Nodes’ Influence

In this context, EDBC algorithm considers only the nearest and the next-nearest neighbor’s nodes. Here, we take V9 as an example of the nearest neighbor node, according to equation (4):(10)I16,9=α16,9+d16ED16,92=2.7614,where d16 is the degree of V16, which is 8. Now, we take the next-nearest neighbor of V9. Therefore, the influence of node V16 to node V7 or node V5 can be computed as follows:(11)I16,7=α16,7+d16ED16,72=0.7379.By this rule, all the nearest and next-nearest neighbor’s nodes of the influence with V16 can be calculated.


## 3.2.4. Computation of the Influence for Each Node

The computation of the total influence of the nodes in the entire network means the sum of the total number of influence nodes on the nearest and next-nearest neighbor nodes. By using equation (5), we can compute the total influence of the node V16 for a given graph:(12)EDBCV16=∑jεΨI16,j+∑kεi,k≠1I16,k=57.6251,where j and k show the nearest and next-nearest neighbor nodes. Applying all of the above procedure, we get all nodes influence the ranking results of the given toy network, as shown in Table 2.Table 2
The influence ranking results using EDBC of the given toy network.
Node167912814136155101Influence57.645.937.427.226.425.224.718.918.917.815.910.7


## 3.3. Computational Complexity

EDBC takes three components. In the first phase, it calculates the degree and K-shell, so the time complexity becomesOM. In the second phase, it computes the effective distance among the nodes and their adjacent or neighbors. The distance between the nearest and next-nearest neighbors in the entire network is calculated. Therefore, the computational time complexity is O N<K>2, and in the third and fourth phases, the node’s influence of all neighbors will be calculated. Therefore, EDBC algorithm’s total time complexity can become ON<k>2+M, where N and k denote the number of nodes and average degree of nodes in the network, respectively.


## 4. Experimentation and Results’ Analysis

In this section, we discuss the experimental setup we performed on various real-world networks and datasets to overview of the performance evaluation and comparison between the proposed EDBC algorithm and ten aforementioned state-of-the-art algorithms. We implemented EDBC algorithm inPython 3.7 and rendered experiments on Feiteng Server (1, 16-core, and 1.5gHZ) provided by Kirin Operating System in the main lab of our school.


### 4.1. Comparison of Some Benchmark Centralities

We compared EDBC of our proposed methodology with nine baseline algorithms, which we are going to briefly summarize and classify according to their characteristic in this section. The existing centrality measures are classified into categories:(a)
Structure-based centralities: the node influence is significantly affected via the network topology. In fact, a lot of centralities consider structural information for the identification of influential nodes. The structure-based measure is further divided into two categories: (i) based on the neighborhood of each node, for example, K-shell and H-index and (ii) based on paths between nodes, such as betweenness and closeness centralities. K-shell (KS) algorithm decomposes a network into sublayers that are directly connected to the centrality [55]. In fact, this algorithm assigns Ks (integer index) to each node, which are representatives of the nodes’ location in the network. The Ks of each node with high or low values is placed at the center or periphery of the network. By this rule, the network is designated via a layered structure, revealing the complete hierarchy of its nodes. The innermost nodes are known as core or nucleus, and K-shell nodes are placed into internal and external layers. It is a straightforward indexing algorithm for identifying the influential nodes and can be applied to any network; however, it cannot differentiate the influential nodes in the same core layer. Therefore, KS algorithm is not suitable for some of the networks. Our experiments provide evidence in this case. The H-index [23] algorithm is commonly used to evaluate researchers’ and scientists’ academic achievements. The computation process of the H value in the H-index signifies that the author or scholar has at least H citations of H article published by an author. High H-index reflects that the node has greater influence. Still, this algorithm has many problems with its effective execution, e.g., edge value weight needs to be in appropriate range, otherwise the desired ranking could not be achieved. Betweeness centrality (BC) [18] is used to computes important nodes via global information. It works on the shortest path between the nodes where a node with a higher BC value indicates that it is more important than other nodes in the entire network. However, it is not appropriate for large and complex networks, whereas experimental results have clearly depicted that EDBC is a suitable approach for any kind of network whether it is large or small. Closeness centrality (CC) [16] depends on global information, and it works on the relative distance between each pair of nodes to detect the important nodes. CC can better be identifying influential nodes but very difficult to apply in large networks. The limitation of this algorithm is the lack of applicability to networks by disconnected components. In short, these kinds of centralities have high computational complexity and cannot be suitable for large-scale networks.(b)
Eigenvector-based centralities: eigenvector-based centralities not only consider the neighborhood node number but also consider their influences. These centralities are PageRank, eigenvector, profit leader, HITS, and gravity index. Eigenvector centrality (EC) [21] is based on the information gain method to choose important nodes in the network. It neither depends only on the degree number of neighborhood nodes nor the impact of each neighbor node. This algorithm has excessive applications both in theoretical and practical. Though, if there exist several nodes with higher degrees in the graph, the risky phenomenon of fractional convergence will still occur; therefore, EC is not an appropriate solution for such networks. PageRank (PR) [22] is one of the famous centrality algorithms; Google search engine is working based on this algorithm. Like EC, PR supposes that the influence of a web page depends on both the quantity and quality of the pages joined by it [55]. It is suitable for directed networks but not for undirected and unweighted, but EDBC is appropriate in case of any type of network whether it is directed or undirected. hyperlink-induced topic search (HITS) [25] is a link analysis technique that uses various metrics concurrently. It scrutinizes the influence of the node via two attributes, i.e., hub and authority value, where the hub value emulates the node role for information transmission, while the authority value analyzes the original node creativity in the information. These two attributes interact and converge through the iteration process. Profit leader (PL) [36] is one of the most recent algorithms, which was proposed by Yu et al. in May 2018. This algorithm is based on the profit leader concept, which chooses the important nodes in the entire network by calculating the profit the node can make. This algorithm is very simple and applicable to some networks. However, this algorithm is not working very well in case of small networks. Gravity (GR) was proposed by Ma et al. in 2016 [44], which works on the principle of gravity formula. Here, mass is replaced by the K-shell value of each node, and the distance is the shortest path between two nodes, to identify the key nodes in the network. Its drawback is the computational time complexity which is too high to be suitable for large-scale networks.


### 4.2. Data Description

We evaluated EDBC on nine real-world networks to reveal its performance. The data has been collected from different genres of fields where its basic properties, scales, and structures are presented in Table3. These datasets are publicly available and can be downloaded from sites http://konect.uni-koblenz.de/networks/, http://snap.stanford.edu/data/as-caida.html, and http://networkrepository.com/web-spam.php.Physicians [56]. This dataset contains 241 nodes and 1098 edges, collected in 1966 by RonBurt. A node denotes a physician, and the link between two physicians represents that the left-hand physician is the friend of the right-hand physician. There is only one link that subsists between any two nodes.e-mail [57]. This network is an e-mail system at the University RV in south Tarragona, Spain. It consists of 5451 links and 1133 nodes. Nodes denote users, and links show that one e-mail was sent at least.Subelij-euroroad [58]. This is a Europe e-road network, which contains 1174 nodes and 1417 edges. Nodes represent cities, and edges of the two nodes indicate that they are linked via an e-road.Air-traffic control [59]. This network was created for FAA (federal aviation administration) system in the USA. Nodes represent service centers or airports, and edges are formed from a string of preferred routes.Petster-friendships [60]. This network consists of friendships among users on the website hamsterster.com. In this network, users represent nodes, and the closeness among users represents edges.US-Powergrid [61]. This is an undirected network which consists of information about the power grid of the Western states in the USA. It contains 6594 links and 4941 nodes. The generator or transformator in the network represents nodes, while the power supply line denotes edges.Web-spam [62]. This dataset is constructed by Purdue University network repository. It consists of 4767 nodes and 37,375 edges. Pages and hyperlinks represent nodes and edges, respectively.PGP algorithm [63]. This is the user’s communication network for the Pretty Good Privacy (PGP) algorithm and consists of 24,316 links and 10,680 nodes. It comprises only the giant interconnected elements of the network.CAIDA-project [64]. This is the CAIDA-project network, collected in 2007 and containing 26,475 nodes and 53,381 edges. A node represents autonomous systems (AS), while edges represent communication.Table 3
The basic statistics of nine real-world networks, whereM, N, and K represent the number of edges, number of nodes, and average degree, respectively. The last two columns indicate the maximum degree (Kmax) and cluster coefficients (CC) of the networks.
NetworksMNKKmaxCCPhysicians10982419.112340.31157e-mail545113339.615710.2202Subelj-euroroad141711742.41050.01673Air-traffic control261512264.2659370.04P-friendships1253418585.745850.167US-powergrid659449412.67100.0801Web-spam37375476715.6814770.2859PGP algorithm24316106804.55362050.2659CAIDA-project53381264754.032626280.208


### 4.3. Evaluation Metrics

#### 4.3.1. SIR Model

To evaluate the effectiveness of the identification of influential nodes, we employ the SIR model to simulate the spreading influence of ranking nodes in our experiments [65, 66]. This model consists of three states, i.e., S (susceptible) means a healthy state and may be infected by others. I (infected) means an infected state and can infect other individuals. R (recovered) represents a recovered state, which cannot be infected by other individuals again. All the seed nodes in the network are in a susceptible state initially. At each time step, the seed node in the network may infect its neighbor’s susceptible nodes via a probability β; then, infected nodes are recovered (enter into the recovered state) with probability μ. This process will continue until there has no longer infected nodes. Finally, all the recovered nodes are used to imitate the real node influence.S(t), I(t), and R(t) denote the nodes’ numbers in susceptible, infected, and recovered states. So,(13)dstdt=−βstit,ditdt=βstit−βit,drtdt=βit.The spreading influenceKi of the node Vi is as follows:(14)Ki=Ft=1NitenI+nR,where Nite denotes iteration numbers; here, we set Nite=1000 independent run, and nI and nR represent the number of infected and recovered nodes, respectively.


#### 4.3.2. Kendall’s Correlation Coefficientτ

Kendall’s correlation coefficientτ [67, 68] is used to measure the correctness results of two ranking methods. In this paper, we acquired Kendall’s correlation coefficient to measure the performance of the proposed algorithm. Let us suppose that two node sequences X&Y are correlated with similar nodes’ number (n), X=x1,x2,……,xn and Y=y1,y2,…,yn. One pair of two annotations xi,yi and Xj,Yji≠j are said to be concordant if the ranking of both component agree, i.e., if both xi>xj and yi>yj or xi<xj and yi<yj. They are said to be discordant if xi>xj and yi<yj or xi<xj and yi>yj or if xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s τ is defined as follows:(15)τX,Y=nc−nd0.5nn−1,where nc and nd represent the number of concordant and discordant pairs, respectively. If Kendall’s correlation coefficient (t) is positive, then the two rankings are positively correlated, and if Kendall’s correlation coefficient (t) is negative, then two rankings are negatively correlated. The coefficient is 1 when the two rankings are the same, and if the coefficient is -1, then it means the two rankings are completely opposite. Higher Kendall’s values specify more precise and better performance.


### 4.4. Performance Evaluation

In this experiment, we used the SIR and Kendall’s models to verify the effectiveness of EDBC. First, we have used a toy network as an example, as shown in Figure1, where we applied EDBC to identify the influential nodes, compared it with nine baseline algorithms, and listed the ranking results and SIR values of each node, as shown in Table 4. It can be seen that the EDBC performs well than other various raking algorithms in terms of identification of influential nodes’ ranking. Figure 3 illustrates Kendall’s correlation coefficient (τ) calculation results of the ten algorithms, where the ranking effects are generated via the K-shell, HITS, H-index, PageRank, BC, CC, EC, PL, and GR.Table 4
Comparison of a toy network’s ranking results of EDBC with other various algorithms, where GR, PL, and PR represent profit leader, page rank, and gravity, respectively. Here, EDBC∗ and SIR∗ indicate the ranking value of the EDBC and SIR value, respectively.
BCCCECH-indexHITSK-shellPRPLGREDBEDBC∗SIRSIR∗161616916161616161657.63161.939912121212779745.7871.627714131413997937.3891.6081291491488121227.2481.411251316139131413826.37141.4913886861213141425.17131.44141367157141281324.65121.51114158685156618.96151.312671571566151518.9661.323151051051555517.8351.34410511511111101015.89111.1351112112242110.7041.17621313313210.7011.151532424424310.7021.16114313111311410.7031.151011410410101011106.69101.17Figure 3
Results of Kendall’sτ obtained from mutual comparison of results generated by ten mentioned algorithms and ranking of results produced of the SIR model. Network’s spreading probability β was set in the range from 0.01 to 0.10, and results were calculated based on average outcome of 1000 independent runs. (a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)In Figure3, EDBC gets the highest Kendall’s τ correlation coefficients in (physicians, e-mail, Subelij-eroroad, petster-friendships, air-traffic control, US-powergrid, and web-spam networks. The results in the range between 0.8 and 1 such as 0.9 for physicians and web-spam, 0.95 for e-mail, Subelij-euroroad, CAIDA-project, and US-powergrid, and 1.0 for PGP algorithm and petster-friendships, respectively. Figure 3 shows the performance between ten algorithms based on the comparison of the Kendall’s τ, and EDBC performs well on all kinds of networks. We note that the performance of BC measure is always the worst on all networks because BC is usually based on the definition of the shortest paths between the nodes and information in most networks which does not flow along with the shortest paths [69].In order to further examine the performance measures of EDBC. We used the SIR model for spreading the impact of the ranked nodes, where we used a relatively smallβ for big networks such as PGP algorithm and CAIDA-project. Especially, we have set β=0.01 due to the bigger value, and the propagation will occur across the whole network [70]; in this situation, it will be hard to separate the influence of different nodes. For small networks such as web-spam, US-powergrid, physicians, e-mail, Subelij-euroroad, petster-friendships, and air-traffic control, we have set β=0.1 to estimate the influences of each node. Therefore, either we achieve the propagation efficiency in the entire network for all nodes or we keep the recovery rate probability, i.e., γ is equal to 1 and the time t is equal to 1000.The ranking results of the average number of infected nodes by the ten algorithms’ comparison are shown in Figure4. A more influential node can affect more nodes; therefore, an efficient algorithm can produce a curve that reduces from left to right showing that EDBC is comparatively capable of the best performance on physicians, e-mail, Subelij-euroroad, air-traffic control, US-powergrid, and web-spam networks. Performance-wise, on petster-friendships network, the GR and EDBC algorithms are approximately the same, but still, EDBC works well in other networks; it is why all the curves are drawn smoothly with a negligible variation. For CAIDA-Project, all the algorithms show similar effects, but EDBC still provides a greater spreading effect than other algorithms. Moreover, ranking results of the performance of ten mentioned algorithms on the Subelij-euroroad network are presented in Table 5, where each node is considered a seed node that has recursively infected its neighbor nodes. It can be seen that EDBC performs better than other baseline algorithms. In addition, we performed the influence comparison of the top-10 nodes, which are distinctly selected by EDBC and other various algorithms. All top-10 distinct nodes are selected as seed nodes, and the time is set to t where values’ range of t varies from 1 to 20. As shown in Table 6, EDBC has highest propagation capability for all nodes, and it clearly shows that when the infection Ft increases as time t increase, we finally get a steady value at a time t after having consecutive time points. Table 7 shows the top-10 ranked nodes. Due to the limited space, we have only shown the top-10 nodes of PGP algorithm network. Consequently, there are ten seed nodes, and most network propagation arrives at a steady-state at time period t = 20 where we can examine the spreading effect of EDBC and all some other baseline algorithms. Moreover, Figure 5 indicates that the EDBC algorithm has a good spreading efficiency of top-10 nodes. Specifically, EDBC has better performance on the physicians, e-mail, Subelij-euroroad, air-traffic control, petster-friendships, and PGP algorithm US-Powergrid networks. In petster-friendships and CAIDA-project networks, PR and EC have the best propagation effect. And, EDBC has also better spreading efficiency than other baseline algorithms.Figure 4
Influence of propagation for ranking effect using ten various algorithms, whereF(t) represents the number of infected and recovered nodes at time (t), and horizontal index line represents the ranking order list.(a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Table 5
Ranking results of the SIR model w.r.t node influence of ten mentioned algorithms in Subelj-euroroad network. Here, GR, PL, and PR represent profit leader, page rank, and gravity, respectively.
tBCCCECH-indexHITSK-shellPRPLGREDB11.6721.771.232.042.211.082.091.991.952.1822.131.601.121.971.751.061.992.172.272.1231.631.501.111.751.761.061.972.021.532.0741.731.491.281.661.931.032.001.961.791.9151.341.461.092.011.911.052.061.911.941.9661.561.721.231.751.581.062.111.931.961.9972.031.331.201.772.101.081.741.942.031.9981.371.311.251.691.811.061.511.951.491.9891.271.581.241.631.711.071.641.851.711.98101.182.211.091.811.811.041.401.891.721.93111.271.771.201.621.761.051.991.971.871.80121.481.351.221.741.651.061.581.901.531.90132.131.841.231.451.531.052.011.751.492.03141.411.471.231.551.861.061.871.791.481.88151.281.441.141.541.501.071.691.761.591.82161.391.271.171.521.651.041.971.721.361.83171.351.511.121.771.701.041.771.801.981.82181.731.561.091.721.521.111.631.741.821.74191.331.561.091.491.691.081.791.811.941.87201.241.631.091.351.781.071.991.761.581.89Table 6
InfluencesF(t) of top-10 distinct nodes using EDBC and other various algorithms in the e-mail network. Here, GR, PL, and PR represent profit leader, page rank, and gravity, respectively.
tBCCCECH-indexHITSK-shellPRPLGREDBC126.5726.3625.0522.8326.1924.3627.5525.9226.4926.98236.3935.9933.9130.5836.9432.5136.4735.9536.7538.14341.5340.9239.1835.1441.7736.8742.8741.3541.8344.30444.6243.6440.8838.2945.4239.3445.3144.0345.5946.70545.1645.8941.6739.4446.3240.6746.7845.2546.9548.24646.7446.5642.7539.9147.8142.0747.8445.6947.1049.27747.5147.7843.5939.9847.9542.6748.1247.0647.6149.86847.5346.8943.1341.1047.7541.8948.6347.6447.2149.69947.1146.3443.0941.0647.6041.9148.4148.4048.8848.491047.2646.8144.4841.7948.2441.7548.1647.4248.6848.691147.7147.2644.3241.9047.3542.7048.7046.9548.2549.141246.1846.8944.0439.7747.1642.5148.1947.7747.6848.151346.7347.7743.3639.8947.5542.1549.3947.4847.1949.111447.1647.8043.9940.7347.8542.2948.3046.6748.7049.191547.1047.7544.2240.5247.4242.5549.3847.5348.3649.321647.3347.4942.9640.5348.6842.3348.9547.5347.7850.631748.4345.6843.7639.9347.5443.0348.5946.6948.4350.121848.4146.8943.6740.4548.6242.0349.0748.3048.8549.121948.0647.0144.0039.2947.3441.7448.9247.1748.4948.892047.5146.8144.1740.4348.2942.4648.4047.4748.5250.016Table 7
Comparison of ranking of the top-10 nodes; owing to the limited space, only the top-10 nodes of the PGP algorithm are presented, where PR, PL, and GR denote page rang, profit leader, and gravity, respectively.
BCCCECH-indexHITSK-shellPRPLGREDBC12511251125112512562496012511251338147433815332613612518801408261251338147415401533264512661941533153326180212821408154030711300338131214741474960180215371408308813014115401408131210341312153015301577140812512615401272253103426126615311530588338131215482501621193515379431533147415371548311338250154813003765153725015301530154776113381943154847581540372147415371275Figure 5
Influence of propagation for top-10 ranking effects using ten various algorithms, whereF(t) represents the number of infected and recovered nodes at time (t) in a variable range between 0 and 20. (a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)


## 4.1. Comparison of Some Benchmark Centralities

We compared EDBC of our proposed methodology with nine baseline algorithms, which we are going to briefly summarize and classify according to their characteristic in this section. The existing centrality measures are classified into categories:(a)
Structure-based centralities: the node influence is significantly affected via the network topology. In fact, a lot of centralities consider structural information for the identification of influential nodes. The structure-based measure is further divided into two categories: (i) based on the neighborhood of each node, for example, K-shell and H-index and (ii) based on paths between nodes, such as betweenness and closeness centralities. K-shell (KS) algorithm decomposes a network into sublayers that are directly connected to the centrality [55]. In fact, this algorithm assigns Ks (integer index) to each node, which are representatives of the nodes’ location in the network. The Ks of each node with high or low values is placed at the center or periphery of the network. By this rule, the network is designated via a layered structure, revealing the complete hierarchy of its nodes. The innermost nodes are known as core or nucleus, and K-shell nodes are placed into internal and external layers. It is a straightforward indexing algorithm for identifying the influential nodes and can be applied to any network; however, it cannot differentiate the influential nodes in the same core layer. Therefore, KS algorithm is not suitable for some of the networks. Our experiments provide evidence in this case. The H-index [23] algorithm is commonly used to evaluate researchers’ and scientists’ academic achievements. The computation process of the H value in the H-index signifies that the author or scholar has at least H citations of H article published by an author. High H-index reflects that the node has greater influence. Still, this algorithm has many problems with its effective execution, e.g., edge value weight needs to be in appropriate range, otherwise the desired ranking could not be achieved. Betweeness centrality (BC) [18] is used to computes important nodes via global information. It works on the shortest path between the nodes where a node with a higher BC value indicates that it is more important than other nodes in the entire network. However, it is not appropriate for large and complex networks, whereas experimental results have clearly depicted that EDBC is a suitable approach for any kind of network whether it is large or small. Closeness centrality (CC) [16] depends on global information, and it works on the relative distance between each pair of nodes to detect the important nodes. CC can better be identifying influential nodes but very difficult to apply in large networks. The limitation of this algorithm is the lack of applicability to networks by disconnected components. In short, these kinds of centralities have high computational complexity and cannot be suitable for large-scale networks.(b)
Eigenvector-based centralities: eigenvector-based centralities not only consider the neighborhood node number but also consider their influences. These centralities are PageRank, eigenvector, profit leader, HITS, and gravity index. Eigenvector centrality (EC) [21] is based on the information gain method to choose important nodes in the network. It neither depends only on the degree number of neighborhood nodes nor the impact of each neighbor node. This algorithm has excessive applications both in theoretical and practical. Though, if there exist several nodes with higher degrees in the graph, the risky phenomenon of fractional convergence will still occur; therefore, EC is not an appropriate solution for such networks. PageRank (PR) [22] is one of the famous centrality algorithms; Google search engine is working based on this algorithm. Like EC, PR supposes that the influence of a web page depends on both the quantity and quality of the pages joined by it [55]. It is suitable for directed networks but not for undirected and unweighted, but EDBC is appropriate in case of any type of network whether it is directed or undirected. hyperlink-induced topic search (HITS) [25] is a link analysis technique that uses various metrics concurrently. It scrutinizes the influence of the node via two attributes, i.e., hub and authority value, where the hub value emulates the node role for information transmission, while the authority value analyzes the original node creativity in the information. These two attributes interact and converge through the iteration process. Profit leader (PL) [36] is one of the most recent algorithms, which was proposed by Yu et al. in May 2018. This algorithm is based on the profit leader concept, which chooses the important nodes in the entire network by calculating the profit the node can make. This algorithm is very simple and applicable to some networks. However, this algorithm is not working very well in case of small networks. Gravity (GR) was proposed by Ma et al. in 2016 [44], which works on the principle of gravity formula. Here, mass is replaced by the K-shell value of each node, and the distance is the shortest path between two nodes, to identify the key nodes in the network. Its drawback is the computational time complexity which is too high to be suitable for large-scale networks.


## 4.2. Data Description

We evaluated EDBC on nine real-world networks to reveal its performance. The data has been collected from different genres of fields where its basic properties, scales, and structures are presented in Table3. These datasets are publicly available and can be downloaded from sites http://konect.uni-koblenz.de/networks/, http://snap.stanford.edu/data/as-caida.html, and http://networkrepository.com/web-spam.php.Physicians [56]. This dataset contains 241 nodes and 1098 edges, collected in 1966 by RonBurt. A node denotes a physician, and the link between two physicians represents that the left-hand physician is the friend of the right-hand physician. There is only one link that subsists between any two nodes.e-mail [57]. This network is an e-mail system at the University RV in south Tarragona, Spain. It consists of 5451 links and 1133 nodes. Nodes denote users, and links show that one e-mail was sent at least.Subelij-euroroad [58]. This is a Europe e-road network, which contains 1174 nodes and 1417 edges. Nodes represent cities, and edges of the two nodes indicate that they are linked via an e-road.Air-traffic control [59]. This network was created for FAA (federal aviation administration) system in the USA. Nodes represent service centers or airports, and edges are formed from a string of preferred routes.Petster-friendships [60]. This network consists of friendships among users on the website hamsterster.com. In this network, users represent nodes, and the closeness among users represents edges.US-Powergrid [61]. This is an undirected network which consists of information about the power grid of the Western states in the USA. It contains 6594 links and 4941 nodes. The generator or transformator in the network represents nodes, while the power supply line denotes edges.Web-spam [62]. This dataset is constructed by Purdue University network repository. It consists of 4767 nodes and 37,375 edges. Pages and hyperlinks represent nodes and edges, respectively.PGP algorithm [63]. This is the user’s communication network for the Pretty Good Privacy (PGP) algorithm and consists of 24,316 links and 10,680 nodes. It comprises only the giant interconnected elements of the network.CAIDA-project [64]. This is the CAIDA-project network, collected in 2007 and containing 26,475 nodes and 53,381 edges. A node represents autonomous systems (AS), while edges represent communication.Table 3
The basic statistics of nine real-world networks, whereM, N, and K represent the number of edges, number of nodes, and average degree, respectively. The last two columns indicate the maximum degree (Kmax) and cluster coefficients (CC) of the networks.
NetworksMNKKmaxCCPhysicians10982419.112340.31157e-mail545113339.615710.2202Subelj-euroroad141711742.41050.01673Air-traffic control261512264.2659370.04P-friendships1253418585.745850.167US-powergrid659449412.67100.0801Web-spam37375476715.6814770.2859PGP algorithm24316106804.55362050.2659CAIDA-project53381264754.032626280.208


## 4.3. Evaluation Metrics

### 4.3.1. SIR Model

To evaluate the effectiveness of the identification of influential nodes, we employ the SIR model to simulate the spreading influence of ranking nodes in our experiments [65, 66]. This model consists of three states, i.e., S (susceptible) means a healthy state and may be infected by others. I (infected) means an infected state and can infect other individuals. R (recovered) represents a recovered state, which cannot be infected by other individuals again. All the seed nodes in the network are in a susceptible state initially. At each time step, the seed node in the network may infect its neighbor’s susceptible nodes via a probability β; then, infected nodes are recovered (enter into the recovered state) with probability μ. This process will continue until there has no longer infected nodes. Finally, all the recovered nodes are used to imitate the real node influence.S(t), I(t), and R(t) denote the nodes’ numbers in susceptible, infected, and recovered states. So,(13)dstdt=−βstit,ditdt=βstit−βit,drtdt=βit.The spreading influenceKi of the node Vi is as follows:(14)Ki=Ft=1NitenI+nR,where Nite denotes iteration numbers; here, we set Nite=1000 independent run, and nI and nR represent the number of infected and recovered nodes, respectively.


### 4.3.2. Kendall’s Correlation Coefficientτ

Kendall’s correlation coefficientτ [67, 68] is used to measure the correctness results of two ranking methods. In this paper, we acquired Kendall’s correlation coefficient to measure the performance of the proposed algorithm. Let us suppose that two node sequences X&Y are correlated with similar nodes’ number (n), X=x1,x2,……,xn and Y=y1,y2,…,yn. One pair of two annotations xi,yi and Xj,Yji≠j are said to be concordant if the ranking of both component agree, i.e., if both xi>xj and yi>yj or xi<xj and yi<yj. They are said to be discordant if xi>xj and yi<yj or xi<xj and yi>yj or if xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s τ is defined as follows:(15)τX,Y=nc−nd0.5nn−1,where nc and nd represent the number of concordant and discordant pairs, respectively. If Kendall’s correlation coefficient (t) is positive, then the two rankings are positively correlated, and if Kendall’s correlation coefficient (t) is negative, then two rankings are negatively correlated. The coefficient is 1 when the two rankings are the same, and if the coefficient is -1, then it means the two rankings are completely opposite. Higher Kendall’s values specify more precise and better performance.


## 4.3.1. SIR Model

To evaluate the effectiveness of the identification of influential nodes, we employ the SIR model to simulate the spreading influence of ranking nodes in our experiments [65, 66]. This model consists of three states, i.e., S (susceptible) means a healthy state and may be infected by others. I (infected) means an infected state and can infect other individuals. R (recovered) represents a recovered state, which cannot be infected by other individuals again. All the seed nodes in the network are in a susceptible state initially. At each time step, the seed node in the network may infect its neighbor’s susceptible nodes via a probability β; then, infected nodes are recovered (enter into the recovered state) with probability μ. This process will continue until there has no longer infected nodes. Finally, all the recovered nodes are used to imitate the real node influence.S(t), I(t), and R(t) denote the nodes’ numbers in susceptible, infected, and recovered states. So,(13)dstdt=−βstit,ditdt=βstit−βit,drtdt=βit.The spreading influenceKi of the node Vi is as follows:(14)Ki=Ft=1NitenI+nR,where Nite denotes iteration numbers; here, we set Nite=1000 independent run, and nI and nR represent the number of infected and recovered nodes, respectively.


## 4.3.2. Kendall’s Correlation Coefficientτ

Kendall’s correlation coefficientτ [67, 68] is used to measure the correctness results of two ranking methods. In this paper, we acquired Kendall’s correlation coefficient to measure the performance of the proposed algorithm. Let us suppose that two node sequences X&Y are correlated with similar nodes’ number (n), X=x1,x2,……,xn and Y=y1,y2,…,yn. One pair of two annotations xi,yi and Xj,Yji≠j are said to be concordant if the ranking of both component agree, i.e., if both xi>xj and yi>yj or xi<xj and yi<yj. They are said to be discordant if xi>xj and yi<yj or xi<xj and yi>yj or if xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s τ is defined as follows:(15)τX,Y=nc−nd0.5nn−1,where nc and nd represent the number of concordant and discordant pairs, respectively. If Kendall’s correlation coefficient (t) is positive, then the two rankings are positively correlated, and if Kendall’s correlation coefficient (t) is negative, then two rankings are negatively correlated. The coefficient is 1 when the two rankings are the same, and if the coefficient is -1, then it means the two rankings are completely opposite. Higher Kendall’s values specify more precise and better performance.


## 4.4. Performance Evaluation

In this experiment, we used the SIR and Kendall’s models to verify the effectiveness of EDBC. First, we have used a toy network as an example, as shown in Figure1, where we applied EDBC to identify the influential nodes, compared it with nine baseline algorithms, and listed the ranking results and SIR values of each node, as shown in Table 4. It can be seen that the EDBC performs well than other various raking algorithms in terms of identification of influential nodes’ ranking. Figure 3 illustrates Kendall’s correlation coefficient (τ) calculation results of the ten algorithms, where the ranking effects are generated via the K-shell, HITS, H-index, PageRank, BC, CC, EC, PL, and GR.Table 4
Comparison of a toy network’s ranking results of EDBC with other various algorithms, where GR, PL, and PR represent profit leader, page rank, and gravity, respectively. Here, EDBC∗ and SIR∗ indicate the ranking value of the EDBC and SIR value, respectively.
BCCCECH-indexHITSK-shellPRPLGREDBEDBC∗SIRSIR∗161616916161616161657.63161.939912121212779745.7871.627714131413997937.3891.6081291491488121227.2481.411251316139131413826.37141.4913886861213141425.17131.44141367157141281324.65121.51114158685156618.96151.312671571566151518.9661.323151051051555517.8351.34410511511111101015.89111.1351112112242110.7041.17621313313210.7011.151532424424310.7021.16114313111311410.7031.151011410410101011106.69101.17Figure 3
Results of Kendall’sτ obtained from mutual comparison of results generated by ten mentioned algorithms and ranking of results produced of the SIR model. Network’s spreading probability β was set in the range from 0.01 to 0.10, and results were calculated based on average outcome of 1000 independent runs. (a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)In Figure3, EDBC gets the highest Kendall’s τ correlation coefficients in (physicians, e-mail, Subelij-eroroad, petster-friendships, air-traffic control, US-powergrid, and web-spam networks. The results in the range between 0.8 and 1 such as 0.9 for physicians and web-spam, 0.95 for e-mail, Subelij-euroroad, CAIDA-project, and US-powergrid, and 1.0 for PGP algorithm and petster-friendships, respectively. Figure 3 shows the performance between ten algorithms based on the comparison of the Kendall’s τ, and EDBC performs well on all kinds of networks. We note that the performance of BC measure is always the worst on all networks because BC is usually based on the definition of the shortest paths between the nodes and information in most networks which does not flow along with the shortest paths [69].In order to further examine the performance measures of EDBC. We used the SIR model for spreading the impact of the ranked nodes, where we used a relatively smallβ for big networks such as PGP algorithm and CAIDA-project. Especially, we have set β=0.01 due to the bigger value, and the propagation will occur across the whole network [70]; in this situation, it will be hard to separate the influence of different nodes. For small networks such as web-spam, US-powergrid, physicians, e-mail, Subelij-euroroad, petster-friendships, and air-traffic control, we have set β=0.1 to estimate the influences of each node. Therefore, either we achieve the propagation efficiency in the entire network for all nodes or we keep the recovery rate probability, i.e., γ is equal to 1 and the time t is equal to 1000.The ranking results of the average number of infected nodes by the ten algorithms’ comparison are shown in Figure4. A more influential node can affect more nodes; therefore, an efficient algorithm can produce a curve that reduces from left to right showing that EDBC is comparatively capable of the best performance on physicians, e-mail, Subelij-euroroad, air-traffic control, US-powergrid, and web-spam networks. Performance-wise, on petster-friendships network, the GR and EDBC algorithms are approximately the same, but still, EDBC works well in other networks; it is why all the curves are drawn smoothly with a negligible variation. For CAIDA-Project, all the algorithms show similar effects, but EDBC still provides a greater spreading effect than other algorithms. Moreover, ranking results of the performance of ten mentioned algorithms on the Subelij-euroroad network are presented in Table 5, where each node is considered a seed node that has recursively infected its neighbor nodes. It can be seen that EDBC performs better than other baseline algorithms. In addition, we performed the influence comparison of the top-10 nodes, which are distinctly selected by EDBC and other various algorithms. All top-10 distinct nodes are selected as seed nodes, and the time is set to t where values’ range of t varies from 1 to 20. As shown in Table 6, EDBC has highest propagation capability for all nodes, and it clearly shows that when the infection Ft increases as time t increase, we finally get a steady value at a time t after having consecutive time points. Table 7 shows the top-10 ranked nodes. Due to the limited space, we have only shown the top-10 nodes of PGP algorithm network. Consequently, there are ten seed nodes, and most network propagation arrives at a steady-state at time period t = 20 where we can examine the spreading effect of EDBC and all some other baseline algorithms. Moreover, Figure 5 indicates that the EDBC algorithm has a good spreading efficiency of top-10 nodes. Specifically, EDBC has better performance on the physicians, e-mail, Subelij-euroroad, air-traffic control, petster-friendships, and PGP algorithm US-Powergrid networks. In petster-friendships and CAIDA-project networks, PR and EC have the best propagation effect. And, EDBC has also better spreading efficiency than other baseline algorithms.Figure 4
Influence of propagation for ranking effect using ten various algorithms, whereF(t) represents the number of infected and recovered nodes at time (t), and horizontal index line represents the ranking order list.(a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Table 5
Ranking results of the SIR model w.r.t node influence of ten mentioned algorithms in Subelj-euroroad network. Here, GR, PL, and PR represent profit leader, page rank, and gravity, respectively.
tBCCCECH-indexHITSK-shellPRPLGREDB11.6721.771.232.042.211.082.091.991.952.1822.131.601.121.971.751.061.992.172.272.1231.631.501.111.751.761.061.972.021.532.0741.731.491.281.661.931.032.001.961.791.9151.341.461.092.011.911.052.061.911.941.9661.561.721.231.751.581.062.111.931.961.9972.031.331.201.772.101.081.741.942.031.9981.371.311.251.691.811.061.511.951.491.9891.271.581.241.631.711.071.641.851.711.98101.182.211.091.811.811.041.401.891.721.93111.271.771.201.621.761.051.991.971.871.80121.481.351.221.741.651.061.581.901.531.90132.131.841.231.451.531.052.011.751.492.03141.411.471.231.551.861.061.871.791.481.88151.281.441.141.541.501.071.691.761.591.82161.391.271.171.521.651.041.971.721.361.83171.351.511.121.771.701.041.771.801.981.82181.731.561.091.721.521.111.631.741.821.74191.331.561.091.491.691.081.791.811.941.87201.241.631.091.351.781.071.991.761.581.89Table 6
InfluencesF(t) of top-10 distinct nodes using EDBC and other various algorithms in the e-mail network. Here, GR, PL, and PR represent profit leader, page rank, and gravity, respectively.
tBCCCECH-indexHITSK-shellPRPLGREDBC126.5726.3625.0522.8326.1924.3627.5525.9226.4926.98236.3935.9933.9130.5836.9432.5136.4735.9536.7538.14341.5340.9239.1835.1441.7736.8742.8741.3541.8344.30444.6243.6440.8838.2945.4239.3445.3144.0345.5946.70545.1645.8941.6739.4446.3240.6746.7845.2546.9548.24646.7446.5642.7539.9147.8142.0747.8445.6947.1049.27747.5147.7843.5939.9847.9542.6748.1247.0647.6149.86847.5346.8943.1341.1047.7541.8948.6347.6447.2149.69947.1146.3443.0941.0647.6041.9148.4148.4048.8848.491047.2646.8144.4841.7948.2441.7548.1647.4248.6848.691147.7147.2644.3241.9047.3542.7048.7046.9548.2549.141246.1846.8944.0439.7747.1642.5148.1947.7747.6848.151346.7347.7743.3639.8947.5542.1549.3947.4847.1949.111447.1647.8043.9940.7347.8542.2948.3046.6748.7049.191547.1047.7544.2240.5247.4242.5549.3847.5348.3649.321647.3347.4942.9640.5348.6842.3348.9547.5347.7850.631748.4345.6843.7639.9347.5443.0348.5946.6948.4350.121848.4146.8943.6740.4548.6242.0349.0748.3048.8549.121948.0647.0144.0039.2947.3441.7448.9247.1748.4948.892047.5146.8144.1740.4348.2942.4648.4047.4748.5250.016Table 7
Comparison of ranking of the top-10 nodes; owing to the limited space, only the top-10 nodes of the PGP algorithm are presented, where PR, PL, and GR denote page rang, profit leader, and gravity, respectively.
BCCCECH-indexHITSK-shellPRPLGREDBC12511251125112512562496012511251338147433815332613612518801408261251338147415401533264512661941533153326180212821408154030711300338131214741474960180215371408308813014115401408131210341312153015301577140812512615401272253103426126615311530588338131215482501621193515379431533147415371548311338250154813003765153725015301530154776113381943154847581540372147415371275Figure 5
Influence of propagation for top-10 ranking effects using ten various algorithms, whereF(t) represents the number of infected and recovered nodes at time (t) in a variable range between 0 and 20. (a) Physicians. (b) e-mail. (c) Subelij-euroroad. (d) Air-traffic control. (e) Petster-friendships. (f) Web-Spam. (g) US-Powergrid. (h) PGP algorithm. (i) CAIDA-project, etc.
(a)(b)(c)(d)(e)(f)(g)(h)(i)


## 5. Conclusion and Future Recommendations

This paper investigates the problem of influential or key node ranking from a performance evaluation’s viewpoint. In view of related studies, several methods have been offered to explore how to detect the key or influential node-based centrality measures. However, these centrality measures’ algorithms have their own advantages and disadvantages. In this study, we proposed an effective-based centrality method for detecting the influential nodes in complex networks. Our proposed algorithm considered K-shell, degree nodes, effective distance, and several levels of neighbor’s influence or neighborhood potential. Consequently, this algorithm can be employed in any network, i.e., directed or undirected. In order to evaluate the performance and effectiveness of the proposed algorithm, we applied several types of real-world networks and used two standard evaluation criteria, SIR and Kendall’s correlation coefficientτ methods, to analyze the spreading influence of ranking nodes. The experimental setup demonstrated that the proposed algorithm regarding accuracy and effectiveness is reasonable and significant as compared to the classical sorting algorithms and recently proposed several relevant algorithms. However, there persist challenging issues that need to be addressed to the quality extent of current work. For instance, adding more parameters to adjust the intensity between the nodes to yield better performance is a challenge. Onward, we plan to improve the proposed algorithm in consideration of weighted formal-concept analysis.



---

*Source: 8403738-2021-02-09.xml*