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.