Please use this identifier to cite or link to this item:
Title: Random graphs and applications
Author: Parés Palacín, Adrià
Director: Soria de Diego, F. Javier
Keywords: Teoria de grafs
Anàlisi de xarxes (Planificació)
Rutes aleatòries (Matemàtica)
Simulació per ordinador
Graph theory
Network analysis (Planning)
Random walks (Mathematics)
Computer simulation
Issue Date: 30-Jun-2015
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.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2015, Director: F. Javier Soria de Diego
Appears in Collections:Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
memoria.pdfMemòria1.29 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons