# Efficient Top-k Ego-Betweenness Search

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2021.

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

- [Generative and Contrastive Paradigms Are Complementary for Graph Self-Supervised Learning](https://mlsanity.com/paper/2310.15523/) (2023)
- [CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs](https://mlsanity.com/paper/2506.14122/) (2025)

## Abstract (arXiv)

Betweenness centrality, measured by the number of times a vertex occurs on all shortest paths of a graph, has been recognized as a key indicator for the importance of a vertex in the network. However, the betweenness of a vertex is often very hard to compute because it needs to explore all the shortest paths between the other vertices. Recently, a relaxed concept called ego-betweenness was introduced which focuses on computing the betweenness of a vertex in its ego network. In this work, we study a problem of finding the top-k vertices with the highest ego-betweennesses. We first develop two novel search algorithms equipped with a basic upper bound and a dynamic upper bound to efficiently solve this problem. Then, we propose local-update and lazy-update solutions to maintain the ego-betweennesses for all vertices and the top-k results when the graph is updated, respectively. In addition, we also present two efficient parallel algorithms to further improve the efficiency. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.