Introducing a New Edge Centrality Measure: The Connectivity Rank Index
提出一种基于网络代数连通性的边中心性度量（CRI），能同时评估已有边和缺失边的重要性，并设计了近似算法将时间复杂度从O(N^5)降至O(N^3)，适用于大规模网络。
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.