Complexity and Complex Networks

We’re now going to dive into the concept of complex networks and complexity, and how they’re different from the simple random graph models.

The limitations of the random graph model

A complex network is a graph that models a complex system and contains topological characteristics and structures that we can’t find in classical random graphs.

For example, the random graph generated by the Erdős–Rényi model above isn’t considered a complex network. This is why the model doesn’t create structures commonly found in real-world complex networks, such as:

• Hubs: These are the nodes that have way more connections than the rest of the network, being responsible for reducing the distance traveled to each part of the network

• Clusters: These are groups of nodes that become densely connected between themselves and sparsely connected to the rest of the network. This is also called community structure.

The image below, for example, shows a complex network with a community structure.

The random graph model assumes all edges are independent, so we’re never going to see this kind of community structure in it. This limitation is serious because most real-world phenomena that we’re interested in studying, require these more complex structures. ...