An iterative step-function estimator for graphons
Exchangeable graphs arise via a sampling procedure from measurable functions known as graphons. A natural estimation problem is how well we can recover a graphon given a single graph sampled from it. One general framework for estimating a graphon uses step-functions obtained by partitioning the nodes of the graph according to some clustering algorithm. We propose an iterative step-function estimator (ISFE) that, given an initial partition, iteratively clusters nodes based on their edge densities with respect to the previous iteration's partition. We analyze ISFE and demonstrate its performance in comparison with other graphon estimation techniques.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraphon EstimationSimilar Papers 제목 키워드 기반
Modularity maximisation for graphons
Networks are a widely-used tool to investigate the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite size limit of dense networks. The detection of communities or other …
Community DetectionOpen-Ended Question AnsweringPrivacy PreservingLearning Graphons via Structured Gromov-Wasserstein Barycenters
We propose a novel and principled method to learn a nonparametric graph model called graphon, which is defined in an infinite-dimensional space and represents arbitrary-size graphs. Based on the weak regularity lemma fro…
LEMMANonparametric Modeling of Higher-Order Interactions via Hypergraphons
We study statistical and algorithmic aspects of using hypergraphons, that are limits of large hypergraphs, for modeling higher-order interactions. Although hypergraphons are extremely powerful from a modeling perspective…
When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
Block graphons (also called stochastic block models) are an important and widely-studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number …
Graphon EstimationOn the $H$-property for Step-graphons: Residual Case
We investigate the $H$-property for step-graphons. Specifically, we sample graphs $G_n$ on $n$ nodes from a step-graphon and evaluate the probability that $G_n$ has a Hamiltonian decomposition in the asymptotic regime as…