Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms

Understand

Most previous work of centralities focuses on metrics of vertex importance and methods for identifying powerful vertices, while related work for edges is much lesser, especially for weighted networks, due to the computational challenge.

• In this paper, we propose to use the well-known Kirchhoff index as the measure of edge centrality in weighted networks, called $\theta$-Kirchhoff edge centrality.
• The Kirchhoff index of a network is defined as the sum of effective resistances over all vertex pairs.
• The centrality of an edge $e$ is reflected in the increase of Kirchhoff index of the network when the edge $e$ is partially deactivated, characterized by a parameter $\theta$.