RANDOM GRAPHS WITH A GIVEN DEGREE SEQUENCE

• 成果类型: Article
• 署名作者: Chatterjee, Sourav; Diaconis, Persi; Sly, Allan
• 署名单位: New York University; Stanford University; Microsoft
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10-AAP728
• 发表日期: 2011
• 页码: 1400-1435
• 关键词: p-regression parameters; asymptotic-behavior; M-ESTIMATORS; number; LIMITS; tends; p2/n; sums

摘要

Large graphs are sometimes studied through their degree sequences (power law or regular graphs). We study graphs that are uniformly chosen with a given degree sequence. Under mild conditions, it is shown that sequences of such graphs have graph limits in the sense of Lovasz and Szegedy with identifiable limits. This allows simple determination of other features such as the number of triangles. The argument proceeds by studying a natural exponential model having the degree sequence as a sufficient statistic. The maximum likelihood estimate (MLE) of the parameters is shown to be unique and consistent with high probability. Thus n parameters can be consistently estimated based on a sample of size one. A fast, provably convergent, algorithm for the MLE is derived. These ingredients combine to prove the graph limit theorem. Along the way, a continuous version of the Erdos-Gallai characterization of degree sequences is derived.