Graph entropy, degree assortativity, and hierarchical structures in networks

Abstract

We connect several notions relating the structural and dynamical properties of a graph. Among them are the topological entropy coming from the vertex shift, which is related to the spectral radius of the graph's adjacency matrix, the Randić index, and the degree assortativity. We show that, among all connected graphs with the same degree sequence, the graph having maximum entropy is characterized by a hierarchical structure; namely, it satisfies a breadth-first search ordering with decreasing degrees (BFD-ordering for short). Consequently, the maximum-entropy graph necessarily has high degree assortativity; furthermore, for such a graph the degree centrality and eigenvector centrality coincide. Moreover, the notion of assortativity is related to the general Randić index. We prove that the graph that maximizes the Randić index satisfies a BFD-ordering. For trees, the converse holds as well. We also define a normalized Randić function and show that its maximum value equals the difference of Shannon entropies of two probability distributions defined on the edges and vertices of the graph based on degree correlations.