Offdiagonal Complexity: a local approach to estimating graph complexity

While for text strings many complexity measures exist, for a graph (binary, unweighted) still it is unclear how to define complexity: especially if the complexity measure shall discard both regularity and randomness, and if it itself shall be computeable in low order polynomial time. This seems to be an open problem of applied graph theory for which solutions are more prohibitive than intuitively expected. Here I discuss an entropy-type property for the distribution of degree-differences between the nodes [Physica A 375, 365]. While being nonadditive, it goes beyond the network assortativity and shows some of the desired properties: vanishing for regular lattices, taking low values for random graphs, and significantly higher values for scalefree graphs and biological networks. Finally I will survey the strengths and limitations of the existing approaches.