Optimal Estimation in Mixed-Membership Stochastic Block Models

• URL: http://arxiv.org/abs/2307.14530v1
• Date: Wed, 26 Jul 2023 22:27:08 GMT
• Title: Optimal Estimation in Mixed-Membership Stochastic Block Models
• Authors: Fedor Noskov and Maxim Panov
• Abstract summary: We consider the Mixed-Membership Block Model (MMSB) first proposed by Airoldi et al. This paper is to reconstruct relations between communities given an observed network. Theoretical results are proved under fairly general conditions on the considered model.
• Score: 2.474391692385924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community detection is one of the most critical problems in modern network science. Its applications can be found in various fields, from protein modeling to social network analysis. Recently, many papers appeared studying the problem of overlapping community detection, where each node of a network may belong to several communities. In this work, we consider Mixed-Membership Stochastic Block Model (MMSB) first proposed by Airoldi et al. (2008). MMSB provides quite a general setting for modeling overlapping community structure in graphs. The central question of this paper is to reconstruct relations between communities given an observed network. We compare different approaches and establish the minimax lower bound on the estimation error. Then, we propose a new estimator that matches this lower bound. Theoretical results are proved under fairly general conditions on the considered model. Finally, we illustrate the theory in a series of experiments.

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)
• Distributed Bayesian Learning of Dynamic States [65.7870637855531]
  The proposed algorithm is a distributed Bayesian filtering task for finite-state hidden Markov models. It can be used for sequential state estimation, as well as for modeling opinion formation over social networks under dynamic environments.
  arXiv  Detail & Related papers  (2022-12-05T19:40:17Z)
• Federated Learning Aggregation: New Robust Algorithms with Guarantees [63.96013144017572]
  Federated learning has been recently proposed for distributed model training at the edge. This paper presents a complete general mathematical convergence analysis to evaluate aggregation strategies in a federated learning framework. We derive novel aggregation algorithms which are able to modify their model architecture by differentiating client contributions according to the value of their losses.
  arXiv  Detail & Related papers  (2022-05-22T16:37:53Z)
• Bayesian community detection for networks with covariates [16.230648949593153]
  "Community detection" has arguably received the most attention in the scientific community. We propose a block model with a co-dependent random partition prior. Our model has the ability to learn the number of the communities via posterior inference without having to assume it to be known.
  arXiv  Detail & Related papers  (2022-03-04T01:58:35Z)
• Mixed membership distribution-free model [0.4972323953932129]
  We consider the problem of community detection in overlapping weighted networks, where nodes can belong to multiple communities and edge weights can be finite real numbers. To model such complex networks, we propose a general framework - the mixed membership distribution-free (MMDF) model. We use an efficient spectral algorithm with a theoretical guarantee of convergence rate to estimate community memberships under the model.
  arXiv  Detail & Related papers  (2021-12-04T18:21:02Z)
• A useful criterion on studying consistent estimation in community detection [0.0]
  We use separation condition for a standard network and sharp threshold of Erd"os-R'enyi random graph to study consistent estimation. We find some inconsistent phenomena on separation condition and sharp threshold in community detection. Our results enjoy smaller error rates, lesser dependence on the number of communities, weaker requirements on network sparsity.
  arXiv  Detail & Related papers  (2021-09-30T09:27:48Z)
• Community models for networks observed through edge nominations [6.442024233731203]
  Communities are a common and widely studied structure in networks, typically under the assumption that the network is fully and correctly observed. We propose a general model for a class of network sampling mechanisms based on recording edges via querying nodes. We show community detection can be performed by spectral clustering under this general class of models.
  arXiv  Detail & Related papers  (2020-08-09T04:53:13Z)
• A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network Representation Learning [52.83948119677194]
  We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning. Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions. We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
  arXiv  Detail & Related papers  (2020-07-19T22:50:20Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition [12.244594819580831]
  We study the problem of community detection in multi-layer networks, where pairs of nodes can be related in multiple modalities. We propose a tensor-based algorithm (TWIST) to reveal both global/local memberships of nodes, and memberships of layers.
  arXiv  Detail & Related papers  (2020-02-10T06:19:50Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.