Department of
Applied
Mathematics

Exploring Closeness Centrality and Related Measures for Sparse and Planar Graphs

Sudatta Bhattacharya

Indraprastha Institute of Information Technology, Delhi

Abstract

We address the problem of computing closeness centrality and a few related centrality measures that operate on the shortest paths in a graph. We consider sparse graphs, especially planar graphs and this makes our results widely applicable to real-world networks such as social, geographical, citation, biological, communication, etc. on which centrality values are often evaluated in practice. We show that closeness, Harmonic and number-farness centrality values of all nodes of a planar graph can be computed in o(n^2). On the other hand for sparse graphs the optimal algorithms for computing these values of all nodes require O(n^2) time (up to polylogarithmic factor) and is, therefore, computationally no different from betweenness centrality.

We also show that one centrality measures that involves shortest paths passing through a particular node can be computed in O(n^2) in planar graphs and no faster, making it a harder problem compared to the others. One of the centralities that we introduce, between number-farness centrality, has a tight bound of O(n^2) for one node and all nodes in the case of sparse graphs, putting it into a league of its own. Based on these results, we conjecture that for planar graphs, computing betweenness centrality of only a single node can possibly be done in subquadratic time but not of all nodes.