# Identifying high betweenness centrality nodes in large social networks

arXiv: https://arxiv.org/abs/1702.06087 · HTML: https://mlsanity.com/paper/1702.06087/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs](https://mlsanity.com/paper/2506.14122/) (2025)

## Abstract (arXiv)

This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, k-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high k-path centrality have high node betweenness centrality. The randomized algorithm runs in time O(kappa3n2-2αlog n) and outputs, for each vertex v, an estimate of its k-path centrality up to additive error of ± n1/2+ α with probability 1-1/n2. Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.