Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series- Monday, February 28, 2011

Linda Casals lindac at
Wed Feb 23 10:28:16 EST 2011

DIMACS/CCICADA Interdisciplinary Seminar Series Presents

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

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. 

More information about the Dimacs-ccicada-announce mailing list