Computing Subgraph Probability of Random Geometric Graphs with Applications in Quantitative Analysis of Ad Hoc Networks

摘要

Random geometric graphs (RGG) contain vertices whose points are uniformly distributed in a given plane and an edge between two distinct nodes exists when their distance is less than a given positive value. RGGs are appropriate for modeling ad hoc networks consisting of n mobile devices that are independently and uniformly distributed randomly in an area. To the best of our knowledge, this work presents the first paradigm to compute the subgraph probability of RGGs in a systematical way. In contrast to previous asymptotic bounds or approximation, which always assume that the number of nodes in the network tends to infinity, the closed-form formulas we derived herein are fairly accurate and of practical value. Moreover, computing exact subgraph probability in RGGs is shown to be a useful tool for counting the number of induced subgraphs, which explores fairly accurate quantitative property on topology of ad hoc networks.