Sparse graphs using exchangeable random measures

作者：Caron Francois^*; Fox Emily B

来源：Journal of the Royal Statistical Society - Series B: Statistical Methodology , 2017, 79(5): 1295-1366.

DOI：10.1111/rssb.12219

• Exchangeability
• Generalized gamma process
• Levy measure
• Point process
• Random graphs

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.

• 出版日期2017-11