Walk entropies on graphs

Ernesto Estrada, José A. de la Peña, Naomichi Hatano

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)
181 Downloads (Pure)


Entropies based on walks on graphs and on their line-graphs are defined. They are based on the summation over diagonal and off-diagonal elements of the thermal Green’s function of a graph also known as the communicability. The walk entropies are strongly related to the walk regularity of graphs and line-graphs. They are not biased by the graph size and have significantly better correlation with the inverse participation ratio of the eigenmodes of the adjacency matrix than other graph entropies. The temperature dependence of the walk entropies is also discussed. In particular, the walk entropy of graphs is shown to be non-monotonic for regular but non-walk-regular graphs in contrast to non-regular graphs.
Original languageEnglish
Pages (from-to)235-244
Number of pages10
JournalLinear Algebra and its Applications
Early online date25 Nov 2013
Publication statusPublished - 15 Feb 2014


  • graph walks
  • walk-regular graphs
  • entropy measures

Fingerprint Dive into the research topics of 'Walk entropies on graphs'. Together they form a unique fingerprint.

Cite this