Politecnico di Torino | Servizi per la didattica

KEYWORD

Centrality measures on networks

keywords ADVERSARIAL GAME, CENTRALITY MEASURE, NETWORK, PAGE RANK

Reference persons GIACOMO COMO, FABIO FAGNANI

Research Groups Analisi e controllo di sistemi dinamici

Thesis type METHODOLOGICAL

Description Centrality measures play a crucial role in the analysis of networks both in socio-economic models as well in engineering. Nodes with high centrality are those where shocks can potentially have the most disruptive effects, triggering cascade effects in the whole network. Their individuation is at the basis of understanding the systemic risk of the network, namely its potential fragility to small localized perturbations. Nodes with high centrality are, on the other hand, the natural target of intervention strategies, in socio-economic applications, that aim to maximally enhance or depress the performance of the network. They are also, complementarily, the target of strategies that instead aim to protect the network from external shocks.

In this thesis we will review a family of popular centrality measures (e.g. Katz, Bonacich, page-rank) and analyze how such indices depend on the topology of the network and how they can be modified by perturbing (e.g. adding or deleting links) a part of the network. Possible research problems are the following:

1. Formulate and solve optimization problems where a desired target of the centrality is traded against the cost of the intervention;
2. Study game adversarial problems where two or more agents are modifying a network in order to achieve different (and typically antithetic) shaping of the centrality.

[1] G. Como and F. Fagnani, Robustness of large-scale stochastic matrices to localized perturbations, IEEE Transactions on Network Science and Engineering, 2 (2), pp. 1-12, 2015.

[2] M. Castaldo, C. Catalano, G. Como, F. Fagnani, On a centrality maximization game. ArXiv https://arxiv.org/abs/1911.06737