# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 17.12.2019 at 10:45 in 510, there is the following noon lecture:

# 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 diﬀerent 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.

Webmaster: kamweb.mff.cuni.cz Archive page