Walk entropies in graphs

Entropies based on walks in graphs and in their line graphs are defined. They are based on the summation over diagonal and off-diagonal elements of the exponential of the adjacency matrix, known as the network 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. A homogeneous weighting of the edges of the graph is used to simulate the effects of the 'temperature' over the entropies defined. In particular, the walk entropy of graphs is non-monotonic for regular but non-walk-regular graphs in contrast to non-regular graphs.