Hardness of Approximate Vertex Ranking by Betweenness Centrality in the CONGEST Model

Betweenness centrality is one of the most popular metrics to quantify the importance of vertices within a network. We consider distributed vertex ranking algorithms based on betweenness centrality in the CONGEST model. Hua et al. show an O(n)-round algorithm of computing the exact values of betweenness centralities for all vertices in the CONGEST model, where n is the number of vertices. They also show a nearly-tight Ω (n)-round lower bound for computing the exact betweenness centrality of a given single vertex. However, their lower bound does not imply the hardness of ranking based on betweenness centrality. In other words, the hardness of comparing the betweenness centralities of two given vertices is not straightforwardly deduced from the known bound for computing betweeness centralities. It naturally raises the question if there exists a sublinear-time CONGEST algorithm of (approximately) computing the vertex ranking based on betweenness centrality or not. The main contribution of this paper is to provide a negative answer for this question in a very strong sense: Quantifying the preciseness of output rankings by Kendall's τ-distance (i.e.,the number of inversion pairs for the correct ranking), we show that there is no o(n/log3 n)-round algorithm of outputting an approximate ranking within additive error at most (1 - o(1)) · n(n - 1)/4. Since the maximum gap between two rankings is n(n - 1)/2, it implies that no o(n/log3 n)-round algorithm can distinguish the instances whose rankings are almost inverted.