What is a complex graph?

Many papers published in recent years show that real-world graphs G(n, m) (n nodes, m 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 Cl, 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 Offoliagonal 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 G(Cmax) has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph n - 1 < m(G(Cmax)) < n(n -1)/2. Interestingly, for some measures (C) over tilde this number scales exactly with the geometric mean of the extremes: m(G((C) over tilde max) = root n/2(n - 1) similar to n(1.5). All graph complexity measures are characterized with the help of different example graphs. For all measures the corresponding time complexity is given. Finally, we discuss the complexity of 33 real-world graphs of different biological, social and economic systems with the six computationally most simple measures (including OdC). The complexities of the real graphs are compared with average complexities of two different random graph versions: complete random graphs (just fixed n, m) and rewired graphs with fixed node degrees. (C) 2008 Elsevier B.V. All rights reserved.