Back to Search
Start Over
Approximate Discovery of Random Graphs.
- Source :
- Stochastic Algorithms: Foundations & Applications (9783540748700); 2007, p82-92, 11p
- Publication Year :
- 2007
-
Abstract
- In the layered-graph query model of network discovery, a query at a node v of an undirected graph G discovers all edges and non-edges whose endpoints have different distance from v. We study the number of queries at randomly selected nodes that are needed for approximate network discovery in Erdős-Rényi random graphs Gn,p. We show that a constant number of queries is sufficient if p is a constant, while Ω(nα) queries are needed if p = nε/n, for arbitrarily small choices of ε = 3 / (6 ·i + 5) with i ∈ ℕ. Note that α> 0 is a constant depending only on ε. Our proof of the latter result yields also a somewhat surprising result on pairwise distances in random graphs which may be of independent interest: We show that for a random graph Gn,p with p = nε/n, for arbitrarily small choices of ε> 0 as above, in any constant cardinality subset of the nodes the pairwise distances are all identical with high probability. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540748700
- Database :
- Complementary Index
- Journal :
- Stochastic Algorithms: Foundations & Applications (9783540748700)
- Publication Type :
- Book
- Accession number :
- 33176150
- Full Text :
- https://doi.org/10.1007/978-3-540-74871-7_8