Centrality maximization in complex networks

One of the main issue in complex networks analysis consists in determining what are the most important nodes in a network. For this reason, researchers have defined several centrality indices in order to measure this concept. In several scenarios, having a high centrality can have a positive impact on the node itself. Hence, in this thesis we study the problem of determining how much a node can increase its centrality by creating a limited amount of new edges incident to it. In particular, we cope with the problem of adopting the best strategy in order to increase the value of two well known centrality indices namely harmonic centrality (cm-h) and betweenness centrality (cm-b). We show that cm-h cannot be approximated in polynomial-time within a factor 1− 1 3e in directed graphs and 1 − 1 15e in undirected graphs, unless P = NP. On the other hand, we prove that cm-b cannot be approximated in polynomial time within a factor 1 − 1 2e in both directed and undirected graphs, unless P = NP. We then propose a greedy approximation algorithm for both problems with an almost tight approximation ratio in all the cases except for cm-b in undirected networks. We test the performance of our algorithms on both synthetic and real-world networks and we show that they provide a good solution in every case. Moreover, we design some heuristics in order to speed up the computation and run the algorithm on large graphs with millions of nodes and edges. We also study the problem of improving the ranking according to harmonic centrality (crmb) and betweenness centrality (crm-b) by adding a limited amount of edges incident to a given node and we prove that it does not admit any polynomial-time constant factor approximation algorithm, unless P = NP. However, we experimentally show that our greedy algorithms allow a node to reach the top positions in the ranking by adding few new edges.