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.
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$.
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