Random Geometric Graphs: Exploring Connectivity and Discrepancy
Delve into the fascinating realm of random geometric graphs through a discussion of key concepts such as connectivity thresholds, discrepancy analysis, and implications on edge conductance and capacity scaling. Explore the intricacies of node placement and connectivity in G(n,r) graphs, shedding light on their distinct characteristics and how they influence information diffusion and hierarchical scaling.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
RANDOM GEOMETRIC GRAPHS Discussion of Markov Lecture of Francois Baccelli Devavrat Shah Laboratory for Information & Decision System Massachusetts Institute of Technology
Random geometric graph G(n,r) Place n node uniformly at random in unit square Connect two nodes that are within distance r r Unit length Unit length
Random geometric graph Quantity of interest: discrepancy How far is G(n,r) from expected node placement At what r does G(n,r) become connected? near ? 1/ n 1/ n
Random geometric graph Quantity of interest: discrepancy How far is G(n,r) from expected node placement At what r does G(n,r) become connected? near ? 1/ n Connectivity threshold (Penrose 97, Gupta-Kumar 00) c n log n Let , then r = + 2 n n 0 if c n n P[G(n, connected] r) + 1 if c n Connectivity discrepancy Additional log n
Random geometric graph Quantity of interest: discrepancy How far is G(n,r) from expected node placement Minimum of total edge-lengths over all perfect matchings L1 grid-matching threshold: (Ajtai-Komlos-Tusnady 80) With high probability, the minimal total length of matching is ( n log n ) Similar to (and implies) connectivity threshold Additional discrepancy log n
Random geometric graph Quantity of interest: discrepancy How far is G(n,r) from expected node placement Minimum of maximum edge-length over all perfect matchings L grid-matching threshold: (Leighton-Shor 86) With high probability, minimal max length over all matchings is log ~ L n max l length 3 4 n 1 4 r ~ log n c n 1 4 log n Further, additional discrepancy of
Why worry about discrepancy ? For r scaling as L grid-matching threshold (say L) G(n,r) contains expected grid as it s sub-graph w.h.p (L) Implications: edge conductance of G(n,r) for r = (L) scales as (1/ n) (ignoring log n term) Hence Capacity scales as (1/ n) (Gupta-Kumar 00) Hierarchical schemes for info. th. scaling (Ozgur et al 06, Niesen et al 08) Monotone graph properties have sharp threshold (Goel-Rai-Krish 06) Mixing time of RW scales (n) (Boyd-Ghosh-Prabhakar-Shah 06) Information diffuses in time ( n) (MoskAoyama-Shah 08) 2L + 1/ n L L 1/ n
Why worry about discrepancy ? For r scaling as L grid-matching threshold (say L) G(n,r) contains expected grid as it s sub-graph w.h.p Implication: n RED, n BLUE points thrown at random in unit square Match a RED point to a BLUE point that is UP-RIGHT Number of unmatched points scale as (n L) ~ ( n) Online bin-packing analysis (Talagrand-Rhee 88) Mean Glivanko-Cantelli convergence (Shor-Yukich 91) Bin-packing with queues (Shah-Tsitsiklis 08)
The ultimate matching conjecture Talagrand 01 proposed the following conjecture Unifies L1 and L threshold results (and more) Throw n RED, n BLUE points at random in unit square (X1i,Y1i) : position of ith RED pt (X2i,Y2i) : position of ith BLUE pt For any 1/ 1+ 1/ 2=2, and some constant C, there exists a matching such that for j =1, 2: n j j j exp C X - Y 2 i (i) log n i
Point process view Poisson process and stochastic geometry Useful, for example understanding Structure of radial spanning trees (cf. Baccelli-Bordenave 07) Behavior of wireless protocols (cf. Baccelli-Blaszczyszyn 10) Hope: resolution of The ultimate matching conjecture (or a variant of it)
