Walk entropy and walk-regularity

Kyle Kloster, Daniel Král͏̌, Blair D. SullivanLinear 2018 · DOI · arXiv

Abstract

In graph theory, walk-regularity represents a high degree of symmetry where every vertex is involved in the same number of closed walks of any length. It has long been conjectured that a graph achieves maximum walk entropy if and only if it is walk-regular. This paper disproves this notion by constructing a 24-vertex non-regular graph, $H_4$, which exhibits maximum entropy at specific "temperatures." We show that while non-regular graphs can "fake" perfect symmetry, they can only do so at a finite number of parameter values.

Introduction

Walk-regularity is a structural property requiring that for every length $\ell$, the number of closed walks of length $\ell$ starting and ending at vertex $v$ is independent of $v$. This is closely linked to walk entropy, an algebraic measure of vertex centrality. Benzi (2014) and Estrada et al. conjectured that if a graph's walk entropy is maximized at any inverse temperature $\beta > 0$, the graph must be walk-regular. This paper challenges this assumption by exploring whether a non-regular graph can achieve maximum entropy.

The $H_4$ Construction

To test these conjectures, the authors introduced a family of graphs $H_m$. The specific counterexample, $H_4$, consists of 24 vertices. It is built from four isolated vertices and five cliques ($K_4$), connected via a perfect matching.

The H4 graph construction, a 24-vertex counterexample.

The resulting graph is not even degree-regular, containing vertices of both degree 4 and degree 5. Despite this lack of basic regularity, the graph's spectral properties allow for "accidental" maximum entropy.

Spectral Analysis and Methodology

The authors analyzed the adjacency matrix $A_{H_4}$ to derive the diagonal entries of the matrix exponential $e^{\beta A}$, which determines vertex centrality.

Adjacency matrix construction for the H4 graph.

By examining the eigenvalues and eigenvectors, the researchers proved that the centrality functions for different vertex types must cross at specific values of $\beta$. At these crossing points, the entropy function reaches its theoretical maximum, $\log 24$, making all vertices appear identical in terms of walk-based centrality.

Key Results and Insights

The primary contribution of this work is the formal disproof of conjectures by Benzi and Estrada et al. The existence of $H_4$ demonstrates that maximum walk entropy does not imply walk-regularity or even degree-regularity.

Numerical analysis identifies two such "Goldilocks" points for $H_4$ at $\beta \approx 0.499$ and $\beta \approx 1.912$. The authors further established a Classification Theorem: while "fake" symmetries exist, they are rare. For any non-walk-regular graph, there are at most a finite number of $\beta$ values that maximize entropy. Consequently, a randomly chosen $\beta$ will almost certainly distinguish between walk-regular and non-walk-regular graphs.

Conclusion and Future Directions

This research clarifies the boundaries between algebraic graph properties and information-theoretic measures. Future work remains to determine if maximum entropy can occur at rational values of $\beta$ and to prove the conjecture that the number of such accidental maximums is bounded by $n_G - 1$.

Summary updated

BibTeX
@inproceedings{kloster2018walk,
  author = {Kyle Kloster and Daniel Král͏̌ and Blair D. Sullivan},
  title = {{Walk entropy and walk-regularity}},
  booktitle = {Linear},
  year = {2018},
  doi = {10.1016/j.laa.2018.02.009},
}
Figure