There are various network descriptors for the understanding of complex networks. A major theme in complex networks is to understand the relations between network descriptors and their connection to the networks’ function. This is a daunting task because of a large number of quantitative measures and each one typically capturing only a particular aspect of the network.

The aim of this talk is to rigorously connect several network descriptors and concepts using mathematical tools.

The central notion of our talk is entropy. Entropy plays a fundamental role in many areas of the physical sciences in quantifying disorder and complexity. Entropy is also a particularly relevant notion for studying complex systems and networks. Entropy is also closely related to the spectral radius (largest eigenvalue) of the graphs’ adjacency matrix. Another central player of our talk, which at first sight seems unrelated to the concept of entropy, is the so-called Randić index, introduced in the 1970s to study chemical compounds. We will see that the topological entropy is bounded from below by the Randić index. Finally, the Randić index brings us back to real-world networks. In social networks vertices with high degree are often adjacent to other high-degree vertices, a tendency referred to as assortative mixing or assortativity. We will see that Randić index and assortativity come to the same thing in different areas.

We finish our talk with a fundamental hierarchical structure from computer science so-called breadth-first search ordering with decreasing degrees that characterized maximization of all these notions.

This is a joint work with Fatihcan Atay, Bilkent University, Ankara.