Random graphs and applications

Abstract

Graph theory has been a wide area of study of discrete mathematics since the publication of the K ̈onigsberg bridge solution by Leonard Euler in 1736. Despite its historical background and very exciting developments since its birth, graph theory was unable to prove useful when studying complex networks. These networks contain large amounts of vertices and edges, and the sheer quantity of data that has to be handled makes the classical approach not optimal at best and impossible in most cases. The last decade has seen an uprising of the random network theory, which attempts to study the topology of these complex networks via a statistical approach. This theory has proven very successful at modeling these networks, particularly when applied to the degree distribution of the vertices of the graphs. This manuscript will attempt to summarize the two most important models from a historical point of view. First, we will describe the model created by Paul Erdös and Alfréd Rényi in 1960, which is considered one of the first to attempt to describe these networks. The second model was introduced by Lázlo Barabási and Réka Albert in the late 1990s. This model can be considered the spiritual successor of the Erdös-Rényi model, while expanding it with some additional properties that were not considered at first. It is particularly important because it motivates a new wave of scientific study about complex network due to essentially two factors. First, there was more data available on complex networks compared to the times when the Erdös-Rényi model was proposed. Lastly, computers were now capable of handling the calculations required to model these networks and were available to the majority of the scientific community, which made the topic much more accessible for new research to be conducted.