Random graph models and their applications
Thomas Vallier
Centre for Mathematical Sciences
Mathematical Statistics
Lund University
2008
ISBN 9789162873783
LUTFMA10282007

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








