2009 Probability Seminar - 10

  • Date: 04/15/2009
Shankar Bhamidi (UBC)

University of British Columbia


Branching processes and real world networks


The aim of this talk is to highlight the usefulness of continuous time
branching process theory in understanding refined asymptotics about
various random network models. We shall exhibit their usefulness in two
different contexts:
(1) First passage percolation: Consider a connected network and suppose
each edge in the network has a random positive edge weight.
Understanding the structure and weight of the shortest path between
nodes in the network is one of the most fundamental problems studied in
modern probability theory. In the modern context these problems take an
additional significance with the minimal weight measuring the cost of
sending information while the number of edges on the optimal path
(hopcount) representing the actual time for messages to get between
vertices in the network. In the context of the configuration model of
random networks we shall show how branching processes allow us to find
the limiting distribution of the minimal weight path as well as
establishing a general central limit theorem for the hopcount with
matching means and variances.
(2) Spectral distribution of random trees: Many models of random trees
(including general models embedded in continuous time branching
processes) satisfy a general form of convergence locally to limiting
infinite objects. In this context we find via soft arguments, the
convergence of the spectral distribution of the adjacency matrix to a
limiting (model dependent) non random distribution. For any $\gamma$ we
also find a sufficient condition for there to be a positive mass at
$\gamma$ in the limit.
Joint work with Remco van der Hoftsad, Gerard Hooghiemstra, Steve Evans
and Arnab Sen.


3:00pm-4:00pm, WMAX 216