Department of Mathematics
Indian Institute of Science
Bangalore 560 012
SEMINAR
Speaker |
: |
Dr. K. B. Athreya |
Affiliation | : | Iowa State University |
Subject Area |
: |
Mathematics
|
Venue |
: |
Lecture Hall - I, Dept of Mathematics
|
Time |
: |
4.00 pm
|
Date |
: |
August 4,2008 (Monday) |
Title |
: |
Preferential Attachment Random graphs with general weight function and general input sequence. |
Abstract | : |
Consider a network of sites
growing over time such that at step n a newcomer chooses a vertex from the
existing vertices with probability proportional to a function of the degree
of that vertex, i.e., the number of other vertices that this vertex is
connected to. This is called a preferential attachment random graph. The
objects of interest are the growth rates for the growth of the degree for
each vertex with n and the behavior of the empirical distribution of the
degrees. In this talk we will consider three cases: the weight function w(.)
is superlinear, linear, and sublinear. Using recently obtained limit
theorems for the growth rates of a pure birth continuous time Markov chains
and an embedding of the discrete time graph sequence in a sequence of
continuous time pure birth Markov chains, we establish a number of results
for all the three cases. We show that the much discussed power law growth of
the degrees and the power law decay of the limiting degree distribution hold
only in the linear case, i.e., when w(.) is linear.We also discuss the case
of arbitrary input sequence.
|