Benchmark for Discriminating Power of Edge Centrality Metrics. (14th September 2021)

• Record Type: Journal Article
• Authors: Bao, Qi; Xu, Wanyue; Zhang, Zhongzhi
• Is Part Of: Computer journal. Volume 65:Number 12(2022)
• Page Start: 3141
• Page End: 3155
• Publication Date: 2021-09-14
• Subjects: network mining -- network centrality -- edge centrality -- social network analysis -- automorphism -- spanning rooted forest; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab132
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Edge centrality has found wide applications in various aspects. Many edge centrality metrics have been proposed, but the crucial issue that how good the discriminating power of a metric is, with respect to other measures, is still open. In this paper, we address the question about the benchmark of the discriminating power of edge centrality metrics. We first use the automorphism concept to define equivalent edges, based on which we introduce a benchmark for the discriminating power of edge centrality measures and develop a fast approach to compare the discriminating power of different measures. According to the benchmark, for a desirable measure, equivalent edges have identical metric scores, while inequivalent edges possess different scores. However, we show that even in a toy graph, inequivalent edges cannot be discriminated by three existing edge centrality metrics. We then present a novel edge centrality metric called forest centrality (FC). Extensive experiments on real-world networks and model networks indicate that FC has better discriminating power than three existing edge centrality metrics.