Viðburðir eftir árum

Coverage Centrality Maximization

Gianlorenzo D'Angelo, Gran Sasso Science Institute, L'Aquila, Italy

  • 21.10.2020, 13:00 - 14:00

Online lecture from Gianlorenzo D'Angelo, Gran Sasso Science Institute, L'Aquila, Italy, 21 October at 13:00 GMT.

Virtual link: 

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)).

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: