Random graph models and their applications

Thomas Vallier

Research output: ThesisDoctoral Thesis (compilation)

981 Downloads (Pure)

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 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.
Original languageEnglish
QualificationDoctor
Awarding Institution
  • Mathematical Statistics
Supervisors/Advisors
  • Turova, Tatyana, Supervisor
Award date2008 Feb 1
Publisher
ISBN (Print)978-91-628-7378-3
Publication statusPublished - 2007

Bibliographical note

Defence details

Date: 2008-02-01
Time: 09:15
Place: Room MH:B, Matematikcentrum, Sölvegatan 18, Lund University Faculty of Engineering.

External reviewer(s)

Name: Janson, Svante
Title: professor
Affiliation: Matematiska institutionen Uppsala Universitet, Uppsala.

---

Subject classification (UKÄ)

  • Probability Theory and Statistics

Free keywords

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

Fingerprint

Dive into the research topics of 'Random graph models and their applications'. Together they form a unique fingerprint.

Cite this