Introducing a New Edge Centrality Measure: The Connectivity Rank Index

A new edge centrality measure, connectivity rank index (CRI), is proposed based on the effect of an edge on the network algebraic connectivity. Compared with the existing indices, the CRI can determine the importance of a present edge as well as an absent edge. For large-scale networks, the algorithm based on original CRI definition has high-time complexity. Therefore, an approximation algorithm is designed using the eigenvector elements corresponding to the second smallest Laplacian eigenvalue. This algorithm can identify the most influential edges and the least influential ones easily, which reduces the time complexity from the exhaustive searching scheme with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(N^{5})$</tex-math> </inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(N^{3})$</tex-math> </inline-formula> in a network of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$</tex-math> </inline-formula> . Some examples are shown to verify the effectiveness of the algorithm and the theoretical results.