Centrality measures are fundamental in the study of complex networks, offering insights into the relative importance of nodes based on different connectivity patterns. In this talk, we address the problem of enforcing a prescribed Katz [1] or PageRank [2] centrality while maintaining the network’s original structure as much as possible [3]. Specifically, we seek the minimal perturbation of edge weights necessary to achieve the desired centrality values, ensuring that modifications are both efficient and targeted. We formulate this problem as a constrained Quadratic Programming (QP) optimization task and propose scalable numerical methods [4] to solve it. Our approach leverages the structure of the optimization problem to enhance computational efficiency, making it feasible for large-scale networks. By carefully selecting which edges to modify, we ensure that the fundamental topology of the network remains largely intact while achieving the prescribed centrality objectives. Applications of our methodology span various domains. Through extensive computational experiments, we demonstrate the effectiveness of our approach in both synthetic and real-world networks. We also provide an open-source implementation Github of our algorithms, allowing for reproducibility and further research in the field. 

Bibliography 

[1] Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39–43. 
[2] Page , L., & Brin, S. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks, 30(1–7), 107–117. 
[3] Cipolla, S., Durastante, F., & Meini, B. (2024). Enforcing Katz and PageRank Centrality Measures in Complex Networks, arXiv 2409.02524. 
[4] Cipolla, S., & Gondzio, J. (2023). Proximal stabilized interior point methods and low-frequency-update preconditioning techniques. J. Optim. Theory Appl., 197(3), 1061–1103