Nonparametric graphon estimation

2013/09/23 by Patrick J. Wolfe, Sofia C. Olhede, Wolfe, Patrick J. +1 · 23 citations
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Complex Network Analysis Techniques

paper · pdf · doi:10.48550/arxiv.1309.5936

Abstract

We propose a nonparametric framework for the analysis of networks, based on a natural limit object termed a graphon. We prove consistency of graphon estimation under general conditions, giving rates which include the important practical setting of sparse networks. Our results cover dense and sparse stochastic blockmodels with a growing number of classes, under model misspecification. We use profile likelihood methods, and connect our results to approximation theory, nonparametric function estimation, and the theory of graph limits.

Cited by

• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• Optimal link prediction with matrix logistic regression
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Hierarchical Clustering: Objective Functions and Algorithms
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso\n denoising
• A theory of maximum likelihood for weighted infection graphs
• Hypothesis testing for populations of networks
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Network cross-validation by edge sampling
• A Short Note on Upper Bounds for Graph Neural Operator Convergence Rate
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• On the Estimation of Network Complexity: Dimension of Graphons
• A framework for statistical network modeling
• Robustness on Networks
• On clustering network-valued data
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Network Representation Using Graph Root Distributions
• Nonparametric regression for multiple heterogeneous networks
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Classification on Large Networks: A Quantitative Bound via Motifs and\n Graphons
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• On decomposable random graphs

Related

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• When is Nontrivial Estimation Possible for Graphons and Stochastic Block\n Models?
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Private Graphon Estimation for Sparse Graphs
• Oracle inequalities for network models and sparse graphon estimation