Biharmonic Distance Related Centrality for Edges in Weighted Networks

Biharmonic Distance Related Centrality for Edges in Weighted Networks

Yuhao Yi, Liren Shan, Huan Li, Zhongzhi Zhang

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 3620-3626. https://doi.org/10.24963/ijcai.2018/503

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.
Keywords:
Machine Learning: Data Mining
Multidisciplinary Topics and Applications: Social Sciences
Agent-based and Multi-agent Systems: Computational Social Choice
Machine Learning Applications: Networks