# Mining Important Nodes in Directed Weighted Complex Networks

Authors: Yunyun Yang; Gang Xie; Jun Xie
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

In complex networks, mining important nodes has been a matter of concern by scholars. In recent years, scholars have focused on mining important nodes in undirected unweighted complex networks. But most of the methods are not applicable to directed weighted complex networks. Therefore, this paper proposes a Two-Way-PageRank method based on PageRank for further discussion of mining important nodes in directed weighted complex networks. We have mainly considered the frequency of contact between nodes and the length of time of contact between nodes. We have considered the source of the nodes (in-degree) and the whereabouts of the nodes (out-degree) simultaneously. We have given node important performance indicators. Through numerical examples, we analyze the impact of variation of some parameters on node important performance indicators. Finally, the paper has verified the accuracy and validity of the method through empirical network data.


---

## Body

## 1. Introduction

Complex networks are composed of nodes and edges between nodes [1]. But the importance of each node is different in most cases; that is, different nodes have different weights. In the actual network, identifying some important nodes is crucial for understanding and controlling the whole networks [2–5].Currently, most of the algorithms for mining important nodes focused on undirected unweighted complex networks. For example, degree centrality [6] represents that the more the number of neighboring nodes is, the more important the nodes are. Information index [7] depends on the amount of information through its propagation path. Kitsak et al. [8] proposed k-shell decomposition. In addition, there are many other concepts such as closeness centrality [9], subgraph centrality [10], eigenvector centrality [11], and cumulative nomination [12] which were proposed to evaluate the importance of the nodes in the networks. In those regards, Ren and Lv [13], Wang and Zhang [14], and He et al. [15] have done excellent summaries. Further, Sun and Luo [16] and Liu et al. [17] also summarized the history of the methods of mining important nodes in complex networks and summarized the research results. Most of the discussions focused on undirected unweighted complex networks. However, undirected unweighted complex networks only reflect the connections between the nodes and the topology of complex networks. They cannot describe the directions and intensities of interaction between nodes, since when the networks are abstracted into simple undirected unweighted networks they would lose a lot of existing information which is helpful to analyze accuracy. So, some scholars [18–21] have begun to research on it. Among them, Hu [22] proposed an evaluation method for the importance of a node in directed weighted complex networks based on PageRank-DWNodeRank evaluation method. Chen [23] improved DWNodeRank algorithm and proposed B-DWNodeRank algorithm. The literature [24] analyzed the structural characteristics of weighted complex networks considering influence of the weight of an edge on nodes. Since there are many factors to identify the influential nodes, this issue can be seen as a multiattribute decision making model (MADM) [25, 26]. Many MADM methods, such as fuzzy sets [27] and evidence theory [28, 29], are widely used to ranking the nodes in complex networks [30]. The author gave a new definition on important degree of weighted nodes.These literatures did not consider the out-degree of a node. In addition, PageRank [31] developed by Google founders Brin and Page at Stanford University considers that the most important pages on the Internet are the pages with the most links leading to them. In other words, the importance of a web page focuses on its inbound (in-degree), rather than its link out (out-degree). Indeed, the importance of a node depends on its in-degree and its out-degree. For example, the importance of a school is determined by its appeal to students (its in-degree) and students employment (its out-degree). The importance of a person depends on how many people he/she can attract and what he/she is concerned about. In addition, another major feature of this paper is that we have mainly considered the frequency of contact between nodes and the length of time of contact between nodes as the weight of an edge.This paper proposes the Two-Way-PageRank method based on PageRank and analyzes the importance of two important factors that affect the importance of the nodes and gives the definition and expression of the importance of the nodes. Secondly, we give the expression of the importance of nodes. Subsequently, the effects of some parameters to the results are analyzed through numerical simulation. Finally, the conclusions are given.


## 2. Preliminaries

A directed weighted network(DWN) is a tuple DWN=(V,E,W). V={v1,v2,…,vn} is a finite set, and the elements of V are called nodes; that is, vi represents node i. And E={eij}⊆V×V is a set of ordered tuples in V. The elements of E are called nodes edges with E=m (· is the cardinality of a set). The indices i, j run from 1 to n, where n is the size of the network. In a directed network, the edges are formed by ordered pairs of nodes, so vi,vj∈E represents an edge from vi to vj. W={wij} is a set of edge-weights. wij is the value of edge-weight. DWN is defined as a weighted network if wij could be any real number greater than 0. In this paper, we consider a directed weighted network, and wij is defined as follows.BecauseDWN is a directed network, each vi has a weighted-out-degree for Kout(vi) and a weighted-in-degree for Kin(vi). Kout(vi) is the sum of the weighted of edges which point out from vi. Similarly, Kin(vi) is the sum of the weighted of edges which point to vi. The weighted-in-degree and weighted-out-degree of nodes are thus related by the following expressions: (1a)Koutvi=∑vj∈Voutviwij,i,j=1,2,…,n,(1b)Kinvi=∑vj∈Vinviwji,i,j=1,2,…,n,where Vout(vi) is the set of nodes which point out from vi. Analogously, Vin(vi) is the set of nodes which point to vi.Generally speaking, the strength of a relationship depends primarily on two factors: the frequency of contact and the length of contact (intimacy). In various practical networks,wij represents a different meaning. In the paper, it represents the strength of a relationship between vi and vj. If vi and vj represent persons, wij means the closeness between them. The larger the frequency of contact and the length of time of contact (intimacy) are, the closer the relationship between them is. And these two factors are calculated based on [32] as follows.(a) Frequency Factor. It depends on the frequency of vi pointing to vj, that is, the number of times that vi takes the initiative to meet with vj. (2)FFji=fiFj-fi,i,j=1,2,…,n.Here, FFj(i) is frequency factors of vi pointing to vj, and f(i) is the number of times that vi takes the initiative to meet with vj. F(j) is the number of times that all of the nodes take the initiative to meet with vj.(b) Length of Contact (Intimacy). That is the length of time contact. It depends on the length of time that vi takes the initiative to contact with vj.(3)FIji=tiTj-ti,i,j=1,2,…,n,where FIj(i) is the length of contact of vi pointing to vj. t(i) is the length of contact time that vi takes the initiative to meet with vj. T(j) is the length of contact time that all of nodes take the initiative to meet with vj. Then (4)wij=αFFji+βFIji,i,j=1,2,…,nwith α, β variable parameters, and 0<α, β<1, α+β=1.We should note that, generally speaking,wij≠wji.


## 3. The Two-Way-PageRank for Mining Important Nodes in Directed Weighted Complex Networks

Indeed, the importance of a node depends on its in-degree (its links source) and its out-degrees (its links whereabouts). Hence, here we consider the importance of a node from both its weighted-in-degree and its weighted-out-degrees simultaneously.


### 3.1. The Definition of the Importance ofvi in Directed Weighted Complex Networks

LetI(v) be the importance of vi in directed weighted complex networks. We assume that the nodes which point to vi are u1,u2,…,uk (including vi), and then the sum of the weighted-in-degrees of vi is as follows:(5)winvi=∑j=1kwujvi.Then vi has got an importance of value from the importance of vi: (6)wvviwinviIvi.Likewise, we assume that the nodes to whichvi points are s1,s2,…,sm (including node v), and then the sum of the weighted-out-degrees of vi is defined by(7)woutvi=∑j=1mwvtsj. Then node v has got an importance of value from the importance of vt: (8)wvtvwoutvtIvt. Then (9a)Ioutv=1-γn+γ∑i=1nwvviwinviIvi,(9b)Iinv=1-δn+δ∑t=1nwvtvwoutvtIvt,(10)Iv=Ioutv+Iinvwith I(vi) and I(vt) own importance of vi, vt. Moreover, γ,δ(0<γ,δ<1) are random jump factors and γ+δ=1. vi in (9a) is the ending node of the edge that starts from node v. As well, vt in (9b) is the node which points into node v. wvvi is weight value of edge evvi and wvtv is weight value of edge evtv.


### 3.2. The Algorithm of the Two-Way-PageRank

LetM be the adjacency matrix of the directed weighted complex networks DWN, and M=(Mij)n×n whose elements are the weight on the edge connecting vi to vj, and 0 otherwise. Here we use the convention Mii=0. Then(11)Mij=wij,vi,vj∈E0,vi,vj∉Ei,j=1,2,…,n.Here we normalize processing for M firstly; in other words, each element of the matrix is divided by the sum of the elements in its row. Thus we get the probability transition matrix P=(Pij)n×n, and it can be written as(12)Pij=wij∑j=1nwij,∑j=1nwij≠01n,∑j=1nwij=0i,j=1,2,…,nwith Pij the transfer probability from vi to vj. Obviously, each element of the matrix P is nonnegative. The sum of elements of each row is 1, and that is ∑j=1nPij=1. So it is a random matrix. Let the probability transition matrix P make transpose and get the probability transition matrix PT. The reason for transposing to the matrix P is that we consider weighted-in-degrees of the node.In addition, we normalize processing forM; namely, each element of the matrix is divided by the sum of the elements in its column. Thus we then obtain the probability transition matrix Q=(Qij)n×n.(13)Qij=wij∑i=1nwij,∑i=1nwij≠01n,∑i=1nwij=0i,j=1,2,…,n,where Qij is the transfer probability from vi to vj. It is not difficult to find each element of the matrix Q is nonnegative. The sum of elements of each column is 1, and ∑i=1nQij=1. Likewise, it is a random matrix. Similarly, the reason for doing this to the matrix Q is that we consider weighted-out-degrees of the node. Then according to (9a) and (9b), the equations for the matrix H1 and the matrix H2 can be explicitly solved, obtaining (14a)H1=1-γn×In×1×In×1T+γ×Q,(14b)H2=1-δn×In×1×In×1T+δ×PTin which (In×1×In×1T)n×n is the matrix whose elements are 1.It is not difficult to find that matrixH1 and matrix H2 are irreducible random matrixes, and they have an eigenvalue for 1. The eigenvectors of eigenvalue 1 are the stationary distributions of the matrix H1 and the matrix H2.We can use the power iteration method to compute the stationary distributions of the matrixH1 and the matrix H2. The iterative formulas are as follows: (15)r1=H1x,r2=H2y.Set the initial values of the importance of weighted-out-degree and weighted-in-degree forxi, yi, respectively. So xT=(x1,x2,…,xn), yT=(y1,y2,…,yn). Here, for simplicity, let the initial vector be the ratio of the weighted-out-degree (out-degree) of vi(i=1,2,…,n) and the sum of the weighted-in-degrees (out-degree) of all nodes in the network by the following expressions. (16a)xj=∑i=1nwij∑j=1n∑i=1nwij,j=1,2,…,n,(16b)yi=∑j=1nwij∑j=1n∑i=1nwij,i=1,2,…,n.Given a precision errorε>0. The iteration would stop when r1n+1-r1n<ε, r2n+1-r2n<ε. At this time we get approximations r1 and r2 with r1=r1n+1 and r2=r2n+1. Finally, calculate the formula R=r1+r2. Further, we rank the elements of R from big to small. It is the order of the importance of nodes.It is worth noticing, however, that this indicatesε≪1.The algorithm steps of the importance of mining important nodes in directed weighted complex networks are described in the following.Step 1.
Give the adjacency matrixM of DWN, M=(Mij)n×n.Step 2.
Normalize processing for the adjacency matrixM, and get the probability transition matrices P and Q.Step 3.
Let the probability transition matrixP make transpose and get the probability transition matrix PT.Step 4.
Calculate matricesH1 and H2 of the directed weighted complex networks according to (9a) and (9b).Step 5.
Solve the stationary distributions of the matrixH1 and the matrix H2 using the power iteration method. And that is to calculate r1=H1x and r2=H2y.Step 6.
CountR=r1+r2 and rank the elements of R from big to small. It is the order of the importance of nodes.


## 3.1. The Definition of the Importance ofvi in Directed Weighted Complex Networks

LetI(v) be the importance of vi in directed weighted complex networks. We assume that the nodes which point to vi are u1,u2,…,uk (including vi), and then the sum of the weighted-in-degrees of vi is as follows:(5)winvi=∑j=1kwujvi.Then vi has got an importance of value from the importance of vi: (6)wvviwinviIvi.Likewise, we assume that the nodes to whichvi points are s1,s2,…,sm (including node v), and then the sum of the weighted-out-degrees of vi is defined by(7)woutvi=∑j=1mwvtsj. Then node v has got an importance of value from the importance of vt: (8)wvtvwoutvtIvt. Then (9a)Ioutv=1-γn+γ∑i=1nwvviwinviIvi,(9b)Iinv=1-δn+δ∑t=1nwvtvwoutvtIvt,(10)Iv=Ioutv+Iinvwith I(vi) and I(vt) own importance of vi, vt. Moreover, γ,δ(0<γ,δ<1) are random jump factors and γ+δ=1. vi in (9a) is the ending node of the edge that starts from node v. As well, vt in (9b) is the node which points into node v. wvvi is weight value of edge evvi and wvtv is weight value of edge evtv.


## 3.2. The Algorithm of the Two-Way-PageRank

LetM be the adjacency matrix of the directed weighted complex networks DWN, and M=(Mij)n×n whose elements are the weight on the edge connecting vi to vj, and 0 otherwise. Here we use the convention Mii=0. Then(11)Mij=wij,vi,vj∈E0,vi,vj∉Ei,j=1,2,…,n.Here we normalize processing for M firstly; in other words, each element of the matrix is divided by the sum of the elements in its row. Thus we get the probability transition matrix P=(Pij)n×n, and it can be written as(12)Pij=wij∑j=1nwij,∑j=1nwij≠01n,∑j=1nwij=0i,j=1,2,…,nwith Pij the transfer probability from vi to vj. Obviously, each element of the matrix P is nonnegative. The sum of elements of each row is 1, and that is ∑j=1nPij=1. So it is a random matrix. Let the probability transition matrix P make transpose and get the probability transition matrix PT. The reason for transposing to the matrix P is that we consider weighted-in-degrees of the node.In addition, we normalize processing forM; namely, each element of the matrix is divided by the sum of the elements in its column. Thus we then obtain the probability transition matrix Q=(Qij)n×n.(13)Qij=wij∑i=1nwij,∑i=1nwij≠01n,∑i=1nwij=0i,j=1,2,…,n,where Qij is the transfer probability from vi to vj. It is not difficult to find each element of the matrix Q is nonnegative. The sum of elements of each column is 1, and ∑i=1nQij=1. Likewise, it is a random matrix. Similarly, the reason for doing this to the matrix Q is that we consider weighted-out-degrees of the node. Then according to (9a) and (9b), the equations for the matrix H1 and the matrix H2 can be explicitly solved, obtaining (14a)H1=1-γn×In×1×In×1T+γ×Q,(14b)H2=1-δn×In×1×In×1T+δ×PTin which (In×1×In×1T)n×n is the matrix whose elements are 1.It is not difficult to find that matrixH1 and matrix H2 are irreducible random matrixes, and they have an eigenvalue for 1. The eigenvectors of eigenvalue 1 are the stationary distributions of the matrix H1 and the matrix H2.We can use the power iteration method to compute the stationary distributions of the matrixH1 and the matrix H2. The iterative formulas are as follows: (15)r1=H1x,r2=H2y.Set the initial values of the importance of weighted-out-degree and weighted-in-degree forxi, yi, respectively. So xT=(x1,x2,…,xn), yT=(y1,y2,…,yn). Here, for simplicity, let the initial vector be the ratio of the weighted-out-degree (out-degree) of vi(i=1,2,…,n) and the sum of the weighted-in-degrees (out-degree) of all nodes in the network by the following expressions. (16a)xj=∑i=1nwij∑j=1n∑i=1nwij,j=1,2,…,n,(16b)yi=∑j=1nwij∑j=1n∑i=1nwij,i=1,2,…,n.Given a precision errorε>0. The iteration would stop when r1n+1-r1n<ε, r2n+1-r2n<ε. At this time we get approximations r1 and r2 with r1=r1n+1 and r2=r2n+1. Finally, calculate the formula R=r1+r2. Further, we rank the elements of R from big to small. It is the order of the importance of nodes.It is worth noticing, however, that this indicatesε≪1.The algorithm steps of the importance of mining important nodes in directed weighted complex networks are described in the following.Step 1.
Give the adjacency matrixM of DWN, M=(Mij)n×n.Step 2.
Normalize processing for the adjacency matrixM, and get the probability transition matrices P and Q.Step 3.
Let the probability transition matrixP make transpose and get the probability transition matrix PT.Step 4.
Calculate matricesH1 and H2 of the directed weighted complex networks according to (9a) and (9b).Step 5.
Solve the stationary distributions of the matrixH1 and the matrix H2 using the power iteration method. And that is to calculate r1=H1x and r2=H2y.Step 6.
CountR=r1+r2 and rank the elements of R from big to small. It is the order of the importance of nodes.


## 4. Experiment Simulation

In the section, we show the application of the method on a directed weighted network (see Figure1). Its adjacency matrix can be expressed as M.Figure 1
An example directed weighted network consisted of 13 nodes and 24 edges. The figure shows the connection relationships of the directed weighted network.According to (16a) and (16b), we get xT and yT as shown below xT = (0.0625,0.0469,0.1719,0.0313,0.0781, 0.0938,0.1094,0.0938,0.0156,0.0469,0.1094,0,0.1406), yT = (0.0156,0.0781,0,0.0625,0.1719, 0.1563,0.0469,0.1250,0.1250,0.0469,0.0156,0.1563,0). (17)M=0100000000000003020000000000000000000000220000000000005202000000240100005000000000300000000000004100300000000041003000000002010000000000000000100000000004060000000000000.Further, r1, r2, and R are given when γ=0.2, γ=0.45, and γ=0.85, respectively, as shown in Table 1. The ranks of the importance nodes are defined by Sr1, Sr2, and SR, respectively, as shown in Table 2.Table 1
The values of the importance of nodes.
Nodes
γ=0.2
γ=0.45
γ
=
0.85
r
1
r
2
R
r
1
r
2
R
r
1
r
2
R
1
0.0676
0.0559
0.1236
0.0552
0.0606
0.1158
0.0293
0.0719
0.1012
2
0.0736
0.0961
0.1697
0.0696
0.0928
0.1624
0.0562
0.0834
0.1396
3
0.0627
0.1505
0.2133
0.0447
0.1222
0.1669
0.0134
0.087
0.1004
4
0.0748
0.0501
0.1249
0.0693
0.0554
0.1247
0.0473
0.0697
0.117
5
0.0924
0.1289
0.2213
0.1073
0.1117
0.2191
0.1169
0.0846
0.2015
6
0.0931
0.0767
0.1698
0.1187
0.0743
0.193
0.1965
0.0753
0.2717
7
0.0738
0.0834
0.1572
0.0737
0.0855
0.1592
0.073
0.0813
0.1543
8
0.0938
0.0666
0.1604
0.1261
0.0685
0.1946
0.2218
0.0744
0.2962
9
0.0798
0.045
0.1249
0.0822
0.055
0.1372
0.0856
0.071
0.1566
10
0.0829
0.0513
0.1343
0.0912
0.0584
0.1496
0.1039
0.0716
0.1754
11
0.0641
0.0549
0.1191
0.047
0.0653
0.1123
0.0146
0.0754
0.0901
12
0.0784
0.0314
0.1098
0.0702
0.0443
0.1145
0.0281
0.0674
0.0955
13
0.0627
0.1091
0.1718
0.0447
0.106
0.1507
0.0134
0.0871
0.1005Table 2
The ranks of the importance of nodes.
Rank
γ
=
0
.
2
γ
=
0.45
γ=0.85
S
r
1
S
r
2
S
R
S
r
1
S
r
2
S
R
S
r
1
S
r
2
S
R
1
8
3
5
8
3
5
8
13
8
2
6
5
3
6
5
8
6
3
6
3
5
13
13
5
13
6
5
5
5
4
10
2
6
10
2
3
10
2
10
5
9
7
2
9
7
2
9
7
9
6
12
6
8
7
6
7
7
11
7
7
4
8
7
12
8
13
2
6
2
8
7
1
10
2
11
10
4
8
4
9
2
11
9
4
1
9
1
1
1
10
1
10
4
1
10
4
12
10
13
11
11
4
1
11
4
1
11
9
3
12
13
9
11
3
9
12
13
4
12
13
3
12
12
13
12
11
3
12
11In an actual network, according to the actual situation, at the same time we consider the weighted-out-degree and the weighted-in-degree of nodes for mining important nodes accurately relatively. Figures2–4 provide some comparisons between the actual value of Sr1, the rank of Sr1, and the rank of SR for several networks when γ takes different values. In Figure 2γ=0.2, the rank of SR basically tallies with the rank of Sr2. This is because we mainly consider the impact of out-degree of a node on the importance of the node. For realizations of random networks, the out-degree provides almost complete information. In Figure 3γ=0.45, the rank of SR is associated with both Sr1 and Sr2 at the same time. This is because we give them almost the same weight. In Figure 4γ=0.85, the rank of SR basically tallies with the rank of Sr1. This is because we mainly consider the impact of in-degree of a node on the importance of the node. For realizations of random networks, the in-degree provides almost complete information. At this time, the numerical calculation tallies with the experiment result using the PageRank.Figure 2
The values of the importance index of nodes whenγ=0.2.Figure 3
The values of the importance index of nodes whenγ=0.45.Figure 4
The values of the importance index of nodes whenγ=0.85.The results ofSR relate to the in-degree and out-degree of a node, so when only considering in-degree or out-degree of a node it is clearly not enough. When considering simultaneously the in-degree and out-degree of the nodes, we can better find the important nodes. Through the example, we can mine the important nodes preferably using the method of the Two-Way-PageRank.


## 5. Conclusions and Discussion

Recently, research on complex networks has shown that some real networks exhibit the property of important nodes. Some nodes play an important role in the actual network and control the entire network. Some different physical quantities are considered in the definitions of important nodes of complex networks. However, the existing studies on the importance nodes mainly have focused on undirected unweighted complex networks. The previous analytical study does not accurately reflect the actual information on the networks.In this paper, we therefore addressed the problem of mining important nodes in directed weighted complex networks by constructing a novel Two-Way-PageRank analysis method. We have presented a quantifiable metrics and shown how it can be used to analyze the relative importance of nodes in a network with respect to the contributions nodes which make the overall network connectivity. Numerical examples of real directed weighted complex networks show that when only considering the in-degree or out-degree of a node, the importance of the node cannot well be characterized. The Two-Way-PageRank analysis method proposed can well reveal the importance of the node of directed weighted complex networks such as the infectious disease networks and social networks. To sum up, the proposed method is capable of revealing the importance of the node of directed weighted complex networks. These results not only deepen our understanding of the interplay between network topology and dynamical processes but also have implications in all areas where ranking has a role, from social network to marketing.Our algorithm has been verified in small networks. In future work, we will further build a real data set and verify the algorithm. In addition, what is the relationship between the accuracy of the results and the number of iterations? How can we mine important nodes in directed weighted dynamic complex networks? In future work, we hope to address this problem more systematically.



---

*Source: 9741824-2017-03-30.xml*