# Ranking Influential Nodes in Complex Networks with Information Entropy Method

Authors: Nan Zhao; Jingjing Bao; Nan Chen
Journal: Complexity
 (2020)

---

## Abstract

The ranking of influential nodes in networks is of great significance. Influential nodes play an enormous role during the evolution process of information dissemination, viral marketing, and public opinion control. The sorting method of multiple attributes is an effective way to identify the influential nodes. However, these methods offer a limited improvement in algorithm performance because diversity between different attributes is not properly considered. On the basis of the k-shell method, we propose an improved multiattribute k-shell method by using the iterative information in the decomposition process. Our work combines sigmod function and iteration information to obtain the position index. The position attribute is obtained by combining the shell value and the location index. The local information of the node is adopted to obtain the neighbor property. Finally, the position attribute and neighbor attribute are weighted by the method of information entropy weighting. The experimental simulations in six real networks combined with the SIR model and other evaluation measure fully verify the correctness and effectiveness of the proposed method.


---

## Body

## 1. Introduction

Multidimensional information flows rapidly on the network, while different nodes have different effects on information transmission [1], viral marketing [2], public opinion guidance [3], and social recommendation [4, 5] due to their different influences. From the perspective of information transmission, different social networks have different modes of information transmission because of the diversity of functional focuses and user structures. From the perspective of marketing, by providing influential user rankings for different hobbies and groups, it can help new users quickly and effectively obtain relevant information sources of interest so as to achieve a smooth cold start. From the perspective of public opinion guidance and control, the event evolution process of hot public opinions often includes the forwarding and comments of users with different influences on different platforms. These simple operations often lead to an enormous development of public opinions in different directions.The influence of nodes is evaluated from global structure information, such as betweenness centrality [6], closeness centrality [7], and Katz centrality [8]. These methods show good performance in node sorting. However, because of On2 or even higher computational complexity, these methods are not suitable for large-scale networks. The influence of nodes is quantified by local information, such as degree centrality [9], semilocal centrality [10], hybrid degree centrality [11], average shortest path centrality [12], and h index [13]. Local measures are less efficient because they only consider local neighborhood information. There are many heuristic algorithms [14, 15] combined with local neighborhood information. Research based on random walk evaluates the influence of nodes through multiple iterative operations with high-computational complexity such as feature vector centrality [16], PageRank [17], LeaderRank [18], and Hits [19].Kitsak et al. [20] argues that the most influential nodes are those located at the core of the network. Each node is assigned a fixed shell value after k-shell decomposition. However, k-shell decomposition tends to assign the same shell value to many nodes so that the influence of these nodes with same shell value cannot be further distinguished. On this basis, plenty of methods have been proposed to further improve the performance of k-shell method. Zeng and Zhang [21] propose a mixed degree decomposition method, which combines the residual degree and depletion degree to update the nodes. In each step of decomposition, the nodes are removed and decomposed based on the mixed degree. However, the λ parameter is difficult to optimize. Liu et al. [22] proposes an improved ranking method to generate a more differentiated ranking list. This method is realized by calculating the shortest distance between the target node and the core node of the network. The core nodes of the network are in a node set with the highest shell value in k-shell decomposition. The computational cost of this method is relatively expensive by calculating the shortest distances to the core nodes. Bae and Kim [23] propose a new measurement of neighborhood coreness centrality, which calculates the diffusion influence of nodes in the network by summing all neighborhood shell values. The influence of nodes with the same ks value can be further distinguished by using the iterative information of removal nodes to identify the position difference of nodes in the network. The degree decomposition method based on iteration factor [24] is to improve the performance of the traditional method by using the iteration information and node degree in the decomposition. In addition, some other node-sorting algorithms were introduced to improve the sorting performance.On the basis of the k-shell method, our work makes full use of the iterative information in the decomposition process and proposes an improved multiattribute k-shell method. First, the iteration information is processed by sigmod function to obtain the position index. Then, the position attribute is captured by combining the shell value and the position index. The local information of the node is adapted to obtain the neighbor property. Finally, the position attribute and neighbor attribute are weighted by the method of information entropy weighting. In the experiment, the SIR model, Kendall coefficient, and imprecision function are used to, respectively, evaluate the propagation capability of different probabilities of propagation, the imprecision of ranking and the correlation coefficient of different probability of propagation. Furthermore, we evaluate ranking results of the proposed method by selecting seeds in influence maximization problem and measuring the ranking uniqueness and distribution. The experimental results prove that the proposed method can effectively distinguish the differences of different attributes and significantly promote the performance of identifying the influence of nodes.The following parts are organized as follows. We briefly review the definition of related algorithms used for comparison in Section2. In Section 3, our improved multiattribute k-shell method is proposed and a meaningful example is illustrated to show how the proposed measure works. In Section 4, we present the details of the data, the spreading model, and the evaluation measure that are used to evaluate the performance of our measure. The experimental results are presented in Section 5. Finally, we expose the conclusion of the work in Section 6.


## 2. Related Work

Kitsak et al. proposed the k-shell method to determine the influence of nodes in the network. This method considers that the closer the node is to the center of the network, the higher the influence of the node will be. This method uses node degree to rank the importance of nodes. The following details show the decomposition principle of the k-shell method.First, we need to remove the nodes and edges with a medium degree as 1 in the network. At this time, nodes with a degree as 1 still exist in the remaining network. We should continue to remove them until no nodes with a degree as 1 exist in the network. At this point, the removed nodes form a layer and itsks value is assigned to 1. According to the abovementioned method, continue to remove nodes with a degree value as 2 in the network and repeat this operation until there are no nodes in the network. As can be seen in Figure 1, the ks value allocated for nodes 8, 9, 10, 11, 12, 13, 14, 15, and 16 is 1. The value allocated for nodes 5, 6, and 7 is 2. The ks value allocated for nodes 1, 2, 3, and 4 is 3.Figure 1
The schematic diagram of basic principles of the k-shell method.K-shell decomposition method is suitable for large networks because of low-computational complexity. Of course, the disadvantages of this method are obvious. First, most nodes are assigned the sameks value so that the importance of these nodes cannot be further distinguished. For example, from the perspective of degree, the degree of node 8 is 3 and the degree of node 11 is 1. The influence of node 8 is obviously greater than 11, but they have the same ks value. Second, in the process of removing nodes, the edges that have been removed are not considered and the influence of residue is only concerned about. In this way, it is considered that nodes with the same ks have the same number of edges in the outer layer, which is obviously not consistent with common sense. For example, node 1 and node 2 have abundant first-order and second-order neighbors in the outer layer, while node 1 has no neighbors in the outer layer. The same ks value assigned to them does not reflect the difference between them. Third, in the regular network, the ks value of most nodes is 1, which is obviously not suitable for this background.The traditional K-shell decomposition method only updates the nodes according to the residual degree of the remaining nodes and completely ignores the depletion degree of the removed nodes. In the mixed degree decomposition method, the decomposition process is based on the residual degree of the remaining nodes and the depletion degree of the removed nodes. For nodei, its residual degree and depletion degree are represented by kir and kie, respectively. In each step of the mixing degree decomposition method, the node removal is determined by the mixing degree kim:(1)kim=kir+λkie,where λ is the adjustable parameter between 0 and 1. When λ is 0, the mixing degree decomposition method is consistent as the K-shell decomposition method. When λ is 1, the mixed degree decomposition method is equivalent to the degree centrality method. Different from the traditional K-shell decomposition method, in the mixed degree decomposition method, the value of ks of all nodes can be decimal. The parameter λ is usually set to 0.7.The traditional K-shell decomposition method is improved by using the shortest distance from the source node to the core node of the network. The propagation capability of nodes with the sameks value can be further distinguished by the following methods:(2)θi=ksmax−ksi+1∑j∈Scdij,where ksmax is the maximum ks value in K-shell decomposition, ksi is the ks value of node i, and Sc is the set of nodes whose ks value is maximum. Although this nonparametric method can identify nodes with the same ks value, the computational complexity is high because of calculation of the shortest path distance to the core. More seriously, if the network is not fully connected, the shortest path distance between partial node pairs cannot be obtained.If the iterative information is used to identify the position difference of nodes in the network, the propagation ability of nodes with the sameks value can be further distinguished. Degree decomposition method based on the iteration factor is proposed to improve the performance of the traditional method by using iteration information and node degree in decomposition. It is worth noting that the degree is a local variable and the iteration factor is a global variable. This method fully combines local and global factors to identify influential nodes more effectively. The iterative factor δi of node i is(3)δi=ksi∗1+iterim,where m is the total number of iterations in K-shell decomposition and iteri is the number of times that node i has been removed from the decomposition. The influence of node i in the degree decomposition method based on iterative factor is(4)ICi=δi∗di+∑j∈Γiδj∗dj.The influence of node will be great if a node has many neighbors at the core of the network. Based on this assumption, the neighbor core of the node is(5)Cnci=∑j∈Γiksj,where Γi is the neighbor of node i. Recursively, the extended neighbor kernel is defined as(6)Cnc+i=∑j∈ΓiCncj.


## 3. Materials and Methods

Practice has proved that the combination of multiple attributes can further improve the sorting effect. In recent years, researchers have combined different attributes and strategies to mine the influence of nodes. The performance of these methods proves that considering multiple attributes is an effective strategy to evaluate the impact capability of nodes. At present, there are many attribute weighting methods, such as least squares weighting method and principal component analysis method. Among the many attributes of nodes, location attributes play a significant role in the sorting process of nodes. At the same time, the influencing ability of nodes depends largely on the neighbor attributes. Combining these two attributes, it is an effective strategy to use the attribute weighting method to further identify the influence of nodes.In the K-shell decomposition process, the number of iterations reveals very important location information, and it can further distinguish the location differences of the removed nodes. A node with a higher number of iterations is closer to the core of the network, or it is closer to the edge of the network. The number of iterations here refers to the number of global iterations decomposed from K-shell to the end. In this paper, sigmod function is used to further process the number of iterations when the node is deleted, so as to define the node position indexpi:(7)pi=3411+e−iteri.The relationship between the position index and the number of iterations is shown in Figure2. As the number of iterations increases, the position index increases in a downward slope with a critical value of 0.75.Figure 2
The diagram of the relationship between iteration number and position index.The position attribute of the node is represented byPNpi, which is composed of the ks value of the node and the sum of the location index of the neighbor of the node:(8)PNpi=ksi+∑j∈Γipj,where ksi is the ks value of the node in the K-shell decomposition.The position attribute of a node cannot effectively distinguish the influence of a node in the same position. For example, all nodes on the edge of a network have the same position information, so their influence should be the same. In fact, due to the difference of local structure, the influence of edge nodes in the same position will vary greatly. The local attributes of nodes should be further used to distinguish the influence differences of nodes with the same location attributes. If a node has more neighbors, it can have a greater impact on the network. Furthermore, the influence of a node’s neighbor is also impacted by its neighbors. Consider the second-order neighbor can improve the capability of measuring the influence of a node.The neighbor attribute of a node is represented byPNni, and it is represented by the second-order neighbor number of the node:(9)PNni=∑j∈Γi∑l∈Γjkl,where kl represents the degree of node l.Both position attribute and local attribute play a significant role in identifying the influence of nodes. Combining these two key attributes, the influence of nodes can be accurately calculated and the performance of node influence ranking can be further improved. Many traditional multiattribute sorting methods treat all attribute weights to be consistent. At the same time, there are many weighting methods, such as analytic hierarchy process, multiobjective programming, principal component analysis, and weighted least square method. Information entropy weighting method is an excellent weighting method, which has been verified by many examples. Our method adapts the method of information entropy weighting to avoid the defects of the traditional weighting method:(10)PNi=w1∗PNpi+w2∗PNni,where w1 represents the weight of the location attribute and w2 represents the weight of the neighbor attribute.The calculation process of information entropy weighting method is as follows. First, the entropy value of each attribute is calculated:(11)Hi=−1lnn∑j=1nrijlnrij,i=1,2,where Hi represents the entropy of the ith attribute, and rij represents the normalized value of the ith attribute of the jth node. Because this method has only location and neighbor attributes, i is set as 1 and 2:(12)r1j=PNpj∑j=1nPNpj,r2j=PNnj∑j=1nPNnj.Then, the information entropy is combined to calculate the weight of the two attributes:(13)wi=1−Hi2−∑iHi,i=1,2.Whether the multiattribute-improved K-shell algorithm proposed in this section is feasible, the feasibility can be explained with the help of diagrams. The graph is an undirected graph with 16 nodes and 20 edges. The PN value of each node is calculated according to the algorithm. The values in the calculation process are shown in Table1. As we can see from the table, the importance of all nodes can be sorted in the descending order according to the PN value. The PN values of node 11 and node 12 are the same and their importance cannot be distinguished. The PN values of nodes 1, 2, 3, and 4 are in the first gradient, and the PN value of node 2 is the largest. Its importance can be seen in Figure 1 in the network. PN values of nodes 5, 6, 7, and 8 are located in the second gradient. These nodes are not outer edge nodes.Table 1
Example verification results of K-shell-improved algorithm based on multiple or inner core nodes.
NodeksIteriPNpiPNniPNi1355.0327444859446495036.799446735506792356.3539401029114736648.4903481057996763355.6933422944280615943.351338182634644356.2416362284005656447.044498742008895243.97543521861567363425.1860116409371036243.88647323777079823223.7470145056648337243.9584852525099833626.5939173457655048132.8122140043361331914.2479258779049569111.637255914817378975.42571693266510410122.7338437827623867139.98627500348794511111.603322261880217654.00287387140285812111.603322261880217654.00287387140285813111.660597808483411996.845450685146440514111.67758149531488291611.79552173718132315122.208891742455916139.83217048253927416111.603322261880217643.2964331094214456The PN value of node 14 is larger than that of edge nodes 9, 11, 12, 13, and 16. It can be seen from the figure that since it is directly connected to core node 4, its influence has been enhanced. From the calculation results shown in Table1, it can be preliminarily concluded that the improved K-shell method based on multiple attributes is feasible to some extent.


## 4. Experimental Setup

### 4.1. Data Description

We conduct several experiments on six different real networks to evaluate the performance of our proposed centrality measure. The real networks are drawn from disparate fields. CA-HepTh [25] is a collaboration network of Arxiv High Energy Physics Theory. Netscience [25] is the network of co-authorship of scientists in network theory and experiments. Cond-Mat [25] is from the e-print arXiv and covers scientific collaborations between authors papers submitted to Condense Matter category. DNC Email [26] is the network of emails in the 2016 Democratic National Committee email leak. Nodes in the network correspond to persons in the dataset and the edge is the mail exchange between users. Ego-Twitter [27] contains Twitter user-user following information. A node represents a user and an edge indicates that the user follows the other user. Route Views [28] is the network of autonomous systems of the Internet connected with each other. Nodes are autonomous systems (AS), and edges denote communication. A brief overview of the networks is shown in Table 2.Table 2
The basic topological features of four real network datasets.
NetworkNMKKmaxCrβthβCA-HepTh9877519715.26650.470.2680.0870.12Netscience3799144.82430.74−0.0820.1420.25Cond-Mat16264475955.851070.620.1850.0840.14DNC Email202955984.724048.9−0.3070.0140.08Ego-Twitter23370331012.832392.15−0.4780.0270.08Route Views6474138954.314590.96−0.1820.0070.06N and M are the numbers of nodes and edges, respectively. K and Kmax denote the average degree and the maximum degree. C and r are the clustering coefficient [29] and assortative coefficient [30]. βth and β are the epidemic threshold of network and the infection probability used in our experiment.


### 4.2. Spreading Model

To evaluate the lists ranked by all the centrality measures, we need to know the list ranked by the real spreading process of the nodes. In the spreading process, the probability of accepting a message from another user depends on the user’s influence [31]. So, the spreading efficiency of nodes is used to measure the ranking result of influential nodes. There are many information diffusion models, such as SIR model, Independent Cascade model, and Linear Threshold model, and some information diffusion models independent of network topology [32, 33]. In this paper, we employ the standard SIR model [34] to simulate the spreading process on networks and record the spreading efficiency for every node. In the SIR model, every node belongs to one of the susceptible states, the infected state or the recovered state. In detail, we set one node as an infected node and the other nodes are susceptible nodes. At each step, for every infected node, it can infect its susceptible neighbors with infection probability β and then can be removed with probability λ. Generally, we set λ=1.0. The appropriate propagation probabilities are needed to be chosen, in case too small or too large propagation probability makes the propagation effect not ideal and leads to the failure to distinguish the influence of nodes. According to the heterogenous mean-field method, the epidemic threshold of network is βth=<k>/<k2>−<k>. k and k2 are degree and second-order degree of node. The propagation probabilities are set just larger than the epidemic threshold. In the experiment, this dynamical process of infection and recovering will repeat until there are no infected nodes. The sum of infected and recovered nodes at time t, denoted by Ft, can be considered as an indicator to evaluate the influence of the initially infected node at time t. Obviously, Ft increases with the increasing of t and will reach stable state at time tc, denoted by Ftc, where tc represents the final time and Ftc represents the eventual influence of the initially infected node. To guarantee the reliability of the results, all of them are averaged over a large number of realizations.


### 4.3. Evaluation

In order to evaluate the performance of the centrality measures, we use Kendall’s coefficientτ [35] to measure the correlation between one topology-based ranking list and the one generated by the SIR model, which is approached by a large number of simulations. Let xi,yi and xj,yj be a randomly selected pair of joint from two ranking list, X and Y, respectively. If both xi>xj and yi>yj or if both xi<xj and yi<yj, they are said to be concordant. If xi>xj and yi<yj or xi<xj and yi>yj, they are said to be discordant. If xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s coefficient τ is defined as(14)τ=nc−nd0.5nn−1,where nc and nd denote the number of concordant and discordant pairs, respectively. The value τ lies between +1 and −1. The higher the τ value indicates, the more accurate ranked list a centrality measure could generate. The most ideal case is τ=1, where the ranked list generated by the centrality measure is exactly the same as the ranked list generated by the real spreading process.To measure the imprecision [17] of methods in ranking influential nodes, we compare propagation capability of influential nodes obtained by ranking result with nodes which have largest propagation capability and the propagation capability of nodes generated from the SIR model. Kendall’s correlation coefficient considers the correlation between the ranking order of all nodes in the network and the order of propagation capability of all nodes. However, the imprecision function is used to evaluate the cumulative propagation capability of top-ranked nodes in different proportions. The imprecision function εp is defined as(15)εp=1−∑i∈ϕmpFitc∑j∈ϕspFjtc,where p is the proportion of top-ranked nodes and ϕmp and ϕsp denote the set of nodes at the top when proportion is p. Fitc is propagation capability of node i. The value of ε lies between 0 and 1. The lower ε value indicates, the more precise the centrality measure is in ranking propagation capability of node.


## 4.1. Data Description

We conduct several experiments on six different real networks to evaluate the performance of our proposed centrality measure. The real networks are drawn from disparate fields. CA-HepTh [25] is a collaboration network of Arxiv High Energy Physics Theory. Netscience [25] is the network of co-authorship of scientists in network theory and experiments. Cond-Mat [25] is from the e-print arXiv and covers scientific collaborations between authors papers submitted to Condense Matter category. DNC Email [26] is the network of emails in the 2016 Democratic National Committee email leak. Nodes in the network correspond to persons in the dataset and the edge is the mail exchange between users. Ego-Twitter [27] contains Twitter user-user following information. A node represents a user and an edge indicates that the user follows the other user. Route Views [28] is the network of autonomous systems of the Internet connected with each other. Nodes are autonomous systems (AS), and edges denote communication. A brief overview of the networks is shown in Table 2.Table 2
The basic topological features of four real network datasets.
NetworkNMKKmaxCrβthβCA-HepTh9877519715.26650.470.2680.0870.12Netscience3799144.82430.74−0.0820.1420.25Cond-Mat16264475955.851070.620.1850.0840.14DNC Email202955984.724048.9−0.3070.0140.08Ego-Twitter23370331012.832392.15−0.4780.0270.08Route Views6474138954.314590.96−0.1820.0070.06N and M are the numbers of nodes and edges, respectively. K and Kmax denote the average degree and the maximum degree. C and r are the clustering coefficient [29] and assortative coefficient [30]. βth and β are the epidemic threshold of network and the infection probability used in our experiment.


## 4.2. Spreading Model

To evaluate the lists ranked by all the centrality measures, we need to know the list ranked by the real spreading process of the nodes. In the spreading process, the probability of accepting a message from another user depends on the user’s influence [31]. So, the spreading efficiency of nodes is used to measure the ranking result of influential nodes. There are many information diffusion models, such as SIR model, Independent Cascade model, and Linear Threshold model, and some information diffusion models independent of network topology [32, 33]. In this paper, we employ the standard SIR model [34] to simulate the spreading process on networks and record the spreading efficiency for every node. In the SIR model, every node belongs to one of the susceptible states, the infected state or the recovered state. In detail, we set one node as an infected node and the other nodes are susceptible nodes. At each step, for every infected node, it can infect its susceptible neighbors with infection probability β and then can be removed with probability λ. Generally, we set λ=1.0. The appropriate propagation probabilities are needed to be chosen, in case too small or too large propagation probability makes the propagation effect not ideal and leads to the failure to distinguish the influence of nodes. According to the heterogenous mean-field method, the epidemic threshold of network is βth=<k>/<k2>−<k>. k and k2 are degree and second-order degree of node. The propagation probabilities are set just larger than the epidemic threshold. In the experiment, this dynamical process of infection and recovering will repeat until there are no infected nodes. The sum of infected and recovered nodes at time t, denoted by Ft, can be considered as an indicator to evaluate the influence of the initially infected node at time t. Obviously, Ft increases with the increasing of t and will reach stable state at time tc, denoted by Ftc, where tc represents the final time and Ftc represents the eventual influence of the initially infected node. To guarantee the reliability of the results, all of them are averaged over a large number of realizations.


## 4.3. Evaluation

In order to evaluate the performance of the centrality measures, we use Kendall’s coefficientτ [35] to measure the correlation between one topology-based ranking list and the one generated by the SIR model, which is approached by a large number of simulations. Let xi,yi and xj,yj be a randomly selected pair of joint from two ranking list, X and Y, respectively. If both xi>xj and yi>yj or if both xi<xj and yi<yj, they are said to be concordant. If xi>xj and yi<yj or xi<xj and yi>yj, they are said to be discordant. If xi=xj or yi=yj, the pair is neither concordant nor discordant. Kendall’s coefficient τ is defined as(14)τ=nc−nd0.5nn−1,where nc and nd denote the number of concordant and discordant pairs, respectively. The value τ lies between +1 and −1. The higher the τ value indicates, the more accurate ranked list a centrality measure could generate. The most ideal case is τ=1, where the ranked list generated by the centrality measure is exactly the same as the ranked list generated by the real spreading process.To measure the imprecision [17] of methods in ranking influential nodes, we compare propagation capability of influential nodes obtained by ranking result with nodes which have largest propagation capability and the propagation capability of nodes generated from the SIR model. Kendall’s correlation coefficient considers the correlation between the ranking order of all nodes in the network and the order of propagation capability of all nodes. However, the imprecision function is used to evaluate the cumulative propagation capability of top-ranked nodes in different proportions. The imprecision function εp is defined as(15)εp=1−∑i∈ϕmpFitc∑j∈ϕspFjtc,where p is the proportion of top-ranked nodes and ϕmp and ϕsp denote the set of nodes at the top when proportion is p. Fitc is propagation capability of node i. The value of ε lies between 0 and 1. The lower ε value indicates, the more precise the centrality measure is in ranking propagation capability of node.


## 5. Results and Discussion

In this chapter, SIR model, Kendall coefficient, and imprecision function are used to verify the performance of the proposed method. Degree, Ks (K-shell), MDD (Mixed Degree Decomposition), ksIF (K-shell iteration factor method), and Cnc+ (Extended Neighborhood coreness centrality measure) were compared with the proposed multiattribute PN method.


### 5.1. Evaluate the Spreading Capability of Nodes

This section verifies that different propagation probabilities are selected under the fixed proportion of transmission sources to calculate the propagation capability of the influence node set. By comparing the propagation capability of different algorithms under the same propagation probability, the performance of different methods can be compared. The simulation set the propagation source ratio as 0.1. The max time step of infection process is set as 100, but the infection will stop when there is no user in the infection state. The results were based on an average of 500 independent experiments. The simulation results are shown in Figure3. The abscissa is the propagation probability and the ordinate is the propagation capability, which is expressed as a percentage.Figure 3
The propagation capability graph of the five methods under different propagation probabilities. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f). The green vertical line is the epidemic threshold of the corresponding network.
(a)(b)(c)(d)(e)(f)Firstly, with the increasement of the propagation probability, the node propagation ability of the six methods is improved. The performance of the six methods is relatively close when the propagation probability is small and obviously different when the propagation probability is large. Specifically, in the CA-HepTh, DNC Email, and Cond-Mat, the performance of PN maintained the best under various propagation probabilities. In the Ego-Twitter dataset, the performance of PN and Cnc+ is significantly higher than that of the other four methods. Moreover, when the transmission probability is 0.03, the node transmission ability of Cnc+ is higher, and in other cases, the node transmission ability of PN method is higher. In the Netscience and Route Views dataset, the performance of PN is relatively better than the other method, but Cnc + outperforms the PN method when the transmission probability is less than 0.1 in the Netscience. PN is not the best in several points in Route Views, but it had highest propagation ability in most cases, as shown in Figure3(f). In general, the proposed PN in this chapter has better performance. The difference in performance is related to the specific network structure.


### 5.2. Evaluate the Imprecision of Ranking

This section verifies that different proportions of top-ranked nodes are selected under the fixed propagation probability to calculate the imprecision of ranking the influence of nodes. By comparing the imprecision of different algorithms under the same proportion of top-ranked, the performance of different methods in ranking the influence of nodes can be distinguished. The simulation set the propagation probability of node, as shown in Table2, and the proportion top-ranked nodes varies from 0.01 to 0.2. The max time step of infection process set as 100 and the results were based on an average of 500 independent experiments. Simulation results in six networks are shown in Figure 4. The abscissa is the proportion of top-ranked nodes that are considered and the ordinate is the imprecision of ranking.Figure 4
The imprecision of six ranking methods with different proportion of top-ranked nodes. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)In Figure4(a), the method PN, KsIF, and Cnc + have low imprecision when p is higher than 0.02 and they have poor performance in identifying the 2% top-ranked nodes. However, the imprecision of PN is much lower than the other two in CA-HepTh dataset. The imprecision of Degree to rank top 1% nodes is low about 0.07 than the method PN. However, Degree has highest ε when p is greater than 0.04. In Netscience and Cond-Mat, Degree, K-shell, and MDD have higher value, and PN is lowest in most p except that p is in the range of 0.02 to 0.04, KsIF outperforms PN in Netscience. When p is larger than 0.04 and smaller than 0.06, Cnc + outperforms PN in Cond-Mat. In the dataset, DNC Email, K-shell, and PN are better compared with other method, and K-shell has a slight edge when p between 0.04 and 0.1 or 0.13 and 0.15. However, K-shell performs poor in 3% top-ranked nodes. In the dataset, Ego-Twitter and Route Views, it is obvious that the method we proposed performs well and is more stable in all cases. From the simulation results of the abovementioned six datasets, it can be seen that the method PN can not only precisely identify most of the top 1% to 4% nodes but also rank the following nodes by their influence stably.


### 5.3. Evaluate the Correlation Coefficients of Method

This section verifies the correlation between the influence value and propagation ability of nodes under different propagation probabilities by Kendall’s coefficientτ. The value range of propagation probability in this simulation is 0.02 to 0.2 in the datasets CA-HepTh, Cond-Mat, DNC Email, Ego-Twitter, and Route Views, and extended to 0.3 in the dataset Netscience because of higher epidemic threshold of it. In the DNC Email and Route Views, we also put the simulation result when the value of propagation probability is equal to their epidemic threshold. The max time step of infection process is 100. The results were based on an average of 500 independent experiments. The simulation results are shown in Figure 5. The abscissa is the propagation probability and the ordinate is the correlation coefficient. The epidemic threshold of each network is also drawn into the figure as a vertical line.Figure 5
The correlation coefficient variation diagram of the six methods under different propagation probabilities. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f). The green vertical line is the epidemic threshold of the corresponding network.
(a)(b)(c)(d)(e)(f)The correlation of ranking result of different methods and real propagation abilities obtained by the SIR model has different manifestations in different datasets, but the general trend is the same. When the propagation probability is small, the ranking correlation of Degree, K-shell, and MDD with real propagation ability is higher than the other three methods and the thresholds are roughly the same as the epidemic thresholdβth of network. It can be seen in Figure 5 that the Degree has high Kendall’s coefficient τ when β is less than 0.06 in the CA-HepTh and Cond-Mat and less than 0.07 in the Netscience, and it is not obvious in other three networks because of the small epidemic threshold. However, in the cases where β is higher than βth, these methods that have considered both degree and other aspects such as the influence of neighbors to the spreading ability of nodes perform better than the method that mainly take degree into account. This is because the very small propagation probability will make the infection behaviour in a small range near the initial infected node, unable to spread over a large area, so the degree is the decisive factor. As the probability of propagation increases, the act of infection becomes easier, so the extent of infection depends not only on the number of neighbors of a node but also on the ability of its neighbors to propagate, or even the neighbors’ neighbors. On the contrary, when the propagation probability increases to a point much larger than βth of network, infection becomes too easy so that the nodes in the core of the network or with high degree had largest scope of infection. It is clearly shown in the networks with small epidemic threshold such as DNC Email and Route Views in the figure. When β>βth, the method PN has the highest Kendall’s coefficient t in CA-HepTh, Netscience, and Cond-Mat. Our proposed method also performs best when β is between 0.06 to 0.14 in DNC Email and between 0.06 to 0.18 in Route Views. In short, compared with the other five methods, the PN method proposed in this chapter has good performance under the appropriate propagation probability value range.


### 5.4. Evaluate the Performance of Selecting Seeds in Influence Maximization Problem

This section verifies the reliability of PN when it is applied in the influence maximization problem. Maximization of influence is widely used in real life. For example, viral marketing is a typical application that can promote new products or ideas for merchants or publicity departments. It aims to select a group of nodes in the network called seed node set as initial propagation nodes and spread in the network as widely as possible according to a certain diffusion mode. There are many related studies. We use the selection of top from the ranking to specify seed nodes to measure the propagation range of seed nodes selected by several ranking methods. We examine the spreading efficiency of different seed node set with six real networks: CA-HepTh, Netscience, Cond-Mat, DNC Email, Ego-Twitter, and Route Views.In the experiment, we setP as the proportion of seed nodes in the whole network, ranging from 0.01 to 0.05. We also used the SIR Model to simulate the propagation process and calculated the influence range by using the number of users who were finally infected. The propagation probability in the simulation is determined according to the epidemic threshold and is shown in Table 2. The max time step of infection process is set as 100 and the results were based on an average of 500 independent experiments. The simulation results are shown in Figure 6. The abscissa is the ratio of the seed set in all users, and the ordinate is the propagation scope of initial seed nodes and expressed as a percentage.Figure 6
The performance of selecting seeds of the six methods in influence maximization problem. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)The results manifest that the PN method performs best in the datasets Cond-Mat, DNC Email, Ego-Twitter, and Route Views. In the CA-HepTh dataset, the seed set selected by the method PN whenP is greater than 0.02 can infect wilder than others. When P is 0.02 and below, degree is most effective and the PN is better than KsIF an Cnc+. In the Netscience network, KsIF is best when P is 0.03 and 0.04, and the infected rate of seeds selected by PN is almost same as KsIF in other cases.


### 5.5. Measure the Ranking Uniqueness and Distribution

This section verifies the monotonicity of the new method on the sorting by using Bae and Kim’s ranking monotonicity method [23]. Since the K-shell method will calculate the K-shell value of many nodes into the same value, it is difficult to distinguish their differences in influence. In this respect, the method we proposed can do better. According to the definition of Bae and Kim, the monotonicity of the ranking result is expressed as follows:(16)MR=1−∑r∈Rnrnr−1nn−12.In (16), R represents the ranking list and n is the size of it, every element of the ranking list is a set of nodes that have the same ranking value, and nr is the number of nodes in R that have the same ranking position r. The value of MR fluctuates between 0,1 and the higher the value, the stronger the uniqueness. In extreme cases, 1 means that each node is assigned a different sort value, whereas 0 is the opposite and all nodes are in the same rank.We examine the monotonicity of different methods with the same six datasets as above. The calculation results are shown in Table3. It can be seen from the table that the monotonicity result of the PN is apparently higher than the degree, ks and MDD, and approximate to KsIF and Cnc+.Table 3
The monotonicityM (R) of six real networks, R is representing the ranking vector of different methods.
NetworkM (Degree)M (Ks)MMDDM (KsIF)MCnc+M (PN)CA-HepTh0.7626830.6742370.810570.9924160.9888760.993566Netscience0.7642060.6420830.8215270.9947020.9893070.995036Cond-Mat0.8090540.7408790.860480.9941380.9914070.994788DNC Email0.3397620.323440.3445650.9360820.9360280.936465Ego-Twitter0.1314630.1223070.1316560.9955740.9913220.996321Route Views0.5871740.5496220.6086710.9932850.9925480.993893In order to clarify the ranking distribution of the different measures more clearly, a complementary cumulative distribution function (CCDF) is plotted. According to the CCDF principle, if many nodes are in the same rank, the CCDF plot will decrease rapidly; otherwise, the CCDF plot will slow down. Figure7 shows the ranking distribution in six networks.Figure 7
The complementary cumulative distribution (CCDF) of the six methods in six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)The line representing Degree,ks, or MDD drop sharply, as can be seen on the left side of each graph. This is especially true when the number of nodes in the dataset is large. For the method PN, the ranking distribution is slightly improved compared with Cnc+ and KsIF in datasets DNC Email and Route Views. The curves of KsIF and PN in the dataset Netscience are basically overlapping and drop off more slowly than that of Cnc+. In the dataset CA-HepTh and Cond-Mat, the method Cnc+ also does not perform well compared to the method KsIF and PN. The KsIF and PN are equally good at identifying the influential nodes, while in the latter part of the ranking, the downward trend of KsIF curve is more obvious than that of PN curve. It is indicated that the ability of method PN to distinguish the nodes’ spreading capability is better than Cnc+. It can be seen in the Ego-Twitter that the performance of PN is better than the method Cnc+. So, we can say that PN performs well in most networks.


## 5.1. Evaluate the Spreading Capability of Nodes

This section verifies that different propagation probabilities are selected under the fixed proportion of transmission sources to calculate the propagation capability of the influence node set. By comparing the propagation capability of different algorithms under the same propagation probability, the performance of different methods can be compared. The simulation set the propagation source ratio as 0.1. The max time step of infection process is set as 100, but the infection will stop when there is no user in the infection state. The results were based on an average of 500 independent experiments. The simulation results are shown in Figure3. The abscissa is the propagation probability and the ordinate is the propagation capability, which is expressed as a percentage.Figure 3
The propagation capability graph of the five methods under different propagation probabilities. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f). The green vertical line is the epidemic threshold of the corresponding network.
(a)(b)(c)(d)(e)(f)Firstly, with the increasement of the propagation probability, the node propagation ability of the six methods is improved. The performance of the six methods is relatively close when the propagation probability is small and obviously different when the propagation probability is large. Specifically, in the CA-HepTh, DNC Email, and Cond-Mat, the performance of PN maintained the best under various propagation probabilities. In the Ego-Twitter dataset, the performance of PN and Cnc+ is significantly higher than that of the other four methods. Moreover, when the transmission probability is 0.03, the node transmission ability of Cnc+ is higher, and in other cases, the node transmission ability of PN method is higher. In the Netscience and Route Views dataset, the performance of PN is relatively better than the other method, but Cnc + outperforms the PN method when the transmission probability is less than 0.1 in the Netscience. PN is not the best in several points in Route Views, but it had highest propagation ability in most cases, as shown in Figure3(f). In general, the proposed PN in this chapter has better performance. The difference in performance is related to the specific network structure.


## 5.2. Evaluate the Imprecision of Ranking

This section verifies that different proportions of top-ranked nodes are selected under the fixed propagation probability to calculate the imprecision of ranking the influence of nodes. By comparing the imprecision of different algorithms under the same proportion of top-ranked, the performance of different methods in ranking the influence of nodes can be distinguished. The simulation set the propagation probability of node, as shown in Table2, and the proportion top-ranked nodes varies from 0.01 to 0.2. The max time step of infection process set as 100 and the results were based on an average of 500 independent experiments. Simulation results in six networks are shown in Figure 4. The abscissa is the proportion of top-ranked nodes that are considered and the ordinate is the imprecision of ranking.Figure 4
The imprecision of six ranking methods with different proportion of top-ranked nodes. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)In Figure4(a), the method PN, KsIF, and Cnc + have low imprecision when p is higher than 0.02 and they have poor performance in identifying the 2% top-ranked nodes. However, the imprecision of PN is much lower than the other two in CA-HepTh dataset. The imprecision of Degree to rank top 1% nodes is low about 0.07 than the method PN. However, Degree has highest ε when p is greater than 0.04. In Netscience and Cond-Mat, Degree, K-shell, and MDD have higher value, and PN is lowest in most p except that p is in the range of 0.02 to 0.04, KsIF outperforms PN in Netscience. When p is larger than 0.04 and smaller than 0.06, Cnc + outperforms PN in Cond-Mat. In the dataset, DNC Email, K-shell, and PN are better compared with other method, and K-shell has a slight edge when p between 0.04 and 0.1 or 0.13 and 0.15. However, K-shell performs poor in 3% top-ranked nodes. In the dataset, Ego-Twitter and Route Views, it is obvious that the method we proposed performs well and is more stable in all cases. From the simulation results of the abovementioned six datasets, it can be seen that the method PN can not only precisely identify most of the top 1% to 4% nodes but also rank the following nodes by their influence stably.


## 5.3. Evaluate the Correlation Coefficients of Method

This section verifies the correlation between the influence value and propagation ability of nodes under different propagation probabilities by Kendall’s coefficientτ. The value range of propagation probability in this simulation is 0.02 to 0.2 in the datasets CA-HepTh, Cond-Mat, DNC Email, Ego-Twitter, and Route Views, and extended to 0.3 in the dataset Netscience because of higher epidemic threshold of it. In the DNC Email and Route Views, we also put the simulation result when the value of propagation probability is equal to their epidemic threshold. The max time step of infection process is 100. The results were based on an average of 500 independent experiments. The simulation results are shown in Figure 5. The abscissa is the propagation probability and the ordinate is the correlation coefficient. The epidemic threshold of each network is also drawn into the figure as a vertical line.Figure 5
The correlation coefficient variation diagram of the six methods under different propagation probabilities. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f). The green vertical line is the epidemic threshold of the corresponding network.
(a)(b)(c)(d)(e)(f)The correlation of ranking result of different methods and real propagation abilities obtained by the SIR model has different manifestations in different datasets, but the general trend is the same. When the propagation probability is small, the ranking correlation of Degree, K-shell, and MDD with real propagation ability is higher than the other three methods and the thresholds are roughly the same as the epidemic thresholdβth of network. It can be seen in Figure 5 that the Degree has high Kendall’s coefficient τ when β is less than 0.06 in the CA-HepTh and Cond-Mat and less than 0.07 in the Netscience, and it is not obvious in other three networks because of the small epidemic threshold. However, in the cases where β is higher than βth, these methods that have considered both degree and other aspects such as the influence of neighbors to the spreading ability of nodes perform better than the method that mainly take degree into account. This is because the very small propagation probability will make the infection behaviour in a small range near the initial infected node, unable to spread over a large area, so the degree is the decisive factor. As the probability of propagation increases, the act of infection becomes easier, so the extent of infection depends not only on the number of neighbors of a node but also on the ability of its neighbors to propagate, or even the neighbors’ neighbors. On the contrary, when the propagation probability increases to a point much larger than βth of network, infection becomes too easy so that the nodes in the core of the network or with high degree had largest scope of infection. It is clearly shown in the networks with small epidemic threshold such as DNC Email and Route Views in the figure. When β>βth, the method PN has the highest Kendall’s coefficient t in CA-HepTh, Netscience, and Cond-Mat. Our proposed method also performs best when β is between 0.06 to 0.14 in DNC Email and between 0.06 to 0.18 in Route Views. In short, compared with the other five methods, the PN method proposed in this chapter has good performance under the appropriate propagation probability value range.


## 5.4. Evaluate the Performance of Selecting Seeds in Influence Maximization Problem

This section verifies the reliability of PN when it is applied in the influence maximization problem. Maximization of influence is widely used in real life. For example, viral marketing is a typical application that can promote new products or ideas for merchants or publicity departments. It aims to select a group of nodes in the network called seed node set as initial propagation nodes and spread in the network as widely as possible according to a certain diffusion mode. There are many related studies. We use the selection of top from the ranking to specify seed nodes to measure the propagation range of seed nodes selected by several ranking methods. We examine the spreading efficiency of different seed node set with six real networks: CA-HepTh, Netscience, Cond-Mat, DNC Email, Ego-Twitter, and Route Views.In the experiment, we setP as the proportion of seed nodes in the whole network, ranging from 0.01 to 0.05. We also used the SIR Model to simulate the propagation process and calculated the influence range by using the number of users who were finally infected. The propagation probability in the simulation is determined according to the epidemic threshold and is shown in Table 2. The max time step of infection process is set as 100 and the results were based on an average of 500 independent experiments. The simulation results are shown in Figure 6. The abscissa is the ratio of the seed set in all users, and the ordinate is the propagation scope of initial seed nodes and expressed as a percentage.Figure 6
The performance of selecting seeds of the six methods in influence maximization problem. The experiments are simulated on six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC Email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)The results manifest that the PN method performs best in the datasets Cond-Mat, DNC Email, Ego-Twitter, and Route Views. In the CA-HepTh dataset, the seed set selected by the method PN whenP is greater than 0.02 can infect wilder than others. When P is 0.02 and below, degree is most effective and the PN is better than KsIF an Cnc+. In the Netscience network, KsIF is best when P is 0.03 and 0.04, and the infected rate of seeds selected by PN is almost same as KsIF in other cases.


## 5.5. Measure the Ranking Uniqueness and Distribution

This section verifies the monotonicity of the new method on the sorting by using Bae and Kim’s ranking monotonicity method [23]. Since the K-shell method will calculate the K-shell value of many nodes into the same value, it is difficult to distinguish their differences in influence. In this respect, the method we proposed can do better. According to the definition of Bae and Kim, the monotonicity of the ranking result is expressed as follows:(16)MR=1−∑r∈Rnrnr−1nn−12.In (16), R represents the ranking list and n is the size of it, every element of the ranking list is a set of nodes that have the same ranking value, and nr is the number of nodes in R that have the same ranking position r. The value of MR fluctuates between 0,1 and the higher the value, the stronger the uniqueness. In extreme cases, 1 means that each node is assigned a different sort value, whereas 0 is the opposite and all nodes are in the same rank.We examine the monotonicity of different methods with the same six datasets as above. The calculation results are shown in Table3. It can be seen from the table that the monotonicity result of the PN is apparently higher than the degree, ks and MDD, and approximate to KsIF and Cnc+.Table 3
The monotonicityM (R) of six real networks, R is representing the ranking vector of different methods.
NetworkM (Degree)M (Ks)MMDDM (KsIF)MCnc+M (PN)CA-HepTh0.7626830.6742370.810570.9924160.9888760.993566Netscience0.7642060.6420830.8215270.9947020.9893070.995036Cond-Mat0.8090540.7408790.860480.9941380.9914070.994788DNC Email0.3397620.323440.3445650.9360820.9360280.936465Ego-Twitter0.1314630.1223070.1316560.9955740.9913220.996321Route Views0.5871740.5496220.6086710.9932850.9925480.993893In order to clarify the ranking distribution of the different measures more clearly, a complementary cumulative distribution function (CCDF) is plotted. According to the CCDF principle, if many nodes are in the same rank, the CCDF plot will decrease rapidly; otherwise, the CCDF plot will slow down. Figure7 shows the ranking distribution in six networks.Figure 7
The complementary cumulative distribution (CCDF) of the six methods in six different datasets: CA-HepTh (a), Netscience (b), Cond-Mat (c), DNC email (d), Ego-Twitter (e), and Route Views (f).
(a)(b)(c)(d)(e)(f)The line representing Degree,ks, or MDD drop sharply, as can be seen on the left side of each graph. This is especially true when the number of nodes in the dataset is large. For the method PN, the ranking distribution is slightly improved compared with Cnc+ and KsIF in datasets DNC Email and Route Views. The curves of KsIF and PN in the dataset Netscience are basically overlapping and drop off more slowly than that of Cnc+. In the dataset CA-HepTh and Cond-Mat, the method Cnc+ also does not perform well compared to the method KsIF and PN. The KsIF and PN are equally good at identifying the influential nodes, while in the latter part of the ranking, the downward trend of KsIF curve is more obvious than that of PN curve. It is indicated that the ability of method PN to distinguish the nodes’ spreading capability is better than Cnc+. It can be seen in the Ego-Twitter that the performance of PN is better than the method Cnc+. So, we can say that PN performs well in most networks.


## 6. Conclusions

On the basis of the K-shell method, we proposed a new multiattribute ranking method based on node position and neighborhood. We made full use of the iterative information in the decomposition process. First, the iteration information is processed by sigmod function to obtain the position index. The position attribute is obtained by combining the shell value and the position index. Then, the local information of the node is adopted to obtain the neighbor property. Furthermore, the position attribute and neighbor attribute are weighted by the method of information entropy weighting. Finally, we evaluated the propagation capability of different propagation probabilities, the imprecision of different proportions, the correlation coefficient of different propagation probabilities, and the propagation capability of selected seed nodes in influence maximization problem. At the same time, we also verified the good performance of our method in distinguishing influence of nodes. Compared with other K-shell decomposition and its improved algorithms, the method proposed in this paper had better performance. Through simulation experiments, it is found that the PN method can make full use of the iterative information in the decomposition process and the influence of neighbors to further distinguish the difference of nodes with the sameks value. Experiments with SIR model, Kendall’s coefficient, and imprecision function fully verified the correctness and effectiveness of the proposed method. In a word, the effectiveness of the proposed method in the identification of influence nodes was verified by various forms of experiments.



---

*Source: 5903798-2020-06-08.xml*