Random graph models and their applications

Thomas Vallier

Centre for Mathematical Sciences
Mathematical Statistics
Lund University
2008

ISBN 978-91-628-7378-3
LUTFMA-1028-2007

Abstract:

This thesis explores different models of random graphs. The first part treats a change from the preferential attachment model where the network incorporates new vertices and attach them preferentially to the previous vertices with a large number of connections. We introduce on top of this model the deletion of the oldest connections in the system and discuss the impact on the degree of the vertices. We show that the structure of the resulting graph doesn't resemble the structure of the former graph.

The second and third part of the thesis concern the phase transition in a model combining the classical random graphs model and the bond percolation model. We describe the phase diagram on the different parameters inherited from percolation and classical random graphs. We show that the phase transition is of second order similarly to the classical random graphs and give the size of the largest connected component above the phase transition.

In the last part, we study the spread of activation on the classical random graph model. We give, for a given probability of connection of the vertices, conditions on the original set of activated vertices under which the activation diffuses through the graph and conversely, conditions under which the activation stops before spreading to a positive part of the graph.

Key words:

random graphs, percolation, preferential attachment, degree sequence, classical random graphs, phase transition, contact process