Allerton 2015 Paper Abstract


Paper ThA4.2

Zhao, Jun (CMU & ASU/Princeton)

The Absence of Isolated Node in Geometric Random Graphs

Scheduled for presentation during the Regular Session "Sensor Networks I" (ThA4), Thursday, October 1, 2015, 08:50−09:10, Pine

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Sensor Networks, Sensor Networks in Communications, Wireless Communications at Large


One-dimensional geometric random graphs are constructed by distributing $n$ nodes uniformly and independently on a unit interval and then assigning an undirected edge between any two nodes that have a distance at most $r_n$. These graphs have received much interest and been used in various applications including wireless networks. A threshold of $r_n$ for connectivity is known as $r_n^{*} = frac{ln n}{n}$ in the literature. In this paper, we prove that a threshold of $r_n$ for the absence of isolated node is $frac{ln n}{2n}$ (i.e., a half of the threshold $r_n^{*}$). Our result shows there is a curious gap between thresholds of connectivity and the absence of isolated node in one-dimensional geometric random graphs; in particular, when $r_n$ equals $frac{c ln n}{n}$ for a constant $c in (frac{1}{2}, 1)$, a one-dimensional geometric random graph has no isolated node but is not connected. This curious gap in one-dimensional geometric random graphs is in sharp contrast to the prevalent phenomenon in many other random graphs such as two-dimensional geometric random graphs, Erdos-Renyi graphs, and random intersection graphs, all of which in the asymptotic sense become connected as soon as there is no isolated node.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  09:27:53 PST  Terms of use