Scalable online betweenness centrality in evolving graphs

Nicolas Kourtellis; Gianmarco De Francisci Morales; Francesco Bonchi

doi:10.1109/ICDE.2016.7498421

Scalable online betweenness centrality in evolving graphs

Nicolas Kourtellis, Gianmarco De Francisci Morales, Francesco Bonchi

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

21 Citations (Scopus)

Abstract

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 language	English
Title of host publication	2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Publisher	IEEE
Pages	1580-1581
Number of pages	2
ISBN (Electronic)	978-1-5090-2020-1
DOIs	https://doi.org/10.1109/ICDE.2016.7498421
Publication status	Published - 22 Jun 2016
MoE publication type	A4 Conference publication
Event	International Conference on Data Engineering - Seoul, Korea, Republic of Duration: 13 Apr 2015 → 17 Apr 2015 Conference number: 31

Conference

Conference	International Conference on Data Engineering
Abbreviated title	ICDE
Country/Territory	Korea, Republic of
City	Seoul
Period	13/04/2015 → 17/04/2015

Access to Document

10.1109/ICDE.2016.7498421

Cite this

@inproceedings{7d5cb0a0d3c3461a841e5c95e0fe1dcf,

title = "Scalable online betweenness centrality in evolving graphs",

abstract = "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.",

author = "Nicolas Kourtellis and {De Francisci Morales}, Gianmarco and Francesco Bonchi",

year = "2016",

month = jun,

day = "22",

doi = "10.1109/ICDE.2016.7498421",

language = "English",

pages = "1580--1581",

booktitle = "2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016",

publisher = "IEEE",

address = "United States",

note = "International Conference on Data Engineering , ICDE ; Conference date: 13-04-2015 Through 17-04-2015",

}

TY - GEN

T1 - Scalable online betweenness centrality in evolving graphs

AU - Kourtellis, Nicolas

AU - De Francisci Morales, Gianmarco

AU - Bonchi, Francesco

N1 - Conference code: 31

PY - 2016/6/22

Y1 - 2016/6/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84980320164&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2016.7498421

DO - 10.1109/ICDE.2016.7498421

M3 - Conference article in proceedings

AN - SCOPUS:84980320164

SP - 1580

EP - 1581

BT - 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

PB - IEEE

T2 - International Conference on Data Engineering

Y2 - 13 April 2015 through 17 April 2015

ER -

Scalable online betweenness centrality in evolving graphs

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this