Sparse graphs using exchangeable random measures

被引:110
作者
Caron, Francois [1 ]
Fox, Emily B. [2 ]
机构
[1] Univ Oxford, Oxford, England
[2] Univ Washington, Seattle, WA 98195 USA
基金
英国工程与自然科学研究理事会; 美国国家科学基金会;
关键词
Exchangeability; Generalized gamma process; Levy measure; Point process; Random graphs; CONVERGENT SEQUENCES; NETWORK; MODELS; DISTRIBUTIONS; STATISTICS; SIMULATION; INFERENCE; ARRAYS; PRIORS; NOISE;
D O I
10.1111/rssb.12233
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
Statistical network modelling has focused on representing the graph as a discrete structure, namely the adjacency matrix. When assuming exchangeability of this arraywhich can aid in modelling, computations and theoretical analysisthe Aldous-Hoover theorem informs us that the graph is necessarily either dense or empty. We instead consider representing the graph as an exchangeable random measure and appeal to the Kallenberg representation theorem for this object. We explore using completely random measures (CRMs) to define the exchangeable random measure, and we show how our CRM construction enables us to achieve sparse graphs while maintaining the attractive properties of exchangeability. We relate the sparsity of the graph to the Levy measure defining the CRM. For a specific choice of CRM, our graphs can be tuned from dense to sparse on the basis of a single parameter. We present a scalable Hamiltonian Monte Carlo algorithm for posterior inference, which we use to analyse network properties in a range of real data sets, including networks with hundreds of thousands of nodes and millions of edges.
引用
收藏
页码:1295 / 1366
页数:72
相关论文
共 203 条
[21]  
[Anonymous], 2008, REND MAT APPL
[22]  
[Anonymous], 2007, Random Graph Dynamics
[23]  
[Anonymous], 2003, 13 EUROPEAN YOUNG ST
[24]  
[Anonymous], 2001, Cambridge studies in advanced mathematics, DOI DOI 10.1017/CBO9780511814068
[25]  
[Anonymous], 2016, BAYESIAN NONPARAMETR
[26]  
Arbel J., 2017, ASYMPTOTIC IN PRESS
[27]   ON THE BOOTSTRAP OF U-STATISTICS AND V-STATISTICS [J].
ARCONES, MA ;
GINE, E .
ANNALS OF STATISTICS, 1992, 20 (02) :655-674
[28]   A blocked Gibbs sampler for NGG-mixture models via a priori truncation [J].
Argiento, Raffaele ;
Bianchini, Ilaria ;
Guglielmi, Alessandra .
STATISTICS AND COMPUTING, 2016, 26 (03) :641-661
[29]  
Athreya A, 2016, SANKHYA SER A, V78, P1
[30]   de Finetti Priors using Markov chain Monte Carlo computations [J].
Bacallado, Sergio ;
Diaconis, Persi ;
Holmes, Susan .
STATISTICS AND COMPUTING, 2015, 25 (04) :797-808