This report explores the use of matrix functions in network analysis, following closely the work of Benzi and Boito. We first establish several foundational results in algebraic graph theory, including properties of the adjacency and Laplacian matrices of undirected graphs, and provide an overview of the Perron-Frobenius theorem’s consequences for graph centrality. We then prove that the diagonal entries of powers of the adjacency matrix count closed walks, and use this to give an explicit walk-counting interpretation of the limit to which the power method converges under primitivity assumptions. Finally, we implement and compare five centrality measures — degree centrality, eigenvector centrality, subgraph centrality, total communicability, and Katz centrality — on two real-world networks, reproducing Tables 3 and 4 of Benzi and Boito and discussing discrepancies between our results and the reference.
The code you find here was used to generate the tables you can find in the reports.
This file contains implementations to compute the different centralities we considered. Each method takes as argument a sparse matrix representing the network as we as sometimes hyperparameters. We have given the values used by the paper as default values in the implementation. It also contains two functions to easily load the two example networks used by the paper.
This file contains the main loop which runs the computations and saves them as json files as well as formatted latex table.