# Identifying and Ranking Influential Nodes in Complex Networks Based on Dynamic Node Strength
## 3 Experimental Results
### Evaluation Methodologies  
First, we apply the monotonicity index, \(M(R)\), in [26] to evaluate resolution ratio of different ranking methods, as follows:  
\[M(R)=\left[1-\frac{\sum_{r\in R}n_{r}(n_{r}-1)}{n(n-1)}\right]^{2}, \tag{5}\]  
where \(R\) is ranking vector ranking method, \(n\) is the size of \(R\) and \(n_{r}\) is the number of nodes in ties with the same rank \(r\). This index quantifies proportion of ties in \(R\). The \(M(R)\) is 0 if all nodes are assigned to one rank, while it is 1 if each node is assigned to a different rank. The closer the \(M(R)\) is to 1, the better the resolution ratio of the ranking method is.  
We remark that there are various spreading processes on networks such as epidemic, rumor, information spreading and so on. In the previous works, the method of decom  
Figure 2: A sample to illustrate the procedure of DNSD. The nodes with dashed nodes are the removed nodes and the edges with dashed line are the vanishing edges and weight.  
posing network is proved to be suitable for the epidemic spreading process [31; 40]. In this article, we apply SIR to simulate spreading capacity of nodes. In the SIR model, there are three kinds of individuals: (S) susceptible individuals can be infected; (I) infected individuals have the ability to infect susceptible individuals; and infected individuals are likely to recover with the probability \(\eta\) and become (R) recovered individuals who have immunity to disease and no ability to infect others. Initially, the spreading process starts with only one seed individual infected, and all other individuals are susceptible. At each time step, each infected individual attempts to infect its neighbors with the probability \(\theta\) and then recover with the possibility \(\eta\). The epidemic spreading process terminates when there is no infected individual in the network and the disease cannot spread anymore. In this paper, the recovery possibility \(\eta\) is set to \(1\). We take the average range of recovered population, \(\mu(i)\), over a sufficiently large number of simulations, which are set to be \(1000\), as the indicator to evaluate the influence of node \(i\).  
To evaluate the effectiveness of the ranking methods, the ranking results by the methods are compared with spreading capacity simulated by SIR model. [PERSON]'s \(\tau\)[41] is adopted to judge the correlation between the two ranking lists. The spreading capacity ranking list, \(R_{1}\), simulated by SIR model is denoted as \(X\), and the ranking list, \(R_{2}\), measured by ranking methods is denoted as \(Y\). They have the same number of elements, all of which are \(n\). Let \((x_{1},y_{1})\), \((x_{2},y_{2})\), \((x_{3},y_{3}),\ldots,(x_{n},y_{n})\) be a series of sequence pairs. For any pair of \((x_{i},y_{i})\) and \((x_{j},y_{j})\), if \(x_{i}>x_{j}\) and \(y_{i}>y_{j}\) or if \(x_{i}<x_{j}\) and \(y_{i}<y_{j}\), it is said to be concordant; if \(x_{i}>x_{j}\) and \(y_{i}<y_{j}\) or if \(x_{i}<x_{j}\) and \(y_{i}>y_{j}\), the pair is said to be discordant; and if \(x_{i}=x_{j}\) or \(y_{i}=y_{j}\), the pair is neither concordant nor discordant. The Kendall's \(\tau\) of \(R_{1}\) and \(R_{2}\) is defined as:  
\[\tau(X,Y)=\frac{n_{c}-n_{d}}{\frac{1}{2}n(n-1)}, \tag{6}\]  
where \(n_{c}\) and \(n_{d}\) are the numbers of concordant and discordant pairs, respectively. The higher the \(\tau\) is, the more accurate the method is.