HP Labs Technical Reports
Click here for full text:
Compound Poisson Approximations of Subgraph Counts in Random Graphs
Keyword(s):Poisson approximation; random graphs; Stein's method
Abstract:Poisson approximations for the counts of a given subgraph in large random graphs were accomplished using Stein's method by Barbour and others. Compound Poisson approximation results, on the other hand, have not appeared, at least partly because of the lack of a suitable coupling. We address that problem by introducing the concept of cluster determining pairs, leading to a useful coupling for a large class of subgraphs we call local. We find bounds on the compound Poisson approximation of counts of local subgraphs in large random graphs.
Back to Index