What is a complex graph?

Many papers published in recent years show that real-world graphs G(n,m)G(n,m) (nn nodes, mm edges) are more or less “complex” in the sense that different topological features deviate from random graphs. Here we narrow the definition of graph complexity and argue that a complex graph contains many different subgraphs. We present different measures that quantify this complexity, for instance C1eC1e, the relative number of non-isomorphic one-edge-deleted subgraphs (i.e. DECK size). However, because these different subgraph measures are computationally demanding, we also study simpler complexity measures focussing on slightly different aspects of graph complexity. We consider heuristically defined “product measures”, the products of two quantities which are zero in the extreme cases of a path and clique, and “entropy measures” quantifying the diversity of different topological features. The previously defined network/graph complexity measures Medium Articulation and Offdiagonal complexity (OdC) belong to these two classes. We study OdC   measures in some detail and compare it with our new measures. For all measures, the most complex graph GCmax has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph n−1