Advanced

Random graph models and their applications

Vallier, Thomas LU (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... (More)
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 model 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. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • professor Janson, Svante, Matematiska institutionen Uppsala Universitet, Uppsala.
organization
publishing date
type
Thesis
publication status
published
subject
keywords
contact process, phase transition, classical random graphs, degree sequence, preferential attachment, percolation, random graphs
pages
140 pages
publisher
Mathematical Statistics, Centre for Mathematical Sciences, Lund University
defense location
Room MH:B, Matematikcentrum, Sölvegatan 18, Lund University Faculty of Engineering.
defense date
2008-02-01 09:15
ISBN
978-91-628-7378-3
language
English
LU publication?
yes
id
6b060084-70bc-4a8c-82e1-3ecbfeb0884e (old id 835268)
date added to LUP
2008-01-09 10:27:10
date last changed
2016-09-19 08:45:06
@phdthesis{6b060084-70bc-4a8c-82e1-3ecbfeb0884e,
  abstract     = {This thesis explores different models of random graphs. The first part treats a change from the preferential attachment model<br/><br>
where the network incorporates new vertices and attach them<br/><br>
preferentially to the previous vertices with a large number of<br/><br>
connections. We introduce on top of this model the deletion of the<br/><br>
oldest connections in the system and discuss the impact on the<br/><br>
degree of the vertices. We show that the structure of the resulting graph doesn't<br/><br>
resemble the structure of the former graph.<br/><br>
<br/><br>
The second and third part of the thesis concern the phase transition<br/><br>
in a model combining the classical random graphs model and the bond<br/><br>
percolation model. We describe the phase diagram on the different<br/><br>
parameters inherited from percolation model and classical random<br/><br>
graphs. We show that the phase transition is of second order similarly to the<br/><br>
classical random graphs and give the size of the largest connected<br/><br>
component above the phase transition.<br/><br>
<br/><br>
In the last part, we study the spread of activation on the classical<br/><br>
random graph model. We give, for a given probability of connection of<br/><br>
the vertices, conditions on the original set of activated vertices<br/><br>
under which the activation diffuses through the graph and conversely,<br/><br>
conditions under which the activation stops before spreading to a<br/><br>
positive part of the graph.},
  author       = {Vallier, Thomas},
  isbn         = {978-91-628-7378-3},
  keyword      = {contact process,phase transition,classical random graphs,degree sequence,preferential attachment,percolation,random graphs},
  language     = {eng},
  pages        = {140},
  publisher    = {Mathematical Statistics, Centre for Mathematical Sciences, Lund University},
  school       = {Lund University},
  title        = {Random graph models and their applications},
  year         = {2007},
}