Subgraph centrality and walk-regularity

DOI10.1016/J.LAA.2019.02.005MaRDI QIDQ2419001zbMATH OpenOpenAlexWikidataFDO

Authors Eric Horton, Kyle Kloster, Blair D. Sullivan

Publication date 29 May 2019

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

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

zbMATH Keywords

centralityfunctions of matricesgraph entropynetwork analysiswalk-regularity

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Matrix exponential and similar functions of matrices (15A16)

Abstract: Matrix-based centrality measures have enjoyed significant popularity in network analysis, in no small part due to our ability to rigorously analyze their behavior as parameters vary. Recent work has considered the relationship between subgraph centrality, which is defined using the matrix exponential $f(x)=exp(x)$, and the walk structure of a network. In a walk-regular graph, the number of closed walks of each length must be the same for all nodes, implying uniform $f$-subgraph centralities for any $f$ (or maximum $f$-$extitwalkentropy$). We consider when non--walk-regular graphs can achieve maximum entropy, calling such graphs $extitentropic$. For parameterized measures, we are also interested in which values of the parameter witness this uniformity. To date, only one entropic graph has been identified, with only two witnessing parameter values, raising the question of how many such graphs and parameters exist. We resolve these questions by constructing infinite families of entropic graphs, as well as a family of witnessing parameters with a limit point at zero.

Recommendations

• New results and open problems on subgraph centrality
• Maximum walk entropy implies walk regularity
• Walk entropies in graphs
• Walk entropy and walk-regularity
• Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations

Cites work

• A new status index derived from sociometric analysis
• A note on walk entropies in graphs
• Centrality analysis for modified lattices
• Functional centrality in graphs
• Functions of Matrices
• scientific article; zbMATH DE number 5977361 (Why is no real title available?)
• Information processing in complex networks: Graph entropy and information functionals
• Network properties revealed through matrix functions
• Networks. An introduction.
• On connectivity of the cartesian product of two graphs
• On the limiting behavior of parameter-dependent network centrality measures
• PageRank beyond the web
• The Kronecker Product of Graphs
• Walk entropies in graphs
• Walk entropy and walk-regularity

Cited in

(6)

• Walk entropy and walk-regularity
• Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations
• Maximum walk entropy implies walk regularity
• New results and open problems on subgraph centrality
• Equitable partition and star set formulas for the subgraph centrality of graphs
• Matrix functions in network analysis

Describes a project that uses

Uses Software

• mftoolbox

This page was built for publication: Subgraph centrality and walk-regularity

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