Navigation on a Poisson point process

• 成果类型: Article
• 署名作者: Bordenave, Charles
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/07-AAP472
• 发表日期: 2008
• 页码: 708-746
• 关键词: small-world networks; convergence-rates; spanning-trees; large numbers; limit theory; MODEL

摘要

On a locally finite point set, a navigation defines a path through the point set from one point to another. The set of paths leading to a given point defines a tree known as the navigation tree. In this article, we analyze the properties of the navigation tree when the point set is a Poisson point process on R-d. We examine the local weak convergence of the navigation tree, the asymptotic average of a functional along a path, the shape of the navigation tree and its topological ends. We illustrate our work in the small-world graphs where new results are established.