Randomness and structure in complex networks

How to mathematically describe real-life networks, such as social networks or the World Wide Web, as so-called random graphs? How do particular rules of placing random edges result in graphs that share some of the fundamental empirical properties of real-life networks? This article of Nelly Litvak is based on her lectures of PWN Vakantiecursus 2022.

Complex networks, modeled as random graphs
Many real-life systems are networks. A network is a set of objects connected by some relationship. For example, a railroad is a col-lection of stations connected by rails. In a social network, people are connected by friendships. The Internet is a network of routers connected by wires. In our brain, neurons are connected if they fire together.
A graph is a natural mathematical model for a network of any kind. In a graph, each object is represented as a vertex, and if there is a relationship between two vertices, then there is an edge between them. Undirected edges represent symmetric relations, and we draw them as lines. For example, communications between two Internet routers usually go in both directions. If the relation is not symmetric, we model this using directed edges, and draw them as arrows. For example, if somebody follows you on Twitter, you might not follow back. In Figure 1, we give some examples of networks, directed and undirected.
This article is about how to mathematically describe real-life networks, such as social networks or the World Wide Web, using so-called random graphs. Usually in research, and always in this article, the vertices of a random graph are fixed, while the edges are placed at random. This makes sense because relationships be-tween objects often emerge at random, like friendships in a social network. Also, even if a network is not random, such as the Inter-net, its structure is so complicated that it is often useful to describe it through statistical summaries and model it as a random object. A random graph model is in fact a set of rules, according to which the random edges are chosen. Different rules result in different models with different mathematical properties. For example, in one model, edges between all vertex pairs can be equally likely, while other models assign higher probabilities to some vertex pairs.
In this article, I will tell about several random graph models that are by now well understood, even classical. My goal is to explain how particular rules of placing random edges result in graphs that share some of the fundamental empirical properties of real-life networks. There are many such properties, but I will address four of them, listed in the next section.