A complex network refers in the context of network theory to a network (graph) that has certain non-trivial topological features that do not occur in simple networks.
Most social, biological, and technological networks (as well as certain network-driven phenomena) can be considered complex by virtue of non-trivial topological structure (see e.g., social network, computer network, neural network, epidemiology). Such non-trivial features include: a heavy-tail in the degree distribution; a high clustering coefficient; assortativity or disassortativity among vertices; community structure at many scales; and evidence of a hierarchical structure.
In contrast, simple networks have none of these properties, and are typically represented by graphs such as a lattice or a random graph, which exhibit a high similarity no matter what part is examined.
Are the most popular complex network models too simple? Some, like the small-world model, have the property the more broadly applicable they are in terms of binary features (clustering, shorter distances that expected at random) the less informative they are for real world networks. Another is that the more stylized they are, like preferential attachment or the scale-free model, the more ambiguous is the interpretation of what actual processes might have generated similar outcomes.
In The complex network problem Doug white explores the questions posted by the generative feedback network or Social-circles network model, which generates heavy-tails in simulated degree distributions, greater than random clustering coefficients, community and hierarchical structure, complex routing structures, and, waiting to be explored, possibly many other features of complex networks.