Hide search tips...
• The wildcard * means "match zero or more characters" and may only be used at the end of a word.
• The wildcard ? means "match exactly one character" and cannot be used as the first character of a word.
• To search for a phrase in a document, use double-quotes to delimit your search terms -- for example, "search phrase".

Linda Casals lindac at dimacs.rutgers.edu
Mon Feb 28 08:50:46 EST 2011

*************REMINDER***************REMINDER**********REMINDER*********

*****************************************************************

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.