On sparsity, power-law and clustering properties of graphex processes

Abstract

This paper investigates properties of the class of graphs based on exchangeable point processes. We provide asymptotic expressions for the number of edges, number of nodes and degree distributions, identifying four regimes: (i) a dense regime, (ii) a sparse almost dense regime, (iii) a sparse regime with power-law behaviour, and (iv) an almost extremely sparse regime. We show that under mild assumptions, both the global and local clustering coefficients converge to constants which may or may not be the same. We also derive a central limit theorem for the number of nodes. Finally, we propose a class of models within this framework where one can separately control the latent structure and the global sparsity/power-law properties of the graph.

References in corpus (8)

• Graph limits and exchangeable random graphs
• The method of moments and degree distributions for network models
• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• Multifractal Network Generator
• Sampling perspectives on sparse exchangeable graphs
• On sparsity, power-law and clustering properties of graphex processes
• Beyond the Chinese Restaurant and Pitman-Yor processes: Statistical Models with Double Power-law Behavior
• Graphons and cut metric on sigma-finite measure spaces

Cited by in corpus (6)

• Breaking Consensus in Kinetic Opinion Formation Models on Graphons
• On sparsity, power-law and clustering properties of graphex processes
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Random Function Priors for Correlation Modeling
• Asymptotic Behavior of Common Connections in Sparse Random Networks