Approximation bounds for centrality maximization problems

Abstract

Determining what are the most important nodes in a network is one of the
main problems in the field of network analysis. Several so-called centrality
indices have been defined in the literature to try to quantitatively capture the
notion of importance (or centrality) of a node within a network. It has been
experimentally observed that being central for a node, according to some
centrality index, leads to several benefits to the node itself.
In this paper, we study the problem of maximizing the centrality index
of a given node by adding a limited number of edges incident to it. We survey
on some recent results on this problem by focusing on four well-known
centrality indices, namely harmonic centrality, betweenness centrality, eccentricity,
and page-rank.