Sparse graphs using exchangeable random measures.

Area of Science:

• Statistical Network Modeling
• Probability Theory
• Machine Learning

Background:

• Traditional network models represent graphs as adjacency matrices, often leading to dense or empty structures under exchangeability assumptions (Aldous-Hoover theorem).
• Existing methods struggle to model sparse yet exchangeable networks, limiting their applicability.
• Exchangeability is a desirable property for simplifying statistical analysis and theoretical understanding of networks.

Purpose of the Study:

• To develop a novel statistical network model capable of generating sparse exchangeable random graphs.
• To leverage random measures and the Kallenberg representation theorem for flexible graph construction.
• To enable tunable sparsity in network models using a single parameter.

Main Methods:

• Representing graphs as exchangeable random measures, utilizing completely random measures (CRMs).
• Connecting graph sparsity to the Lévy measure defining the CRM.
• Developing a scalable Hamiltonian Monte Carlo algorithm for posterior inference.

Main Results:

• A CRM construction that generates sparse exchangeable random graphs.
• Demonstrated ability to tune graph density from dense to sparse using a single parameter.
• Successful application of the model to analyze large-scale real-world network data.

Conclusions:

• The proposed random measure approach effectively models sparse exchangeable networks, overcoming limitations of adjacency matrix representations.
• The method offers a flexible and scalable framework for network analysis, applicable to large datasets.
• This work provides a new tool for understanding complex network structures across various domains.