Grafi casuali e modelli generativi del web

The thesis aims to provide a study on graphs and generative web models, first of all providing basic notions on oriented and non-oriented graphs, and some preliminary and interesting results (for example the Handshaking Lemma), and then delve deeper into the metrics of the graphs and their properties (degree, clustering coefficient, betweenness etc ...). Furthermore, the degree of a graph will be examined particularly in detail, since in the third chapter of the thesis we introduce the definition of probability distribution on the nodes and in the following ones on the asymptotic behavior of the degree distribution; we will also see two famous examples of random graphs: the Erdòs-Renyi model and that of Gilbert, offering a qualitative analysis (distribution of nodes, expected number of nodes, variance, and some other properties). The two final chapters will mainly focus on the scale-free behavior of the web models and the examination of the preferential attachment, uniform attachment models, and the UPA model, which provides for the coexistence of the two previous attachments, weighted on the graph nodes.

La tesi si prefigge di fornire un approfondimento sui grafi cauali e i modelli generativi del web, fornendo in primo luogo delle nozioni di base sui grafi orientati e non, e alcuni risultati preliminari e interessanti (ad esempio l'Handshaking Lemma), per poi addentrarsi nel dettaglio sulle metriche dei grafici e delle loro proprietà (grado, clustering, betweenness etc...). Il grado di un grafo verrà esaminato dettagliatamente, in quanto nel terzo capitolo della tesi si introduce la definizione di distribuzione di probabilità sui nodi e in quelli successivi sul comportamento asintotico della distribuzione del grado; si vedranno inoltre due esempi famosi di grafi casuali: il modello Erdòs-Renyi e quello di Gilbert, offrendone un'analisi qualitativa (distribuzione dei nodi, valore atteso, varianza, e alcune proprietà). I due capitoli finali verteranno principalmente sullo scale-free behavior dei modelli del web e della presa in esame dei modelli di preferential attachment, uniform attachment, e il modello UPA, che prevede la compresenza dei due tipi di attaccamento precedenti sui nodi del grafo.