Biharmonic Distance Related Centrality for Edges in Weighted Networks

Yuhao Yi, Liren Shan, Huan Li, Zhongzhi Zhang

Abstract

This paper introduces Biharmonic Distance Related Centrality (BDRC), a novel metric for identifying vital edges in weighted networks. By leveraging the sensitivity of the network's overall connectivity (the Kirchhoff index) to changes in edge resistance, BDRC provides a more discriminating measure than traditional centralities. We present a nearly linear-time approximation algorithm (AppxBDRC) that enables the analysis of massive networks with millions of edges while maintaining high accuracy.

1. Introduction

Identifying critical edges is a fundamental task in network science, with applications ranging from community detection to infrastructure protection. Traditional measures like Edge Betweenness, Spanning Edge Centrality, and Current-Flow Centrality often fall short. Betweenness ignores non-shortest paths, Spanning Edge Centrality fails to distinguish between different "cut edges," and Current-Flow Centrality is computationally prohibitive for large-scale datasets ($O(mn^{3/2})$). This work proposes BDRC to address these limitations by providing a mathematically principled, highly sensitive, and computationally efficient metric.

2. Methodology

The core idea of BDRC is to define edge importance based on the sensitivity of the network's overall connectivity, represented by the Kirchhoff index ($R(\mathcal{G})$), to modifications in an edge's resistance ($r_e$). The authors demonstrate that this sensitivity is proportional to the biharmonic distance ($d_B$) between the edge's endpoints:

$$C(e) = n w_e^2 d_B^2(u, v)$$

where $n$ is the node count and $w_e$ is the edge weight. To make this metric scalable, the authors developed AppxBDRC, a fast approximation algorithm. It utilizes the Johnson-Lindenstrauss Lemma for dimensionality reduction and nearly linear-time Laplacian solvers. The resulting complexity is $\tilde{O}(m \log c / \epsilon^2)$, making it suitable for modern massive networks.

3. Experimental Evaluation

The proposed method was evaluated on a diverse set of real-world networks from the Koblenz Network Collection, including road networks (Chicago, Pennsylvania), social networks (Facebook, Brightkite), and biological networks (Reactome). These datasets range from hundreds of nodes to over 1 million nodes and 1.5 million edges.

3.1 Discriminating Power

A key advantage of BDRC is its ability to distinguish between edges that other metrics might rank identically. Empirical results show that BDRC consistently exhibits a higher relative standard deviation across various networks compared to betweenness, current-flow, and spanning tree centralities. This indicates that BDRC provides a much clearer ranking of edge importance.

Relative standard deviation of different centrality measures across various networks.

3.2 Scalability and Accuracy

The AppxBDRC algorithm demonstrates remarkable scalability. While exact calculations are limited by memory on networks exceeding $10^5$ nodes, AppxBDRC successfully processed the Pennsylvania road network (1.5M edges) in approximately 1.5 hours with $\epsilon=0.1$.

Runtime comparison between ExactBDRC and AppxBDRC with varying error parameters across different networks.

Furthermore, the approximation is highly accurate. In empirical tests, the mean relative error was consistently around 1% to 2%, which is significantly better than the theoretical worst-case bounds.

4. Conclusion

BDRC offers a robust and efficient framework for edge centrality analysis. By linking global network robustness to local biharmonic distances, it captures both structural and dynamical importance. Future work may involve extending this framework to directed networks and exploring node-level centrality applications in greater depth.

Summary updated

Abstract

The Kirchhoff index, defined as the sum of effective resistances over pairs all of nodes, is of primary significance in diverse contexts of complex networks. In this paper, we propose to use the rate at which the Kirchhoff index changes with respect to the change of resistance of an edge as a measure of importance for this edge in weighted networks. For an arbitrary edge, we explicitly determine the change of the Kirchhoff index and express it in terms of the biharmonic distance between its end nodes, and thus call this centrality as biharmonic distance related centrality (BDRC). We show that BDRC has a better discriminating power than those commonly used metrics, such as edge betweenness and spanning edge centrality. We give an efficient algorithm that provides an approximation of biharmonic distance for all edges in nearly linear time of the number of edges, with a high probability. Experiment results validate the efficiency and accuracy of the presented algorithm.
BibTeX
@inproceedings{yi2018biharmonic,
  author = {Yuhao Yi and Liren Shan and Huan Li and Zhongzhi Zhang},
  title = {{Biharmonic Distance Related Centrality for Edges in Weighted Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/503},
}
Figure