Introducing a New Edge Centrality Measure: The Connectivity Rank Index
IEEE Transactions on Systems Man and Cybernetics Systems 54(5): 2757-2764
Article 2024 English
Authors
JZ
Jin Zhou
YZ
Yanqi Zhang
JL
Jun-an Lu
Abstract
1 min read
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.
Discussion(0)
No comments yet. Be the first to comment.