The Parameterized Complexity of Maximum Betweenness Centrality

Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents.

Specifically, we study the computation complexity of the Maximum Betweenness Centrality problem, which consists in finding a group of size \(k\) whose betweenness centrality exceeds a given threshold. Since this problem is \(NP\)-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is \(W[1]\)-hard and in \(XP\) when parameterized by the group size \(k\). As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits \(FPT\) algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.