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

DOI10.1016/J.LAA.2020.11.006zbMATH Open1459.05310arXiv2007.08956OpenAlexW3043444165WikidataQ113869479 ScholiaQ113869479MaRDI QIDQ2228533FDOQ2228533

Nikita Deniskin, Francesco Ballini

Publication date: 17 February 2021

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

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.

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

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

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)

Cites Work

• Network Properties Revealed through Matrix Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Walk entropy and walk-regularity
• On the Limiting Behavior of Parameter-Dependent Network Centrality Measures
• Walk entropies in graphs
• Maximum walk entropy implies walk regularity
• A note on walk entropies in graphs
• Title not available (Why is that?)
• Subgraph centrality and walk-regularity

Cited In (3)

• A maple package for integro-differential operators and boundary problems
• New results and open problems on subgraph centrality
• The many facets of the Estrada indices of graphs and networks

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)