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

DOI10.1016/J.LAA.2020.11.006MaRDI QIDQ2228533zbMATH OpenOpenAlexWikidataFDO

Authors Francesco Ballini, Nikita Deniskin

Publication date 17 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.08956

zbMATH Keywords

cospectral verticesLindemann-Weierstrass theoremwalk-regular graphsubgraph centrality

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Matrix exponential and similar functions of matrices (15A16) Irrationality; linear independence over a field (11J72)

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 $$-subgraph centrality, which is based on the exponential of the matrix $$, where $A$ is the adjacency matrix of the graph and $$ is a real parameter ("inverse temperature"). We prove that for algebraic $$, two vertices with equal $$-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'al and Sullivan. We also discuss possible extensions of our results.

Recommendations

• New results and open problems on subgraph centrality
• A maple package for integro-differential operators and boundary problems
• Equitable partition and star set formulas for the subgraph centrality of graphs
• Subgraph centrality and walk-regularity
• Some New Results on the Eigenvector Centrality

Cites work

• scientific article; zbMATH DE number 3650654 (Why is no real title available?)
• scientific article; zbMATH DE number 47603 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• A note on walk entropies in graphs
• Maximum walk entropy implies walk regularity
• Network properties revealed through matrix functions
• On the limiting behavior of parameter-dependent network centrality measures
• Subgraph centrality and walk-regularity
• Walk entropies in graphs
• Walk entropy and walk-regularity

Cited in

(5)

• Subgraph centrality and walk-regularity
• The many facets of the Estrada indices of graphs and networks
• Equitable partition and star set formulas for the subgraph centrality of graphs
• New results and open problems on subgraph centrality
• A maple package for integro-differential operators and boundary problems

This page was built for publication: Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228533)