Coverage Centrality Maximization
Gianlorenzo D'Angelo, Gran Sasso Science Institute, L'Aquila, Italy
Online lecture from Gianlorenzo D'Angelo, Gran Sasso Science Institute, L'Aquila, Italy, 21 October at 13:00 GMT.
https://cs.gssi.it/gianlorenzo.dangelo/
Virtual link: https://us02web.zoom.us/j/81637641318
Centrality metrics are among the main tools in social network analysis. Being central for a user of a network leads to several benefits to him: central users are highly influential and play key roles within the network. Therefore, the problem of increasing the centrality of a network user recently received considerable attention. Given a network and a target user U, the centrality maximization problem consists in creating k new links incident to U in such a way that the centrality of U is maximized, according to some centrality metric. Most of the algorithms proposed in the literature are based on the greedy paradigm, which guarantees a constant approximation factor whenever the given centrality metric is monotone and submodular with respect to link addition. However, this property does not hold for several shortest-path based centrality metrics.
For the case of coverage centrality, we show strong hardness of approximation bounds: if P\neq NP, the problem cannot be approximated within a factor greater than 1-1/e, and, if the gap-ETH hypothesis holds, the problem cannot be approximated within a factor better than 1/n^{o(1)}, where n is the number of users. On the other hand, we propose two greedy approximation algorithms, and show that, by suitably combining them, we can guarantee an approximation factor of Omega (1/sqrt(n)).
