Centrality Measures on Big Graphs

Centrality measures allow to measure the relative importance of a node or an edge in a graph w.r.t.~other nodes or edges. Several measures of centrality have been developed in the literature to capture different aspects of the informal concept of importance, and algorithms for these different measures have been proposed. In this tutorial, we survey the different definitions of centrality measures and the algorithms to compute them. We start from the most common measures, such as closeness centrality and betweenness centrality, and move to more complex ones such as spanning-edge centrality. In our presentation, we begin from exact algorithms and then progress to approximation algorithms, including sampling-based ones, and to highly-scalable MapReduce algorithms for huge graphs, both for exact computation and for keeping the measures up-to-date on dynamic graphs where edges are inserted or removed over time. Our goal is to show how advanced algorithmic techniques and scalable systems can be used to obtain efficient algorithms for an important graph mining task, and to encourage research in the area by highlighting open problems and possible directions.