Scalable online betweenness centrality in evolving graphs

Nicolas Kourtellis, Gianmarco De Francisci Morales, Francesco Bonchi

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

14 Citations (Scopus)


Betweenness centrality measures the importance of an element of a graph, either a vertex or an edge, by the fraction of shortest paths that pass through it [1]. This measure is notoriously expensive to compute, and the best known algorithm, proposed by Brandes [2], runs in O(nm) time. The problems of efficiency and scalability are exacerbated in a dynamic setting, where the input is an evolving graph seen edge by edge, and the goal is to keep the betweenness centrality up to date. In this paper [8] we propose the first truly scalable and practical framework for computing vertex and edge betweenness centrality of large evolving graphs, incrementally and online.

Original languageEnglish
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Number of pages2
ISBN (Electronic)978-1-5090-2020-1
Publication statusPublished - 22 Jun 2016
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Data Engineering - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015
Conference number: 31


ConferenceInternational Conference on Data Engineering
Abbreviated titleICDE
CountryKorea, Republic of

Fingerprint Dive into the research topics of 'Scalable online betweenness centrality in evolving graphs'. Together they form a unique fingerprint.

Cite this