I am just a bit curious about the following question. Following wiki, the definition of "complex networks" goes as follows: " Most social, biological, and technological networks display substantial non-trivial topological features, with patterns of connection between their elements that are neither purely regular nor purely random. "
So, my question is, why emphasize " neither purely regular nor purely random " ?
On
One reason might be the way we study these complex networks. Consider the Erdos Renyi random graph model. We can prove lots of things about the model but it does not capture any real world behaviour so it is useless to do so. On the other hand, we have also developed techniques for more specialized network structures such as some small world models, scale free models, etc. The real world behavior that we see lies somewhere in between the results of randomness and highly structured.
A good paper on this is the Structure and Function of Complex Networks by M. E. J. Newman available here (the journal version is in SIAM Review).
A purely random graph would be something like an Erdos-Renyi(p) graph - connections made at random between pairs of nodes i.i.d. with probability p. The structure is similar at each node (at least on average). There is a lot of structure, such as formation of certain cluster sizes, how many links people make (power law distribution, or something) and what not.
If you look at say the graphs of the IPV6 internet available through CAIDA, and compare their properties (such as degree distributions) to random graphs (say, Erdos-Renyi), you will see significant differences in the distribution. There is structure, like clustering around certain nodes.