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

Abstract

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, Král and Sullivan. We also discuss possible extensions of our results.

arXiv comment8 pages, no figures

References in corpus (7)

• Subgraph Centrality in Complex Networks
• Communicability in complex networks
• The Physics of Communicability in Complex Networks
• Statistical-mechanical approach to subgraph centrality in complex networks
• On the limiting behavior of parameter-dependent network centrality measures
• Strongly Cospectral Vertices
• Discriminating Power of Centrality Measures

Cited by in corpus (1)

• New results and open problems on subgraph centrality