On the Mixing Time of Geographical Threshold Graphs

Details On the Mixing Time of Geographical Threshold Graphs On the Mixing Time of Geographical Threshold Graphs

2011-09-20

arxiv.org/abs/1109.4311v1

Mathematics

Probability

Scientific paper

10.1016/j.disc.2011.08.003

We study the mixing time of random graphs in the $d$-dimensional toric unit cube $[0,1]^d$ generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights, drawn from some distribution. The connectivity threshold for GTGs is comparable to that of RGGs, essentially corresponding to a connectivity radius of $r=(\log n/n)^{1/d}$. However, the degree distributions at this threshold are quite different: in an RGG the degrees are essentially uniform, while RGGs have heterogeneous degrees that depend upon the weight distribution. Herein, we study the mixing times of random walks on $d$-dimensional GTGs near the connectivity threshold for $d \geq 2$. If the weight distribution function decays with $\mathbb{P}[W \geq x] = O(1/x^{d+\nu})$ for an arbitrarily small constant $\nu>0$ then the mixing time of GTG is $\mixbound$. This matches the known mixing bounds for the $d$-dimensional RGG.

Affiliated with

Also associated with

No associations

Rating

On the Mixing Time of Geographical Threshold Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Mixing Time of Geographical Threshold Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Mixing Time of Geographical Threshold Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147469