Hector Zenil, Narsis A. Kiani and Jesper Tegner: Graph spectra through network complexity measures

We introduce concepts and tools at the intersection of information theory and network biology. We show that Shannon's information entropy, Kolmogorov complexity and algorithmic probability quantify different aspects of synthetic and biological networks at the intersection of local  and global pattern detection, including, the detection of the connectivity phase transition leading to the emergence of giant components in Erdos-Renyi random graphs. We will talk about theoretical and numerical approximations of entropy, algorithmic probability and Kolmogorov complexity for different types of graphs characterizing their variant and invariant properties. We introduce formal definitions of complexity for both labelled and unlabeled graphs and we show that the Kolmogorov complexity of a labelled graph is a good approximation of the Kolmogorov complexity of the unlabeled graph. Then we undertake an extensive numerical investigation of the graph spectra of thousands regular graphs, a set of random Erdos-Renyi graphs, and of complex networks by using a novel conceptual information theoretic tool to find informative Eigenvalues. Our objective in so doing is to contribute to an understanding of the meaning of the Eigenvalues of a graph relative to its topological and information theoretic properties.