Vertex distinction with subgraph centrality: A proof of Estrada's conjecture and some generalizations

Centrality measures are used in network science to identify the most important vertices for transmission of information and dynamics on a graph. One of these measures, introduced by Estrada and collaborators, is the beta-subgraph centrality, which is based on the exponential of the matrix beta A, where A is the adjacency matrix of the graph and beta is a real parameter ("inverse temperature"). We prove that for algebraic beta, two vertices with equal beta-subgraph centrality are necessarily cospectral. We further show that two such vertices must have the same degree and eigenvector centralities. Our results settle a conjecture of Estrada and a generalization of it due to Kloster, Kral and Sullivan. We also discuss possible extensions of our results.