Biharmonic Distance Related Centrality for Edges in Weighted Networks

1 Introduction

Measuring the importance of nodes and edges is a fundamental question at the core of network analysis [You et al., 2017]. A lot of desirable centrality metrics were proposed to capture relative importance of nodes or edges from the perspective of both network topology and dynamics [White and Smyth, 2003], and various algorithms were developed to identify vital nodes and edges [You et al., 2017]. However, most previous work centered on the node level. Actually, edge centrality and its corresponding algorithms also play an indispensable role in network science, as their node counterparts. In the past years, edge centrality has been widely used to a variety of aspects of graph mining and applications, including detecting communities in social and biological networks [Girvan and Newman, 2002], revealing new knowledge in semantic web [Berners-Lee et al., 2001], and identifying social ties in social networks [Ding et al., 2011], designing or protecting infrastructure networks [Bienstock et al., 2014], to name just a few. Thus, it is of theoretical and practical interest to present measures of edge centrality and establish algorithms characterizing the relative importance of edges in networks.

∗Corresponding author. This work was supported by the National Natural Science Foundation of China under Grant No. 11275049.

In view of the relevance of edge importance, some metrics for edge centrality have been presented, with frequently used measures including edge betweenness [Brandes, 2001; Bader et al., 2007; Brandes and Pich, 2007; Geisberger et al., 2008], spanning edge centrality [Teixeira et al., 2013; Mavroforakis et al., 2015; Hayashi et al., 2016], and currentflow centrality [Brandes and Fleischer, 2005]. The betweenness of an edge is defined as the fraction of shortest paths between all pairs of nodes that pass through the edge. The spanning edge centrality of an edge is the probability that it is in a uniformly selected spanning tree. While the currentflow centrality of an edge is defined as the amount of current flowing through this edge. Despite their wide applications, these edge centrality metrics have their respective weakness. For instance, edge betweenness only includes the contribution of shortest paths, neglecting those from other longer paths; spanning edge centrality fails to distinguish any pair of cut edges; while the computational complexity for current-flow centrality is high. In addition, for weighted networks these measures either do not apply, or have prohibitively high computational cost.

To overcome the weakness of above mentioned measures for edge centrality, a new index called the Kirchhoff edge centrality was proposed very recently [Li and Zhang, 2018]. Since the criteria of edge importance are dependent on real problems or applications [You et al., 2017], the Kirchhoff edge centrality was defined according to the Kirchhoff index [Klein and Randi´c, 1993], the sum of effective resistances over all pairs of nodes in the network. The Kirchhoff index is a relevant quantity in many real scenarios and has found wide applications. For example, it has been applied to measure the overall connectedness of a network [Tizghadam and LeonGarcia, 2010] and the robustness of first-order consensus algorithm in noisy networks [Patterson and Bamieh, 2014]. In contrast to the aforementioned measures, the Kirchhoff edge centrality is more discriminating and is provably approximated in nearly linear time [Li and Zhang, 2018]. However, the definition of the Kirchhoff edge centrality involves a parameter θ, how to select θ is still not solved. Moreover, the computation for the Kirchhoff edge centrality needs computing Schur complements of a matrix, the implementation of which is not available. Therefore, there exists a gap between the performance framework for the Kirchhoff edge centrality and an efficient implementation.

In this paper, based on the popular notion of the Kirchhoff index, we propose a novel edge centrality measure for a weighted network by considering it as an electrical network with the resistance of any edge being the reciprocal of the weight in the original weighted networks. Given an edge e, its centrality is defined as the rate at which the Kirchhoff index changes with respect to the change of resistance associated with the edge: The larger the change of the Kirchhoff index is, the more important the edge e is. We demonstrate that the centrality of an edge can be represented in terms of the biharmonic distance between its end nodes, and thus call it biharmonic distance related centrality (BDRC). We show that BDRC is more discriminating than those frequently used metrics, for example, edge betweenness and spanning edge centrality. We also provide a fast algorithm to compute approximate biharmonic distance for all edges in nearly linear time. Finally, we experimentally show that our algorithm is accurate and is significantly faster than the direct computation of the biharmonic distance according to its definition.

2 RelatedWorks

Here we briefly review some edge centrality metrics and their related algorithms, especially the computational complexity of these algorithms.

Edge betweenness is one of the popular edge centrality measures. The betweenness of an edge is the probability of a shortest path between two nodes passing through the edge. Brandes presented an algorithm computing the exactly edge betweenness [Brandes, 2001]. Given a network with n nodes and m edges, the computational cost of this algorithm is O(nm) for unweighted networks, and O(nm + n2 logn) for weighted networks, which is computationally expensive. Afterwards, some approximate approaches were developed to speed up the computation [Bader et al., 2007; Brandes and Pich, 2007; Geisberger et al., 2008]. However, these approximate algorithms provide no approximation guarantees.

Spanning edge centrality is another important measure for edge importance proposed in [Teixeira et al., 2013]. For any edge in a network, its spanning edge centrality is the probability that the edge is included in a uniformly chosen spanning tree of the network. Thus far, the best exact algorithm has complexity O(mn3/2 ). Recently two approximation algorithms have been proposed for the purpose of computing spanning edge centrality of massive networks [Mavroforakis et al., 2015; Hayashi et al., 2016], the accuracy of which have theoretical guarantees.

A third edge centrality measure is current-flow centrality that was first introduced in [Brandes and Fleischer, 2005]. By definition, if an edge participates in lots of short paths between node pairs, then it is relatively important with respect to other edges. An algorithm with time complexity O(mn3/2 logn) was designed for computing current-flow centrality in [Brandes and Fleischer, 2005]. Another algorithm with a lower complexity O(mn logn) was proposed in [Mavroforakis et al., 2015].

Very recently, the Kirchhoff edge centrality was proposed [Li and Zhang, 2018], which, together with spanning edge centrality and current-flow centrality, belongs to the class of electrical centrality measures, since they all have a direct connection with effective resistance. In comparison with the first three centrality measures, Kirchhoff edge centrality is more discriminating and can be provably approximated in nearly-linear time. However, the Kirchhoff edge centrality involves determining a parameter θ, and there is no criterion for choosing θ. Moreover, algorithms in [Li and Zhang, 2018] are only theoretically good, their overhead, especially the θdependent factors has much room for improvement. Finally, the algorithms are only in theory stage, it is still a task to bring theory into practice.

In this paper, based on the Kirchhoff index, we propose a novel measure for edge centrality for weighted networks, called biharmonic distance related centrality (BDRC), since it is dependent on biharmonic distance, as will be shown below. The BDRC has a better discriminating power, and can be efficiently approximated with a high probability.

3 Preliminaries

In this section, we give a brief introduction to some basic concepts about graphs, electrical networks and biharmonic distance.

3.1 Graph and LaplacianMatrix

Let G = (V, E, w) be a connected undirected weighted graph (network), where V is the node set, E is the edge set, and w : E → R+ is the positive edge weight function, with we representing the weight of edge e. Then, there are n = |V | nodes and m = |E| edges in G. We use u ∼ v to indicate that nodes u and v are adjacent. Let wmax = maxe∈E we and wmin = mine∈E we.

Let B ∈ R|E|×|V | be the incidence matrix of G. For each edge e connecting two nodes u and v, a direction is assigned arbitrarily. Let b ⊤e be the row of matrix B corresponding to edge e, then beu = 1 if node u is the tail of edge e, beu = -1 if node u is the head of edge e, and beu = 0 otherwise. be can also be written as be = eu - ev, where eu, u ∈ V , is the uth canonical basis of the space R|V | . Let W ∈ R|E|×|E| be a diagonal matrix with the (e, e)th entry being we. Then the Laplacian matrix L of graph G can be written as L = B T WB = ∑e∈E webeb ⊤e .

L is symmetric and positive semidefinite, which means L has a spectral decomposition as L = ∑n-1 i=1 λiuiu⊤i , where 0 < λ1 ≤ λ2 ≤ · · · ≤ λn-1 are its n - 1 positive eigenvalues, and ui, i = 1, 2, . . . , n - 1 are the corresponding mutually orthogonal unit eigenvectors. We denote by L† the pseudoinverse of L, and L2† = (L† )2 . Then L† can be recast as L† = ∑n-1 i=1 1 λi uiu⊤i . Thus, ker(L) = ker(L† ). Let 1n be the n-dimension vector with all entries being 1, let I be the n × n identity matrix, and let 0 be the n × n zero matrix. Define J = 1n 1n1⊤n . Then, we have the following relations: L†L = LL† = I - J, (I - J)2 = I - J, J 2 = J, and JL = LJ = 0 .

3.2 Electrical Networks and Resistance Distance

For any graph G = (V,E,w), we can define an electrical network G = (V, E, r) by considering edges as resistors and considering nodes as junctions between resistors. The resistor of an associated edge e is re = w-1 e . The resistance distance dR(u, v) between two nodes u and v in graph G is defined as the effective resistance between u and v in electrical network G. Specifically, dR(u, v) is defined as the potential difference between u and v when a unit current is injected to u and extracted from v. Let i ∈ R|E| represent the current across all resistors, and let v ∈ R|V | represent the voltages at all junctions. By Kirchoff's law, B ⊤i = c, where c ∈ R|V | denotes the external currents injected at all junctions, and by Ohm's law, W -1 i = Bv. It follows that Lv = c. By the definition of resistance distance, we get

which is the standard definition for resistance distance [Klein and Randi´c, 1993].

Definition 3.1. For a graph G, its Kirchhoff index R(G) is defined as the sum of resistance distance over all its node pairs. That is,

It is easy to verify that R(G) = nTr (L†).

3.3 Biharmonic Distance

The notion of biharmonic distance was first proposed in [Lipman et al., 2010] as a measure of distance between two points on a curve surface.

Definition 3.2. For a graph G, the biharmonic distance dB(u, v) between two nodes u and v is defined by

Biharmonic distance is a metric, which satisfies the following properties: non-negativity, nullity, symmetry, and triangle inequality [Lipman et al., 2010]. It has some advantages over resistance distance and geodesic distance in some realistic contexts, e.g., computer graphics. Moreover, biharmonic distance can be used to measure the robustness of the secondorder noisy consensus problem without leaders [Bamieh et al., 2012]. Below we will show that biharmonic distance is also related to edge centrality in weighted networks.

4 Biharmonic Distance Related Edge Centrality

Generally, the criterion of edge criticality for a graph depends on particular applications. In many realistic contexts of a graph [Tizghadam and Leon-Garcia, 2010; Patterson and Bamieh, 2014], their performance is determined by the Kirchhoff index of the graph, which is the total effective resistance of the corresponding electrical network. Since the Kirchhoff index for a graph is a function of resistances of all resistors in the associated electrical network, the importance of an edge can be captured by the change of the Kirchhoff index with respect to the modification of resistor for the corresponding edge. As shown below, the change of the Kirchhoff index is closely related to the biharmonic distance, and is thus called biharmonic distance related centrality (BDRC).

Definition 4.1. For a graph G = (V, E, w) or its corresponding electrical network G = (V,E, r), let e = (u, v) be an edge with weight we or resistance re = 1/we. The biharmonic distance related centrality C(e) for edge e = (u, v) is defined by

The BDRC C(e) is the rate at which R(G) changes with regard to the change of resistance corresponding to edge e = (u, v). Therefore, this edge centrality index quantifies the influence of an edge on the performance of the network characterized by the Kirchhoff index. The larger the change C(e) of R(G), the more important the edge e.

An advantage of BDRC is that it can be explicitly determined.

Theorem 4.2. For an edge e = (u, v) in graph G = (V, E, w), its BDRC can by expressed by

Proof. By definition, we have

On the other hand,

Then, we can derive that

This completes the proof.

Theorem 4.2 indicates that the BDRC C(e) of an edge e = (u, v) is simultaneously determined by its weight we and the biharmonic distance dB(u, v) between the end nodes u and v of edge e. Thus, the BDRC C(e) reflects both the structural and dynamical importance of edge e.

5 Comparison with Different Measures

In this section, we show that the BDRC has a more discriminating power than other measures, e.g., edge betweenness centrality and spanning edge centrality.

Let us consider the two edges e1 and e2 in the disturbed ring graph in Figure 1. By intuition, e1 is more important than e2. This can be understood from the following arguments If we delete e1, the shortest path length between u and v increases by 12; if we remove e2, the length of shortest paths between any node pair will increase by at most 1. However, betweenness centrality for e1 and e2 are both equal to 24.5, implying the two edges cannot be differentiated by betweenness centrality. According to Theorem 4.2, the BDRC for edges e1 and e2 is C(e1) = 1.1327 and C(e2) = 0.5413, respectively. This shows that e2 is relatively less important than e1, agreeing with our human intuition.

In addition, BDRC also has a better discriminating ability than the spanning edge centrality. Let us consider the edge e3 and any other edge in the double-star graph shown in Figure 2. Spanning edge centrality cannot distinguish them, since their spanning edge centrality is both equal to 1. By contrast, the BDRC is C(e3) = 7 for edge e3, and is 0.9643 for any other edge. Thus, e3 has a higher score, reflecting our intuition.

In order to further demonstrate the ability of BDRC to differentiate between distinct edges in realistic networks, we also experimentally compare BDRC with three frequently used edge centrality measures, edge betweenness, spanning edge centrality, and current-flow edge centrality. For each metric, we numerically calculate the exact centrality value of each edge for some classic real networks listed in Table 1. Similarly to what has been done in [Bergamini et al., 2016], we evaluate the relative standard deviation for each edge centrality measure, which is defined as the standard deviation divided by the average. Figure 3 reports the relative standard deviation for all measures of edge centrality. It is always higher for BDRC than it is for other three metrics, indicating that BDRC can better distinguish between different edges.

6 Fast Approximation Algorithm

A straightforward way to calculate BDRC C(e) of an edge e involves computing the pseudoinverse of L2 , which has a complexity of O(n3 ), making it infeasible to huge networks. In this section, we propose an algorithm to compute an approximation of C(e) for all e ∈ E with a high probability in nearly linear time with respect to the number of edges. Before introducing our algorithm, we recall two lemmas that are critical to proving the approximation factor of our algorithm. In what follows we use the notation ˜O(·) to hide poly(log n) factors.

Lemma 6.1 (Johnson-Lindenstrauss Lemma, [Achlioptas, 2001]). Given fixed vectors v1, v2, . . . , vn ∈ Rd and ϵ > 0, let Qk×d be a random ±1/√k matrix (i.e., independent Bernoulli entries) with k ≥ 24 logn/ϵ2 . Then with probability at least 1-1/n,

Lemma 6.2 ([Spielman and Teng, 2004]). There is an algorithm x = LaplSolve(L, y, δ) which takes a Laplacian matrix L, a column vector y, and an error parameter δ > 0, and returns a column vector x satisfying

where ‖y‖L = √yT Ly. The algorithm runs in expected time ˜O (m log(1/δ)).

From (3), for any pair of nodes u and v in G, d2B (u, v) can be rewritten as d2B (u, v) = ‖L† (eu - ev)‖2 . Thus, dB(u, v) = ‖L† (eu - ev)‖, which is actually the Euclidean distance between vectors L†eu and L†ev. Then, by projecting vectors L†ev, v ∈ V , into a subspace spanned by k =

1 All data can be found at http://wwwpersonal.umich.edu/˜mejn/netdata/

O(log n)-dimensional random vectors and using LaplSolve, we can introduce a fast algorithm to approximate the biharmonic distance dB(u, v) for each edge e ∈ E.

Let Q be a k×n random projection matrix. By Lemma 6.1, QL† (eu - ev) is a good approximation for d2B (u, v). However, computing Z = QL† directly involves calculating L† . We avoid this by solving the system of equations Lz i = qi, i = 1, . . . , k, where z ⊤i and q ⊤i are the ith row of Z and Q, respectively. Lemma 6.2 shows that z ⊤i can be efficiently approximated by using LaplSolve.

Lemma 6.3. Given a k × n matrix Z that satisfies

where

Then for any pair of nodes u and v belonging to V ,

Proof. To prove (9), it suffices to show that for any pair of

nodes u and v,

which is satisfied if

We now prove that (10) is true. Note that in a connected graph G, there is a simple path P between any two nodes u and v. Applying the triangle inequality along P , we obtain

The square of the last sum term can be evaluated as:

where the first inequality follows from Cauchy-Schwarz inequality, ‖ · ‖F denotes the Frobenius norm of a matrix, and the last inequality follows from (7) and can be further evaluated as

The last inequality follows by the fact that Tr(L† ) = R(G)/n, where R(G) achieves the maximum value n(n2 - 1)/6 when G is an n-node path graph. On the other hand,

The last inequality in (11) is due to the fact that wmaxLKn - LG is positive semidefinite, while LKn is the Laplacian of an n-node clique whose edge weights are all equal to 1. Thus,

where δ is given by (8).

Lemma 6.3 leads to the following theorem.

Theorem 6.4. There is an ˜O(mlog c/ϵ2 ) time algorithm, which inputs 0 < ϵ < 1 and G = (V, E, w) where c = w2max wmin , and returns a (24 log n/ϵ2 )×n matrix ˜Z such that with probability at least 1-1/n,

for any pair of nodes u, v ∈ V .

Based on Theorem 6.4, we propose an algorithm AppxBDRC to approximately compute C(e) for all edges e ∈ E, the pseudocode of which is shown in Algorithm 1.

Algorithm 1: AppxBDRC(G, ϵ)

Input : G: a connected undirected graph.

ϵ: approximation parameter of edge centrality

C = {e, ˆ

Output : ˆ

c(e)|e ∈ E}: ˆ

c is an approximation

of C(e), the BDRC of e.

1 L = Laplacian of G, ˆ c(e)=0 for all e ∈ E

2 k = ⌈24 logn/ϵ2 ⌉

3 for i = 1 to k do

4 Construct a ±1/√k random vector qi of size n×1

5

6

7

˜

z i = LaplSolve(L, qi, δ) where δ is given by (8)

for each e ∈ E do

ˆ

c(e) = ˆ

c(e) + nw2

C = {e, ˆ

8 return ˆ

z i,u - ˜

e |˜

c(e)|e ∈ E}

z i,v |2

7 Experimental Evaluation

In this section, we experimentally evaluate the efficiency and accuracy of our approximation algorithm.

We evaluate the algorithm on a large set of real-world networks from different domains. The data of these networks are taken from the Koblenz Network Collection [Kunegis, 2013]. We run our experiments on the largest connected components (LCC) of these networks, related information of which is shown in Table 2.

We run all the experiments on a Linux box with an Intel i77700K @ 4.2-GHz (4 Cores) and with 32GB memory. We implement the algorithm AppxBDRC in Julia v0.6.0, where the LaplSolve is from [Kyng and Sachdeva, 2016], the Julia language implementation of which is accessible on the website 2 .

To demonstrate the efficiency of our approximation algorithm AppxBDRC, in Table 2, we compare the running time of AppxBDRC with that of the accurate algorithm called ExactBDRC that calculates biharmonic distance by inverting L2 + J and computing the BDRC of every edge according to (6). To objectively evaluate the running time of the algorithms, for both ExactBDRC and AppxBDRC on all considered networks excluding the last five ones marked with ∗, we enforce the program to run on a single thread. The results show that for moderate ϵ, AppxBDRC is significantly faster than ExactBDRC, especially for large networks. For the last five networks with node number ranging from 105 to 106 , we cannot run the ExactBDRC algorithm due to memory limit and high time cost. In contrast, for these networks, we approximately compute BDRC for all edges. This further show that AppxBDRC is efficient and scalable, which is suitable for large networks.

In addition to the efficiency, we also evaluate the accuracy of the approximation algorithm AppxBDRC. To this end, we compare the approximate result of AppxBDRC with the exact result calculated by ExactBDRC. In Table 3, we provide the mean relative error σ of our approximation algorithm, where σ is defined as σ = 1m ∑e∈E |C(e) - ˆ c(e)|/C(e). The results show that the actual mean relative errors for all ϵ and all networks are insignificant, which are magnitudes smaller than the theoretical guarantee. Thus, the approximation algorithm AppxBDRC leads to very accurate results in practice.

2 http://danspielman.github.io/Laplacians.jl/latest/

8 Conclusion

In this paper, we introduced a definition of centrality to measure the importance of edges in weighted networks. For every edge, this new centrality is defined as the sensitivity of the Kirchhoff index on the modification of resistance associated with the edge. We derived that for any edge, its centrality is proportional to the square of the product of its weight and the biharmonic distance between its two endnodes, which is thus called biharmonic distance related centrality (BDRC). We showed that the BDRC measure is more discriminating than edge betweenness and spanning tree centrality. Moreover, we provided an approximation algorithm with probabilistic guarantee, which computes BDRC for all edges in a network in nearly-linear time. Extensive experiments demonstrated that the proposed algorithm is both efficient and accurate in large networks.

It deserves to mention that the proposed edge centrality can be easily extended to the node level, by defining the centrality of a node as the sum of centrality of all edges incident to it. Moreover, the approximate method for computing biharmonic distance can be applied to related areas, such as computer graphics [Lipman et al., 2010] and second-order noisy consensus dynamics without leaders [Bamieh et al., 2012].