Graphons, mergeons, and so on!
In this work we develop a theory of hierarchical clustering for graphs. Our modeling assumption is that graphs are sampled from a graphon, which is a powerful and general model for generating graphs and analyzing large networks. Graphons are a far richer class of graph models than stochastic blockmodels, the primary setting for recent progress in the statistical theory of graph clustering. We define what it means for an algorithm to produce the "correct" clustering, give sufficient conditions in which a method is statistically consistent, and provide an explicit algorithm satisfying these properties.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
Nonparametric 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…
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 Regularized Graphon Mean-Field Games with Unknown Graphons
We design and analyze reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs). In contrast to previous works that require the precise values of the graphons, we aim to learn the Nash Equilibrium (NE) of th…
Efficient Evolutionary Models with Digraphons
We present two main contributions which help us in leveraging the theory of graphons for modeling evolutionary processes. We show a generative model for digraphons using a finite basis of subgraphs, which is representati…
Learning 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…
LEMMA