### Interdisciplinary Seminar Series

Title: On the Mixing Time of Geographical Threshold Graphs

Speaker: **Milan Bradonjic**, Los Alamos National Laboratory

Date: Monday, February 28, 2011 12:00 - 1:00 pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The Geographical Threshold Graph (GTG) model is a new structured
random generative model, which is a node-weighted generalization of
Random Geometric Graphs (RGGs) and more accurately characterizes large
scale real-world networks. Nodes in GTG are distributed in a Euclidean
space, and edges are assigned according to a threshold function
involving the distance between nodes and randomly chosen node weights.
The previous studies showed how the structural properties in GTG, such
as connectedness, diameter, existence of the giant component,
clustering coefficient, and chromatic number relate to the threshold
value and node weight distribution.

In this talk, we present a recent study on the mixing time of GTGs.
The mixing time plays an important role not only in theory, but also
in applications such as epidemic spreading. We specifically study the
mixing times of random walks on $d$-dimensional GTGs near the
connectivity threshold for $d \geq 2$. In the regime when the weight
distribution function decays with $Pr[W \geq x] = O(1/x^{d+\nu})$ for
an arbitrarily small constant $\nu>0$, the mixing time of GTG is
$O(n^{2/d} (\log n)^{(d-2)/d})$. This matches the known mixing bounds
for the $d$-dimensional RGG.

This is joint work with Andrew Beveridge.

DIMACS/CCICADA Interdisciplinary Series, Spring 2011