# High-Order Degree and Combined Degree in Complex Networks

Authors: Shudong Wang; Xinzeng Wang; Qifang Song; Yuanyuan Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We define several novel centrality metrics: the high-order degree and combined degree of undirected network, the high-order out-degree and in-degree and combined out out-degree and in-degree of directed network. Those are the measurement of node importance with respect to the number of the node neighbors. We also explore those centrality metrics in the context of several best-known networks. We prove that both the degree centrality and eigenvector centrality are the special cases of the high-order degree of undirected network, and both the in-degree and PageRank algorithm without damping factor are the special cases of the high-order in-degree of directed network. Finally, we also discuss the significance of high-order out-degree of directed network. Our centrality metrics work better in distinguishing nodes than degree and reduce the computation load compared with either eigenvector centrality or PageRank algorithm.


---

## Body

## 1. Introduction

The theory of network has gone through rapid development since the late 1990s. One of the hottest points is the research on the attributes of network. Node degree has always been considered as one of the most important and fundamental attributes. Many relative researches have defined other attributes of network based on node degree [1, 2], such as degree distribution [3, 4], clustering coefficient [5, 6], the characteristic path length [6], and so on. As early as 1960s, Rapoport [3, 4] emphasized the importance of the degree distribution in all kinds of real networks. Wasserman and Faust [5] introduced fraction of transitive triples in social network in 1994. In order to describe cliquishness of a typical neighborhood, Watts and Strogatz [6] defined clustering coefficient of general complex network in 1998 based on the fraction of transitive triples. Watts and Strogatz [6] also defined the characteristic path length to measure the typical separation between two nodes in the network. In more recent years, numerous researches paid attention to degree distribution [7–10]. Early researches believed that degree distribution followed Poisson Distribution just as the random network theory has described [11, 12]. Recent researches have found out that the degree distribution for a large number of networks, such as the World Wide Web [13], the Internet [14], the metabolic networks [15], genome-wide disruption networks for yeast [16], and the network of interregional direct investment stocks across Europe [17], have a power-law tail. Such networks are called scale-free [18].When a practical problem is transformed into a complex network model, people tend to use node centrality to describe the importance and influence of a node, or people need to sort these nodes [19]. Node degree (or degree centrality) is one of the basic methods of sorting the nodes [20–29]. Other common methods are also based on node degree [1, 2]. As long ago as 1948, Bavelas [30] studied the center of social network. Sabidussi et. al. [31] defined what it means for a network node to approach closeness. Freema [32] used node degree and betweenness to define two kinds of node centrality, and, furthermore, he used node centrality to define graph centrality. Network eigenvector centrality [33, 34] is often used to describe the importance of nodes in social network. In 1998, Brin and Page [35, 36] simplified the eigenvector centrality for undirected network into PageRank algorithm (PR), which is widely used in searching engine Google [36] and many other directed networks [37–42]. By using the degree distribution of neighbor nodes, Ai [43] gave the definition of the neighbor vector centrality. Zeng [44] implemented the Mixed Degree Decomposition (MDD) procedure by using coreness centrality, and he defined the mixed degree of nodes. Bae [45] defined the kernel centrality of a node by using the kernel of the neighbor nodes.The degree centrality used for sorting nodes has the advantages of simple calculation, but the results are not accurate enough. Therefore, it may require verification by other methods [20] or other network attributes [27, 28]. Closeness centrality and betweenness centrality are often given with degree centrality for comparison purpose [27, 28]. The computation of both closeness centrality and betweenness centrality are so complicated that big networks often need fast approximate algorithm [46–48]. Even though the eigenvector centrality on undirected network and the PageRank on directed work can give satisfying results in nodes sorting, those two methods often involve expensive computations, such as iterations [42]. In the following paragraphs, we will define several novel centrality metrics, which are cheaper in computation compared with closeness centrality, betweenness centrality, eigenvector centrality on undirected network, and PageRank on directed network. We will show that node degree, the eigenvector centrality on undirected network and in-degree, and PageRank on directed network are all special cases of (or equivalent to) one of our novel centrality metrics (see Sections 4.1 and 4.2). It should be pointed out that the combined degree defined in our paper is different from the mixed degree in Zeng [44], which is the Mixed Degree Decomposition of coreness centrality (see Section 4.4).


## 2. Methods

Random walk has always been one of the most important methods in the research of complex network [49–53]. Noh et. al. [49] derived the mean first passage time (MFPT) between any two nodes by using random walk of complex network. Tejedor [50] computed the MFPT of a network based on a broad class of random walk. Rosvall et. al. [51] used the probability flow of random walks on a network as a proxy for information flow in the real system. Saramäki et. al. [52] generated scale-free networks based on selecting parent nodes by using random walk. Weng [53] used the newly defined mean first traverse distance (MFTD) to describe anomalous random walks. Now let us think about an ideal random walk of a simple network (could be an undirected network or a directed network): choose a node of the network, which we call the origin node, put a ball at the origin node, and the ball obeys the following rules to split repeatedly and to walk randomly.(i)
Splitting: the ball splits up intodG(v) (or dG+(v)) balls at the node v, where dG(v) is the degree of v in undirected network and dG+(v) is the out-degree of v in directed network.(ii)
Random walk: after every split, the balls move to the adjacent nodes along thedG(v) edges; in directed network they can only move along dG+(v) outgoing edges.(iii)
Disappearance: balls that can no longer walk would disappear, for example, at the isolated nodes or dead nodes of directed network.The number of repeats of the random walk would be different depending on the selection of network and/or the selection of origin node, such as in Figure1.Figure 1
Diagram of random walk. Choose the origin node 1: (a) the process of splitting and random walking could be repeated an infinite number of times, because origin node 1 is connected to node 2; (b) the ball can walk randomly an infinite number of times without split since the origin node is one of the directed loop; (c) the ball split and walk randomly only once; (d) the ball can only walk twice without splitting; (e) the ball can walk an infinite number of times without split.
(a) (b) (c) (d) (e)In the undirected network, the number of balls aftersth split is defined as the s-order degree of the origin node v, denoted by dGs(v). Clearly, if s=1, dG1(v) is the degree dG(v) of v (see Theorem 2, Section 4.1). In the directed network, the number of balls after sth split is called the s-order out-degree of the origin node v, denoted by dG+s(v). Also, when s=1, dG+1(v) is the out-degree dG+(v) of v (see Theorem 3, Section 4.2).Consider a more complicated random walk of a directed network: select a network nodev, which we call the sink node. Then we put balls at every node in the network (including the sink node v), and all of the balls follow the above rules to split repeatedly and to walk randomly, the number of balls at the sink node after the sth random walk is defined as the s-order in-degree of the sink node v, denoted by dG-s(v). Clearly, if s=1, dG-1(v) is the in-degree dG-(v) of v (see Theorem 3, Section 4.2).


### 2.1. 2-Order Degree

As for the undirected network, according to the above definition, 2-order degreedG2(v) of the node v is the number of two-edge paths connected to v. The two-edge paths may overlap. For example, Figure 1(e), both nodes have an overlap two-edge path, then the 2-order degree of both nodes is 1. Note that the 2-order degree is not necessarily equal to the number of neighbors of a node’s neighbors, since there may be more than one two-edge path between any two nodes (here the two nodes may be the same one). The computation of node 2-order degree dG2(v) is relatively simple. Suppose matrix A=(aij) is the adjacency matrix of the undirected network G, we call A2=A2 the 2-order adjacency matrix, and then the sum of elements in each row (or each column) of A2 is the 2-order degree of the corresponding node. Use {A2}i to denote the sum of the i-th row of matrix A2, then the 2-order degree of the i-th node vi of the undirected network G is dG2(vi)={A2}i.A directed graph has both a 2-order in-degree and a 2-order out-degree for each node, which are the numbers of incoming and outgoing two-edge paths, respectively. Still denote the adjacency matrix asA=(aij), and denote {A2}i and {A2}i as the sum of the i-th row and i-th column of the 2-order adjacency matrix A2=A2, respectively. Then the 2-order out-degree and the 2-order in-degree of the i-th node vi in this directed network are dG+2(vi)={A2}i and dG-2(vi)={A2}i, respectively.IfG has vertices v1,v2,⋯,vn, the sequence (d(v1),d(v2),⋯,d(vn))T is called thedegree sequence  of G [54]. As we all know, the mean value and the distribution of degree sequence guide the definition of mean degree and degree distribution. We can obtain the mean 2-order degree and the 2-order degree distribution of the network by using the definition of 2-order degree.In Figure1, (a) the 2-order degree of the three nodes all is 2; (b) the 2-order out-degree and 2-order in-degree of the three nodes all are 1; (c) the 2-order out-degree and 2-order in-degree of the three nodes all are 0; (d) the 2-order out-degree of the three nodes is 1, 0, 0, and the 2-order in-degree of the three nodes is 0, 0, 1; (e) the 2-order degree of the two nodes is 1.Figure2 is a relatively complicated undirected network and a relatively complicated directed network. Table 1 shows the 2-order (in-/out-)degree of the all nodes and both mean 2-order degrees for the two networks in Figure 2. As we can see from Table 1, node 5 has the highest 2-order degree in Figure 2(a), which is the same as the common sense that node 5 is the most important node in Figure 2(a). However this conclusion cannot be obtained simply by calculating node degree. Of course we can obtain such conclusion by calculating node betweenness centrality or eigenvector centrality, and so forth. Another thing we can tell from Table 1 is that nodes having the highest 2-order out-degree are 1, 2, and 5, and the node having the highest 2-order in-degree is 10. Therefore, we could consider that nodes 1, 2, and 5 are the source nodes of (b), and the node 10 could be thought as the collection node of (b). In general, we need to run the PageRank algorithm of the entire network in order to get such conclusions.Table 1
The 2-order out-/in-degree of Figure2.
Name of each node 1 2 3 4 5 6 7 8 9 10 Mean Figure2(a) Degree 1 1 1 4 2 5 1 1 1 1 1.9 (Undirected network) 2-order degree 4 4 4 5 9 6 5 5 5 5 5.2  Out-degree 2 2 1 1 2 2 1 1 1 1 1.4 Figure2(b) In-degree 0 1 2 2 1 2 1 2 1 2 1.8 (Directed network) 2-order out-degree 3 3 1 2 3 2 1 1 1 1 1.4 2-order in-degree 0 0 2 1 1 3 2 3 2 4 1.8Figure 2
The degree and 2-order degree of a network.
(a) (b)


### 2.2.s-Order Degree and Its Computation

Same as 2-order degree, suppose matrixA is an adjacency matrix of a network G, we denote As=As(s∈N∗) as the s-order adjacency matrix of G. The matrix As was used to calculate the number of walk with length s between nodes [54–56]. Denote {As}i and {As}i as the sum of the i-th row and i-th column respectively in matrix As; then the s-order degree of node vi in undirected network G is {As}i and {As}i={As}i (if G is a directed network, then the s-order out-degree is {As}i, and the s-order in-degree is {As}i). It is easy to define mean s-order (out-/in-)degree and the s-order (out-/in-)degree distribution, too.The computation ofs-order degree can make use of adjacency matrix, but this involves the exponentiation computation of matrix. The order of matrix A equals the number of nodes in the network, and there could be thousands and tens of thousands of nodes in a network. Therefore even though the computation of s-order adjacency matrix only involves the exponentiation computation of matrix and additions of integers, it would be a high requirement on the computer’s CPU and memory. A simple method to tackle this problem is to firstly compute the lower order degree sequence of the network and then compute the higher-order degree sequence. We can prove Theorem 1 by the method of mathematical induction.Theorem 1.
Fors-order degree sequence, the following conclusions are true: (i)
Ifds is a s-order degree sequence of an undirected network G, A is the adjacency matrix, then the (s+1)-order degree sequence of G is A∗ds; particularly, if d1 is the degree sequence of an undirected network G, then the (s+1)-order degree sequence of G is As∗d1.(ii)
Similarly, ifd+s and d-s are the s-order out-degree sequence and s-order in-degree sequence of directed network respectively, A is the adjacency matrix, then the (s+1)-order out-degree sequence and the (s+1)-order in-degree sequence are A∗d+s and AT∗d-s respectively; particularly, if d+1 and d-1 are the out-degree sequence and in-degree sequence of the directed network respectively, then the (s+1)-order out-degree sequence and the (s+1)-order in-degree sequence are As∗d+1 and (AT)s∗d-1, respectively.


### 2.3. Combined Degree

Based on thes-order degree defined as above, the following gives the definition of combined degree of a node vi of an undirected network:(1)dGComvi=α1·dG1vi+α2·dG2vi+⋯+αs·dGsvi+⋯,where dGm(vi)(m=1,2,⋯,s,⋯) denotes the various order degrees of node vi, and constants αm(m=1,2,⋯,s,⋯) are all nonnegative real numbers, with a sum of 1. If α1=1 and αm=0(m=2,3,⋯,s,⋯), the combined degree is the node degree in common sense, if α2=1 and αm=0(m=1,3,⋯,s,⋯), the combined degree is the 2-order degree, and so forth. For the values of parameters, we usually consider the case α1≥α2≥α3≥⋯, where α1≥α2 indicates that a single neighbor’s influence to vi is no less than a single neighbor’s influence. Notice that the value of constant αm(m=1,2,⋯,s,⋯) may not be integers; therefore the combined degree dGCom(vi) usually not be integer. Since the combined degree is the combination of regular degree and various high-order degree, we need not discuss the mean combined degree and combined degree distribution. Same as above, we can define combined in-degree and combined out-degree of a directed network. According to Theorem 1, we could give the following formula of combined degree sequence. Here we omit the formulas of combined in-degree sequence and combined out-degree sequence of directed networks. (2)dGCom=α1·En+α2·A+⋯+αs·As-1+⋯d1,where En is the identity matrix of order n.


## 2.1. 2-Order Degree

As for the undirected network, according to the above definition, 2-order degreedG2(v) of the node v is the number of two-edge paths connected to v. The two-edge paths may overlap. For example, Figure 1(e), both nodes have an overlap two-edge path, then the 2-order degree of both nodes is 1. Note that the 2-order degree is not necessarily equal to the number of neighbors of a node’s neighbors, since there may be more than one two-edge path between any two nodes (here the two nodes may be the same one). The computation of node 2-order degree dG2(v) is relatively simple. Suppose matrix A=(aij) is the adjacency matrix of the undirected network G, we call A2=A2 the 2-order adjacency matrix, and then the sum of elements in each row (or each column) of A2 is the 2-order degree of the corresponding node. Use {A2}i to denote the sum of the i-th row of matrix A2, then the 2-order degree of the i-th node vi of the undirected network G is dG2(vi)={A2}i.A directed graph has both a 2-order in-degree and a 2-order out-degree for each node, which are the numbers of incoming and outgoing two-edge paths, respectively. Still denote the adjacency matrix asA=(aij), and denote {A2}i and {A2}i as the sum of the i-th row and i-th column of the 2-order adjacency matrix A2=A2, respectively. Then the 2-order out-degree and the 2-order in-degree of the i-th node vi in this directed network are dG+2(vi)={A2}i and dG-2(vi)={A2}i, respectively.IfG has vertices v1,v2,⋯,vn, the sequence (d(v1),d(v2),⋯,d(vn))T is called thedegree sequence  of G [54]. As we all know, the mean value and the distribution of degree sequence guide the definition of mean degree and degree distribution. We can obtain the mean 2-order degree and the 2-order degree distribution of the network by using the definition of 2-order degree.In Figure1, (a) the 2-order degree of the three nodes all is 2; (b) the 2-order out-degree and 2-order in-degree of the three nodes all are 1; (c) the 2-order out-degree and 2-order in-degree of the three nodes all are 0; (d) the 2-order out-degree of the three nodes is 1, 0, 0, and the 2-order in-degree of the three nodes is 0, 0, 1; (e) the 2-order degree of the two nodes is 1.Figure2 is a relatively complicated undirected network and a relatively complicated directed network. Table 1 shows the 2-order (in-/out-)degree of the all nodes and both mean 2-order degrees for the two networks in Figure 2. As we can see from Table 1, node 5 has the highest 2-order degree in Figure 2(a), which is the same as the common sense that node 5 is the most important node in Figure 2(a). However this conclusion cannot be obtained simply by calculating node degree. Of course we can obtain such conclusion by calculating node betweenness centrality or eigenvector centrality, and so forth. Another thing we can tell from Table 1 is that nodes having the highest 2-order out-degree are 1, 2, and 5, and the node having the highest 2-order in-degree is 10. Therefore, we could consider that nodes 1, 2, and 5 are the source nodes of (b), and the node 10 could be thought as the collection node of (b). In general, we need to run the PageRank algorithm of the entire network in order to get such conclusions.Table 1
The 2-order out-/in-degree of Figure2.
Name of each node 1 2 3 4 5 6 7 8 9 10 Mean Figure2(a) Degree 1 1 1 4 2 5 1 1 1 1 1.9 (Undirected network) 2-order degree 4 4 4 5 9 6 5 5 5 5 5.2  Out-degree 2 2 1 1 2 2 1 1 1 1 1.4 Figure2(b) In-degree 0 1 2 2 1 2 1 2 1 2 1.8 (Directed network) 2-order out-degree 3 3 1 2 3 2 1 1 1 1 1.4 2-order in-degree 0 0 2 1 1 3 2 3 2 4 1.8Figure 2
The degree and 2-order degree of a network.
(a) (b)


## 2.2.s-Order Degree and Its Computation

Same as 2-order degree, suppose matrixA is an adjacency matrix of a network G, we denote As=As(s∈N∗) as the s-order adjacency matrix of G. The matrix As was used to calculate the number of walk with length s between nodes [54–56]. Denote {As}i and {As}i as the sum of the i-th row and i-th column respectively in matrix As; then the s-order degree of node vi in undirected network G is {As}i and {As}i={As}i (if G is a directed network, then the s-order out-degree is {As}i, and the s-order in-degree is {As}i). It is easy to define mean s-order (out-/in-)degree and the s-order (out-/in-)degree distribution, too.The computation ofs-order degree can make use of adjacency matrix, but this involves the exponentiation computation of matrix. The order of matrix A equals the number of nodes in the network, and there could be thousands and tens of thousands of nodes in a network. Therefore even though the computation of s-order adjacency matrix only involves the exponentiation computation of matrix and additions of integers, it would be a high requirement on the computer’s CPU and memory. A simple method to tackle this problem is to firstly compute the lower order degree sequence of the network and then compute the higher-order degree sequence. We can prove Theorem 1 by the method of mathematical induction.Theorem 1.
Fors-order degree sequence, the following conclusions are true: (i)
Ifds is a s-order degree sequence of an undirected network G, A is the adjacency matrix, then the (s+1)-order degree sequence of G is A∗ds; particularly, if d1 is the degree sequence of an undirected network G, then the (s+1)-order degree sequence of G is As∗d1.(ii)
Similarly, ifd+s and d-s are the s-order out-degree sequence and s-order in-degree sequence of directed network respectively, A is the adjacency matrix, then the (s+1)-order out-degree sequence and the (s+1)-order in-degree sequence are A∗d+s and AT∗d-s respectively; particularly, if d+1 and d-1 are the out-degree sequence and in-degree sequence of the directed network respectively, then the (s+1)-order out-degree sequence and the (s+1)-order in-degree sequence are As∗d+1 and (AT)s∗d-1, respectively.


## 2.3. Combined Degree

Based on thes-order degree defined as above, the following gives the definition of combined degree of a node vi of an undirected network:(1)dGComvi=α1·dG1vi+α2·dG2vi+⋯+αs·dGsvi+⋯,where dGm(vi)(m=1,2,⋯,s,⋯) denotes the various order degrees of node vi, and constants αm(m=1,2,⋯,s,⋯) are all nonnegative real numbers, with a sum of 1. If α1=1 and αm=0(m=2,3,⋯,s,⋯), the combined degree is the node degree in common sense, if α2=1 and αm=0(m=1,3,⋯,s,⋯), the combined degree is the 2-order degree, and so forth. For the values of parameters, we usually consider the case α1≥α2≥α3≥⋯, where α1≥α2 indicates that a single neighbor’s influence to vi is no less than a single neighbor’s influence. Notice that the value of constant αm(m=1,2,⋯,s,⋯) may not be integers; therefore the combined degree dGCom(vi) usually not be integer. Since the combined degree is the combination of regular degree and various high-order degree, we need not discuss the mean combined degree and combined degree distribution. Same as above, we can define combined in-degree and combined out-degree of a directed network. According to Theorem 1, we could give the following formula of combined degree sequence. Here we omit the formulas of combined in-degree sequence and combined out-degree sequence of directed networks. (2)dGCom=α1·En+α2·A+⋯+αs·As-1+⋯d1,where En is the identity matrix of order n.


## 3. Results

In order to compare the behavior of degree and high-order degree and/or combined degree, we apply these attributes to a couple of best-known networks. We believe that the attributes of network with better behavior should be better to discover the differences among different nodes. By the definition of the differences of a given set of data, standard deviation (std) is the most important metric parameter. The greater the standard deviation is, the more diversities the data has, and the better the discrimination is, the better the attributes behavior is. As a complement to std, we define a novel parameter and call it as overflow ratio (ORα), which denotes the ratio of the number of elements outside [α·mean,1/α·mean] to the number of elements in the given set of data, where mean denotes the mean value of the given set of data and 0<α<1. The greater the overflow ratio is, the less the possibility that data cluster around the mean value of the given set is, and the better the discrimination is, the better the attributes behavior is. Therefore, these two parameters both reflect the diversity of a given set of data to some extent. Clearly, if one of the network attributes shows more diversity, it is easier to distinguish or sort the nodes.


### 3.1. Random Network

Random network was put forward for the first time by Paul Erdo¨s and Alfred Rényi in 1960 (which is called ER Random Network) [11]. Here we generate a random network with n nodes, and we investigate the influence of node connection probability p taking different values on degree and high-order degree. Figure 3 shows the simulation results of 1000 times for node degree distribution, 2-order degree distribution, 4-order degree distribution, and combined degree distribution with n=10000 and p=0.05. We can tell from the results that the two high-order degrees and combined degree of random network still preserve the property of degree distribution, which is similar to Poisson Distribution (or Normal Distribution) with mean degree/mean high-order degree as the peak value.Figure 3
Random network: simulation results of 1000 times for node degree (mean) distributions with number of nodesn=10000 and edge augment connection probability p=0.05, taking α1=1/2,α2=1/4,α3=α4=1/8,α5=⋯=0 for combined degree distribution.Table2 gives the discrimination of some attributes with n=10000 and p=0.05. Since the node degree distribution and high-order degree/combined degree distribution are all similar to Poisson Distribution (or Normal Distribution), we take big values for the overflow ratios. We can also tell from Table 2 that high-order degree has better discrimination compared with regular node degree, which is also true when n and p change (see Supplementary Table 1).Table 2
Random Network: the discrimination parameters of 10000 simulations for different stages in Random Network, with number of nodesn=1000 and connection probability p=0.05.
Node Standard overflow ratio degree Deviation α = 0.9 α = 0.91 α = 0.93 α = 0.95 α = 0.98 degree 2.80 ∗ 10 e 1 1.5% 2.73% 9.1% 23.08% 63.01% 2-order degree 1.093 ∗ 10 e 4 1.55% 2.86% 9.1% 23.86% 64.48% 4-order degree 2.747 ∗ 10 e 9 1.57% 2.9% 9.21% 23.96% 64.54% combined degree 3.440 ∗ 10 e 8 1.57% 2.9% 9.21% 23.96% 64.54%


### 3.2. Small World Model

Watts [57] gave the basic attributes of Small World Model in 1999. Watts and Stregatz [6] proposed the construction of small world network by edge redistribution, which is called the WS small world network. Monasson [58] and Newman et al. [59] initiated the construction of small world network through edge augment, which is called the NW small world network. In this subsection we construct a small world network by edge augment, and investigate the behaviors of high-order degrees in small world network. Firstly, we construct a regular network with n nodes, and with each node connected to the nearest d nodes (where n≫d≫ln⁡n≫1). For a given probability p, we stochastic add pnd/2 edges to produce the small world network. We can tell from Figure 4 that the scatter plot of 2-order degree distribution, 3-order degree distribution and 4-order degree distribution are all similar to Poisson Distribution (or Normal Distribution), which is the same as the degree distribution of the small world network.Figure 4
Small world network: simulation results of 1000 times for node degree distributions with number of nodesn=5000 and given probability p=0.05 and with each node connected to the nearest d=20 nodes initially.For small world network, similar to random network, we are more concerned with the discrimination of small world network. Table3 shows the mean discrimination of 1000 simulations for degree, 2-order degree, 4-order degree and 8-order degree, with n=800, initial edge connection number d=30, and connection probability p=0.05. Of all the situations, 4-order degree and 8-order degree show better discrimination results than the others. But sometimes the 2-order degree does not show good results in discrimination than degree, which is probably caused by the smallness of the value of parameter p. In Supplementary Table 2, we increase the value of p, and show the discrimination of degree, 2-order degree, and 4-order degree, with the number of nodes n and initial connection edges d change over 54 cases. Among all of the cases, the standard deviation discrimination gets bigger (better), 4-order degree shows smaller overflow ratio twice than that of node degree, and 2-order degree shows smaller overflow ratio four times than that of node degree, which suggests that 4-order degree and 2-order degree are better than node degree in the aspect of overflow ratio. Moreover, as the order of high-order degree increases, the overflow ratio shows better results in discriminating the nodes.Table 3
Small world network: the discrimination parameters of 1000 simulations for different stages in small world network withn=5000, p=0.05, and d=20.
order Standard overflow ratio Deviation α = 0.85 α = 0.9 α = 0.93 α = 0.95 degree 1.2476 0.05% 0.6102% 7.2873% 7.2954% 2-order degree 41.321 0.15% 1.57% 5.9382% 5.9425% 4-order degree 45674 0.21% 1.8% 9.87% 9.76% 8-order degree 5.268e + 010 0.4% 4% 16.8% 32.875%


### 3.3. Undirected Scale-Free Network

Barabási and Albert [18, 60, 61] proposed scale-free network (which is called BA scale-free network) with node degree distribution following the power-law distribution. In this subsection, we construct an undirected, scale-free network to investigate the behavior of various orders of degree. Firstly, we produce a random network with the number of nodes n, stochastic connection probability p. Then we add one node each time whose degree equals m by the preferential attachment mechanism. Preferential attachment means that the more connected a node is, the more likely it is to receive new links. Nodes with higher degree have stronger ability to grab links added to the network. In our paper, the probability that new node connects to node i is proportional to the degree of i. Repeating this process for t times, we get an undirected scale-free network with n+t nodes and about np/2+mt edges.The high-order degree distribution and combined degree distribution are also power-law distribution; see Figure5. Supplementary Table 3 gives the discrimination results of various orders of degree, with initial number of nodes n, initial node connection probability p, and running times t, and the new node added to the network each time has a degree of m. As a matter of fact, only if 0.3≤α≤0.5, the higher-order degree shows better discrimination results. The reason maybe that the range of node degree sequence is relatively large for scale-free network (compared with random network and small world network), which coincides with our knowledge [18, 60, 61].Figure 5
Undirected scale-free network: the node degree distribution and high-order degree distribution of a scale-free network, withn=100, p=0.05, m=5, t=4900.


### 3.4. Directed Scale-Free Network

In this subsection, we construct a directed scale-free network. Firstly, produce a random network with nodes numbern and connection probability p. Secondly assign the direction of each existing edge at random (with equal probability) to establish a directed network. Thirdly, run this step t times, add a new node at each time, and add m1 in-edges by out-degree priority mechanism and m2 out-edges by in-degree priority mechanism; there we usually choose m2≥m1≥0. Therefore we obtain a directed network with n+t nodes and np/2+(m1+m2)t edges. Figure 6 shows that both the in-degree distribution and the out-degree distribution in the directed network we developed follow power-law distribution; therefore it is a directed scale-free network [56, 57]. But there are variations at the beginning of the graphs for high-order in-degree and high-order out-degree (especially the out-degree), even though the general shapes of these graphs still resemble the power-rule distributions; see Figure 6. We suspect that this may be caused by the fact that we always add in-edges and out-edges at each time when we construct the network, and the numbers of edges maintain constants rather than random numbers. Since the discrimination comparison between high-order degree and node degree in directed scale-free network is similar to that in undireceted scale-free network, we will not demonstrate the results here.Figure 6
Directed scale-free network: node degree distribution and high-order distribution in the directed scale-free network with initial nodesn=100, initial connection probability p=0.1, the direction of an edge is assigned randomly, and m1=2, m2=5 in-edges/out-edges are added to network by the priority mechanism, running times t=2900.


## 3.1. Random Network

Random network was put forward for the first time by Paul Erdo¨s and Alfred Rényi in 1960 (which is called ER Random Network) [11]. Here we generate a random network with n nodes, and we investigate the influence of node connection probability p taking different values on degree and high-order degree. Figure 3 shows the simulation results of 1000 times for node degree distribution, 2-order degree distribution, 4-order degree distribution, and combined degree distribution with n=10000 and p=0.05. We can tell from the results that the two high-order degrees and combined degree of random network still preserve the property of degree distribution, which is similar to Poisson Distribution (or Normal Distribution) with mean degree/mean high-order degree as the peak value.Figure 3
Random network: simulation results of 1000 times for node degree (mean) distributions with number of nodesn=10000 and edge augment connection probability p=0.05, taking α1=1/2,α2=1/4,α3=α4=1/8,α5=⋯=0 for combined degree distribution.Table2 gives the discrimination of some attributes with n=10000 and p=0.05. Since the node degree distribution and high-order degree/combined degree distribution are all similar to Poisson Distribution (or Normal Distribution), we take big values for the overflow ratios. We can also tell from Table 2 that high-order degree has better discrimination compared with regular node degree, which is also true when n and p change (see Supplementary Table 1).Table 2
Random Network: the discrimination parameters of 10000 simulations for different stages in Random Network, with number of nodesn=1000 and connection probability p=0.05.
Node Standard overflow ratio degree Deviation α = 0.9 α = 0.91 α = 0.93 α = 0.95 α = 0.98 degree 2.80 ∗ 10 e 1 1.5% 2.73% 9.1% 23.08% 63.01% 2-order degree 1.093 ∗ 10 e 4 1.55% 2.86% 9.1% 23.86% 64.48% 4-order degree 2.747 ∗ 10 e 9 1.57% 2.9% 9.21% 23.96% 64.54% combined degree 3.440 ∗ 10 e 8 1.57% 2.9% 9.21% 23.96% 64.54%


## 3.2. Small World Model

Watts [57] gave the basic attributes of Small World Model in 1999. Watts and Stregatz [6] proposed the construction of small world network by edge redistribution, which is called the WS small world network. Monasson [58] and Newman et al. [59] initiated the construction of small world network through edge augment, which is called the NW small world network. In this subsection we construct a small world network by edge augment, and investigate the behaviors of high-order degrees in small world network. Firstly, we construct a regular network with n nodes, and with each node connected to the nearest d nodes (where n≫d≫ln⁡n≫1). For a given probability p, we stochastic add pnd/2 edges to produce the small world network. We can tell from Figure 4 that the scatter plot of 2-order degree distribution, 3-order degree distribution and 4-order degree distribution are all similar to Poisson Distribution (or Normal Distribution), which is the same as the degree distribution of the small world network.Figure 4
Small world network: simulation results of 1000 times for node degree distributions with number of nodesn=5000 and given probability p=0.05 and with each node connected to the nearest d=20 nodes initially.For small world network, similar to random network, we are more concerned with the discrimination of small world network. Table3 shows the mean discrimination of 1000 simulations for degree, 2-order degree, 4-order degree and 8-order degree, with n=800, initial edge connection number d=30, and connection probability p=0.05. Of all the situations, 4-order degree and 8-order degree show better discrimination results than the others. But sometimes the 2-order degree does not show good results in discrimination than degree, which is probably caused by the smallness of the value of parameter p. In Supplementary Table 2, we increase the value of p, and show the discrimination of degree, 2-order degree, and 4-order degree, with the number of nodes n and initial connection edges d change over 54 cases. Among all of the cases, the standard deviation discrimination gets bigger (better), 4-order degree shows smaller overflow ratio twice than that of node degree, and 2-order degree shows smaller overflow ratio four times than that of node degree, which suggests that 4-order degree and 2-order degree are better than node degree in the aspect of overflow ratio. Moreover, as the order of high-order degree increases, the overflow ratio shows better results in discriminating the nodes.Table 3
Small world network: the discrimination parameters of 1000 simulations for different stages in small world network withn=5000, p=0.05, and d=20.
order Standard overflow ratio Deviation α = 0.85 α = 0.9 α = 0.93 α = 0.95 degree 1.2476 0.05% 0.6102% 7.2873% 7.2954% 2-order degree 41.321 0.15% 1.57% 5.9382% 5.9425% 4-order degree 45674 0.21% 1.8% 9.87% 9.76% 8-order degree 5.268e + 010 0.4% 4% 16.8% 32.875%


## 3.3. Undirected Scale-Free Network

Barabási and Albert [18, 60, 61] proposed scale-free network (which is called BA scale-free network) with node degree distribution following the power-law distribution. In this subsection, we construct an undirected, scale-free network to investigate the behavior of various orders of degree. Firstly, we produce a random network with the number of nodes n, stochastic connection probability p. Then we add one node each time whose degree equals m by the preferential attachment mechanism. Preferential attachment means that the more connected a node is, the more likely it is to receive new links. Nodes with higher degree have stronger ability to grab links added to the network. In our paper, the probability that new node connects to node i is proportional to the degree of i. Repeating this process for t times, we get an undirected scale-free network with n+t nodes and about np/2+mt edges.The high-order degree distribution and combined degree distribution are also power-law distribution; see Figure5. Supplementary Table 3 gives the discrimination results of various orders of degree, with initial number of nodes n, initial node connection probability p, and running times t, and the new node added to the network each time has a degree of m. As a matter of fact, only if 0.3≤α≤0.5, the higher-order degree shows better discrimination results. The reason maybe that the range of node degree sequence is relatively large for scale-free network (compared with random network and small world network), which coincides with our knowledge [18, 60, 61].Figure 5
Undirected scale-free network: the node degree distribution and high-order degree distribution of a scale-free network, withn=100, p=0.05, m=5, t=4900.


## 3.4. Directed Scale-Free Network

In this subsection, we construct a directed scale-free network. Firstly, produce a random network with nodes numbern and connection probability p. Secondly assign the direction of each existing edge at random (with equal probability) to establish a directed network. Thirdly, run this step t times, add a new node at each time, and add m1 in-edges by out-degree priority mechanism and m2 out-edges by in-degree priority mechanism; there we usually choose m2≥m1≥0. Therefore we obtain a directed network with n+t nodes and np/2+(m1+m2)t edges. Figure 6 shows that both the in-degree distribution and the out-degree distribution in the directed network we developed follow power-law distribution; therefore it is a directed scale-free network [56, 57]. But there are variations at the beginning of the graphs for high-order in-degree and high-order out-degree (especially the out-degree), even though the general shapes of these graphs still resemble the power-rule distributions; see Figure 6. We suspect that this may be caused by the fact that we always add in-edges and out-edges at each time when we construct the network, and the numbers of edges maintain constants rather than random numbers. Since the discrimination comparison between high-order degree and node degree in directed scale-free network is similar to that in undireceted scale-free network, we will not demonstrate the results here.Figure 6
Directed scale-free network: node degree distribution and high-order distribution in the directed scale-free network with initial nodesn=100, initial connection probability p=0.1, the direction of an edge is assigned randomly, and m1=2, m2=5 in-edges/out-edges are added to network by the priority mechanism, running times t=2900.


## 4. Discussion

The high-order degree in a network considers the influence of different path distances on a node. In a social network, consider a node is a person, and an edge is a friendship. Node degree of nodeva indicates the influence of va’s friends on va. The 2-order degree of va indicates the influence of va’s friends’ friends on va. An interesting question is that, if va and vb are friends, there is an undirected edge connecting va and vb, then va will influence vb, which will in return have influence on va itself also. If va has many friends, va will have influence on all of its friends, which in return will affect va many times.We know from Section3 that high-order degrees and combined degree are superior to degree in discriminating nodes. However the computation of degree is simpler than high-order degrees and combined degree. Compared with the eigenvector centrality in undirected network, and PageRank in directed network, the high-order (out-/in-)degree and/or combined (out-/in-)degree we defined in this paper do not need iterations. The computation of our method only involves multiplications of matrices and vectors, which is clearly easier than eigenvector centrality or PageRank.


### 4.1. The High-Order Degree and Eigenvector Centrality/Betweenness in Undirected Network

In the undirected network, node degree is used to measure the influence of all the nodes connected to a node. 2-order degree considers the influence of a node’s neighbor’s neighbor on the node. 3-order degree considers the influence of a node’s neighbors’ neighbors’ neighbor on that node. As a result, the lower the order of the high-order degree is, the closer it is to the node degree. On the other hand, the higher the order of the high-order degree is, the closer it is to eigenvector centrality.Theorem 2.
Fors-order degree in undirected network, if s=1, it is the node degree of the network. As s approaches to infinity, s-order degree is equivalent to eigenvector centrality.We only need to show that whens approaches to infinity, s-order degree is equivalent to eigenvector centrality. Suppose A is the adjacency matrix in an undirected network and d1 is the degree sequence. Then by Theorem 1, the s-order degree sequence is As-1∗d1, which is consistent with calculating the largest eigenvalue and the corresponding eigenvector by the method of power rule [62]. Therefore, the normalized result of As-1∗d1(s→+∞) is the node eigenvector centrality. If the eigenvector centrality is deemed as the most accurate method in ranking nodes, then from node degree to high-order degree, and to eigenvector centrality, the accuracies get higher and higher, and the computation complexity gets higher and higher at the same time. Therefore, if there is not high requirement on ranking accuracy and computation complexity, high-order degree is a relatively good choice.In fact, high-order degrees are not simple alternative to eigenvector centrality. Sometimes high-order degrees may be more intuitive than some methods including eigenvector centrality. For example, Figure2(a), the top three nodes sorted by both 2-order degree and 4-order degree are 5, 6, 4, which we can see from Tables 1 and 4; it is the same as our supposition. Otherwise the top three nodes sorted by both betweenness and eigenvector centrality are 6, 5, 4.Table 4
Different centralities of Figure2.
Name of each node 1 2 3 4 5 6 7 8 9 10 Figure2(a) 4-order degree 21 21 21 26 50 35 29 29 29 29 Betweenness 0 0 0 21 20 26 0 0 0 0 Eigenvector centrality 0.0547 0.0547 0.0547 0.1296 0.1431 0.2096 0.0884 0.0884 0.0884 0.0884  Figure2(b) 3-order in-degree 0 0 1 2 0 2 3 4 4 6 PageRank∗ 0 0 0 0.1795 0 0.1154 0.1795 0.1154 0.2308 0.1795 PageRank∗∗ 0.0150 0.0318 0.0610 0.1255 0.0505 0.1134 0.1417 0.1283 0.1827 0.1501 ∗ PageRank without damping factor. ∗ ∗ PageRank with damping factor equal to 0.85.


### 4.2. The High-Order Degree and PageRank for Directed Network

Theorem 3.
Fors-order out-degree in a directed network, if s=1, it is the out-degree of the directed network. For s-order in-degree in a directed network, if s=1, it is the in-degree of the directed network. When s approaches to infinity, the s-order in-degree is equivalent to PageRank (without damping factor).Theorem3 is clearly true because PageRank is the simplification of eigenvector centrality in directed network [63]. Moreover, we can reach similar conclusions that when ranking network nodes, high-order in-degree is a good choice if one has certain but not high requirements on the accuracy and computation complexity.Same as Section4.2, high in-order degrees are not simple alternative to PageRank. Sometimes high in-order degrees may be more intuitive than PageRank. For example Figure 2(b), the top node sorted by both 2-order in-degree and 3-order in-degree is 9, which we can see from Tables 1 and 4, it is the same with our supposition. Otherwise the top node sorted by both PageRank without damping factor and PageRank with damping factor is 9.


### 4.3. The Significance of Network High-Order Out-Degree

PageRank (high-order in-degree) indicates that thePR value of a node va is larger when there are more nodes pointing to va in a directed network (quantity hypothesis) and/or the nodes pointing va have larger PR values (quality hypothesis) [35, 36]. Reversely, we call high-order out-degree Reverse PageRank (RPR). The RPR value of a node vb in a directed network is determined by how many nodes pointed by vb (reverse quantity hypothesis) and/or how large RPR value that nodes pointed by vb have (reverse quality hypothesis). For example, we can say that the World Wide Web navigation websites have large RPR value. When someone surfs the Internet, if he does not know which website is worth visiting (with larger PR value), he should start with the navigation website (with larger RPR value). There is more research on the high-order in-degree (PR) for directed network, but there is no research on high-order out-degree (RPR) as far as we know.Figure2(b), although nodes 1, 2, 5 have the same 2-order out-degree, only node 1 has the largest n-order out-degree (n≥3). Node 1 is the only one that can reach any nodes of this graph.


### 4.4. The Combined Degree We Defined and the Mixed Degree Zeng Defined

Zeng [44] used the weighted sum of both the residual degree and the exhausted degree to define the mixed degree of the node of a network. On one hand, Zeng’s definition involves Mixed Degree Decomposition (MDD) to the whole network by using coreness centrality, while the combined degree we defined is based on a linear combination of various high-order degrees. Even though our method involves more terms in the weighted sum, it does not need to consider network decomposition. Therefore it is cheaper in computation than Zeng’s definition. On the other hand, Zeng divides the nodes that are connected to a node into two classes according to MDD, while we divide the nodes that are connected to a node into finite number of classes according to path distance, which is more delicate in classification and has more accurate results.


## 4.1. The High-Order Degree and Eigenvector Centrality/Betweenness in Undirected Network

In the undirected network, node degree is used to measure the influence of all the nodes connected to a node. 2-order degree considers the influence of a node’s neighbor’s neighbor on the node. 3-order degree considers the influence of a node’s neighbors’ neighbors’ neighbor on that node. As a result, the lower the order of the high-order degree is, the closer it is to the node degree. On the other hand, the higher the order of the high-order degree is, the closer it is to eigenvector centrality.Theorem 2.
Fors-order degree in undirected network, if s=1, it is the node degree of the network. As s approaches to infinity, s-order degree is equivalent to eigenvector centrality.We only need to show that whens approaches to infinity, s-order degree is equivalent to eigenvector centrality. Suppose A is the adjacency matrix in an undirected network and d1 is the degree sequence. Then by Theorem 1, the s-order degree sequence is As-1∗d1, which is consistent with calculating the largest eigenvalue and the corresponding eigenvector by the method of power rule [62]. Therefore, the normalized result of As-1∗d1(s→+∞) is the node eigenvector centrality. If the eigenvector centrality is deemed as the most accurate method in ranking nodes, then from node degree to high-order degree, and to eigenvector centrality, the accuracies get higher and higher, and the computation complexity gets higher and higher at the same time. Therefore, if there is not high requirement on ranking accuracy and computation complexity, high-order degree is a relatively good choice.In fact, high-order degrees are not simple alternative to eigenvector centrality. Sometimes high-order degrees may be more intuitive than some methods including eigenvector centrality. For example, Figure2(a), the top three nodes sorted by both 2-order degree and 4-order degree are 5, 6, 4, which we can see from Tables 1 and 4; it is the same as our supposition. Otherwise the top three nodes sorted by both betweenness and eigenvector centrality are 6, 5, 4.Table 4
Different centralities of Figure2.
Name of each node 1 2 3 4 5 6 7 8 9 10 Figure2(a) 4-order degree 21 21 21 26 50 35 29 29 29 29 Betweenness 0 0 0 21 20 26 0 0 0 0 Eigenvector centrality 0.0547 0.0547 0.0547 0.1296 0.1431 0.2096 0.0884 0.0884 0.0884 0.0884  Figure2(b) 3-order in-degree 0 0 1 2 0 2 3 4 4 6 PageRank∗ 0 0 0 0.1795 0 0.1154 0.1795 0.1154 0.2308 0.1795 PageRank∗∗ 0.0150 0.0318 0.0610 0.1255 0.0505 0.1134 0.1417 0.1283 0.1827 0.1501 ∗ PageRank without damping factor. ∗ ∗ PageRank with damping factor equal to 0.85.


## 4.2. The High-Order Degree and PageRank for Directed Network

Theorem 3.
Fors-order out-degree in a directed network, if s=1, it is the out-degree of the directed network. For s-order in-degree in a directed network, if s=1, it is the in-degree of the directed network. When s approaches to infinity, the s-order in-degree is equivalent to PageRank (without damping factor).Theorem3 is clearly true because PageRank is the simplification of eigenvector centrality in directed network [63]. Moreover, we can reach similar conclusions that when ranking network nodes, high-order in-degree is a good choice if one has certain but not high requirements on the accuracy and computation complexity.Same as Section4.2, high in-order degrees are not simple alternative to PageRank. Sometimes high in-order degrees may be more intuitive than PageRank. For example Figure 2(b), the top node sorted by both 2-order in-degree and 3-order in-degree is 9, which we can see from Tables 1 and 4, it is the same with our supposition. Otherwise the top node sorted by both PageRank without damping factor and PageRank with damping factor is 9.


## 4.3. The Significance of Network High-Order Out-Degree

PageRank (high-order in-degree) indicates that thePR value of a node va is larger when there are more nodes pointing to va in a directed network (quantity hypothesis) and/or the nodes pointing va have larger PR values (quality hypothesis) [35, 36]. Reversely, we call high-order out-degree Reverse PageRank (RPR). The RPR value of a node vb in a directed network is determined by how many nodes pointed by vb (reverse quantity hypothesis) and/or how large RPR value that nodes pointed by vb have (reverse quality hypothesis). For example, we can say that the World Wide Web navigation websites have large RPR value. When someone surfs the Internet, if he does not know which website is worth visiting (with larger PR value), he should start with the navigation website (with larger RPR value). There is more research on the high-order in-degree (PR) for directed network, but there is no research on high-order out-degree (RPR) as far as we know.Figure2(b), although nodes 1, 2, 5 have the same 2-order out-degree, only node 1 has the largest n-order out-degree (n≥3). Node 1 is the only one that can reach any nodes of this graph.


## 4.4. The Combined Degree We Defined and the Mixed Degree Zeng Defined

Zeng [44] used the weighted sum of both the residual degree and the exhausted degree to define the mixed degree of the node of a network. On one hand, Zeng’s definition involves Mixed Degree Decomposition (MDD) to the whole network by using coreness centrality, while the combined degree we defined is based on a linear combination of various high-order degrees. Even though our method involves more terms in the weighted sum, it does not need to consider network decomposition. Therefore it is cheaper in computation than Zeng’s definition. On the other hand, Zeng divides the nodes that are connected to a node into two classes according to MDD, while we divide the nodes that are connected to a node into finite number of classes according to path distance, which is more delicate in classification and has more accurate results.


## 5. Conclusion

In this paper, we define several novel centrality metrics: the high-order (out-/in-)degree and combined degree. For the values of combined degree’s parameters, we usually consider the caseα1≥α2≥α3≥⋯≥0 and ∑iαi=1. We prove that both the degree centrality and eigenvector centrality are the special cases of the high-order degree of undirected network, and both the in-degree and PageRank algorithm without damping factor are the special cases of the high-order in-degree of directed network. We present several experiments to discuss the performance of our novel centrality metrics. It can be seen from the experiments that the centrality metrics we defined are easy to calculate and perform better than degree centrality. In a large-scale complex network study, our centrality metrics will be an effective alternative to the eigenvector centrality/PageRank algorithm. The manuscript is only limited in introducing the definition of new metrics. We hope to discuss their efficacy and computational cost in the further works.



---

*Source: 4925841-2018-06-27.xml*