On the mixing time of geographical threshold graphs

DOI10.1016/J.DISC.2011.08.003zbMATH Open1238.05242arXiv1109.4311OpenAlexW2107341492MaRDI QIDQ409397FDOQ409397

Andrew Beveridge, Milan Bradonjić

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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=(logn/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 $dgeq2$. If the weight distribution function decays with $mathbbP[Wgeqx]=O(1/x^{d+u})$ for an arbitrarily small constant $u>0$ then the mixing time of GTG is $mixbound$. This matches the known mixing bounds for the $d$-dimensional RGG.

Full work available at URL: https://arxiv.org/abs/1109.4311

zbMATH Keywords

mixing timerandom geometric graphsgeographical threshold graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Random Geometric Graphs
• Emergence of Scaling in Random Networks
• The Markov chain Monte Carlo revolution
• The degree sequence of a scale-free random graph process
• A note on an inequality involving the normal distribution
• A random graph model for massive graphs
• Mixing time of exponential random graphs
• On the cover time and mixing time of random geometric graphs
• The Structure of Geographical Threshold Graphs
• A Dynamic Model for On-Line Social Networks
• A Geometric Preferential Attachment Model of Networks II
• A Spatial Web Graph Model with Local Influence Regions
• Giant Component and Connectivity in Geographical Threshold Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On the mixing time of geographical threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409397)