Improving Estimation of Betweenness Centrality for Scale-Free Graphs

Citations Over Time

Abstract

Betweenness centrality is a graph statistic used to nd vertices that are participants in a large number of shortest paths in a graph. This centrality measure is commonly used in path and network interdiction problems and its complete form requires the calculation of all-pairs shortest paths for each vertex. This leads to a time complexity of O(jV jjEj), which is impractical for large graphs. Estimation of betweenness centrality has focused on performing shortest-path calculations on a subset of randomly- selected vertices. This reduces the complexity of the centrality estimation to O(jSjjEj); jSj < jV j, which can be scaled appropriately based on the computing resources available. An estimation strategy that uses random selection of vertices for seed selection is fast and simple to implement, but may not provide optimal estimation of betweenness centrality when the number of samples is constrained. Our experimentation has identi ed a number of alternate seed-selection strategies that provide lower error than random selection in common scale-free graphs. These strategies are discussed and experimental results are presented.

Related Papers

• → Towards identifying influential nodes in complex networks using semi-local centrality metrics(2023)36 cited
• → Toward More Effective Centrality-Based Attacks on Network Topologies(2020)15 cited
• → Lightweight Centrality Measures in Networks under Attack(2006)11 cited
• → Identifying influential nodes in complex network based on weighted semi-local centrality(2016)4 cited
• → Flowthrough Centrality: A Stable Node Centrality Measure(2022)