An algorithm for updating betweenness centrality scores of all vertices in a graph upon deletion of a single edge
Open Access
- 29 June 2022
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Complex Networks
- Vol. 10 (4)
Abstract
Betweenness centrality (BC) is a measure of the importance of a vertex in a graph, which is defined using the number of the shortest paths passing through the vertex. Brandes proposed an efficient algorithm for computing the BC scores of all vertices in a graph, which accumulates pair dependencies while traversing single-source shortest paths. Although this algorithm works well on static graphs, its direct application to dynamic graphs takes a huge amount of computation time because the BC scores must be computed from scratch every time the structure of graph changes. Therefore, various algorithms for updating the BC scores of all vertices have been developed so far. In this article, we propose a novel algorithm for updating the BC scores of all vertices in a graph upon deletion of a single edge. We also show the validity and efficiency of the proposed algorithm through theoretical analysis and experiments using various graphs obtained from synthetic and real networks.Keywords
Funding Information
- Japan Society for the Promotion of Science (JP21H03510)
This publication has 46 references indexed in Scilit:
- Fast network centrality analysis using GPUsBMC Bioinformatics, 2011
- Identification of influencers — Measuring influence in customer networksDecision Support Systems, 2008
- On variants of shortest-path betweenness centrality and their generic computationSocial Networks, 2008
- CENTRALITY ESTIMATION IN LARGE NETWORKSInternational Journal of Bifurcation and Chaos, 2007
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- On the computational complexity of dynamic graph problemsTheoretical Computer Science, 1996
- Faster algorithms for the shortest path problemJournal of the ACM, 1990
- Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computationCommunications of the ACM, 1988
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977