Related papers: Community Detection: Exact Recovery in Weighted Graphs

Community Detection: Exact Recovery in Weighted Graphs

URL: http://arxiv.org/abs/2102.04439v1
Date: Mon, 8 Feb 2021 18:54:29 GMT
Title: Community Detection: Exact Recovery in Weighted Graphs
Authors: Mohammad Esmaeili and Aria Nosratinia
Abstract summary: In community detection, the exact recovery of communities (clusters) has been investigated under the general block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means.
Score: 29.326472933292607
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In community detection, the exact recovery of communities (clusters) has been mainly investigated under the general stochastic block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means. For each case, we introduce a new semi-metric that describes sufficient and necessary conditions of exact recovery. The necessary and sufficient conditions are asymptotically tight. The analysis is also extended to incomplete, fully connected weighted graphs.

Related papers

Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
This paper considers the problem of community detection on multiple potentially correlated graphs from antheoretical perspective. We first put forth a random graph model, called the multi-view information block model (MVSBM), designed to generate correlated graphs on the same set of nodes.
arXiv Detail & Related papers (2024-01-17T13:39:38Z)
Conformal inference for regression on Riemannian Manifolds [49.7719149179179]
We investigate prediction sets for regression scenarios when the response variable, denoted by $Y$, resides in a manifold, and the covariable, denoted by X, lies in Euclidean space. We prove the almost sure convergence of the empirical version of these regions on the manifold to their population counterparts.
arXiv Detail & Related papers (2023-10-12T10:56:25Z)
Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
arXiv Detail & Related papers (2023-08-16T13:10:27Z)
Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables [21.35141858359507]
In practice, community membership does not completely explain the dependency between the edges of an observation graph. We study graphs obeying the block model and censored block model with auxiliary latent variables. We show that exact recovery is possible by semidefinite programming down to the respective maximum likelihood exact recovery threshold.
arXiv Detail & Related papers (2023-01-08T21:09:03Z)
Exact Recovery of Community Detection in dependent Gaussian Mixture Models [5.312472550578279]
We study the community detection problem on a Gaussian mixture model. We prove necessary and sufficient conditions for the exact recovery of the maximum likelihood estimation.
arXiv Detail & Related papers (2022-09-23T14:26:19Z)
Exact Community Recovery in Correlated Stochastic Block Models [6.746400031322727]
We study the problem of learning latent community structure from multiple correlated networks. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. We develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.
arXiv Detail & Related papers (2022-03-29T16:44:38Z)
Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
arXiv Detail & Related papers (2022-02-02T20:11:33Z)
Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
arXiv Detail & Related papers (2021-05-11T03:39:08Z)
Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z)
Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model [20.238057838577248]
We study the problem of community recovery from coarse measurements of a graph. We build on the block model by mathematically formalizing the coarsening process.
arXiv Detail & Related papers (2021-02-25T19:24:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.