Improved community detection in heterogeneous SBM with side information.
problem Misclassification in community detection with noisy labels.
method Optimal weighted message passing and minimum energy flow.
result Optimal weighting improves misclassification rate in heterogeneous SBM.
CN-SBM clusters cancer samples and regions based on copy number variants.
problem Clonal evolution in cancer monitored by noisy copy number variants.
method Probabilistic framework using bipartite categorical block model.
result Improved model fit and clinically relevant subtypes identified.
Develops a model to detect shared communities in non-aligned graphs.
problem Clustering and community detection in non-aligned graphs with heterogeneous populations.
method Joint Stochastic Blockmodel (Joint SBM) and efficient spectral clustering.
result The joint model better estimates communities compared to separate SBMs on individual graphs.
The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in recovering communities in the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental information theoretic and computational l…
The stochastic block model (SBM) is a popular framework for studying community detection in networks. This model is limited by the assumption that all nodes in the same community are statistically equivalent and have equal expected degrees. The degree-corrected stochastic block model (DCSBM) is a natural extension of S…
Improved community detection in sparse graphs using Bethe-Hessian matrix.
problem Community detection in sparse heterogeneous graphs.
method Spectral clustering based on the Bethe-Hessian matrix Hr for degree-corrected stochastic block models. result Clustering is insensitive to degree heterogeneity for r=ζ. A new model corrects SBM's bias for power-law degree networks.
problem SBM's incapability to handle power-law degree distributions.
method Introducing degree decay variables to encode varying degree distributions.
result PLD-SBM approximately preserves the scale-free feature in real networks and corrects SBM's bias.
We consider community detection in Degree-Corrected Stochastic Block Models (DC-SBM). We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block-membership of all but a vanishing fraction of nodes, in the regime where the lowes…
New algorithms cluster nodes in SBM graphs faster and more accurately.
problem Efficiently clustering nodes in graphs generated from SBM models.
method Inspired by Lloyd's algorithm, proposes model-free clustering methods for SBM graphs.
result Consistent estimation of node clusters and parameters in SBM graphs.
VEC-SBM detects communities using side information like texts and images.
problem Community detection in social networks with side information.
method Proposes a novel algorithm based on iterative refinement techniques.
result Optimally recovers latent communities with side information.
A new SBM for bipartite networks improves community detection in noisy data.
problem Community detection in bipartite networks with stochastic blockmodels.
method Bayesian nonparametric formulation of SBM for bipartite networks, algorithm to find communities efficiently.
result Improves community detection results over general SBMs, especially in noisy data.
Combines SBMs and graph neural nets for graph embeddings.
problem Discovering community structure and link prediction on graphs.
method Sparse variational autoencoder integrating SBMs and graph neural nets.
result Encouraging link prediction results with interpretable latent structure.
Proposes a method for evaluating multiple dimensions of organizational effectiveness using DEA.
problem Evaluating multiple dimensions of organizational effectiveness in large data sets.
method Introduces two regularized DEA models (SBM and GP-SBM) to estimate both dimension-specific and aggregate efficiency scores.
result Demonstrates improved efficiency and validity compared to conventional methods.
The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. W…
The stochastic block model accurately describes most empirical networks but struggles with large diameter and slow-mixing networks.
problem Assessing the quality of fit of the stochastic block model for empirical networks.
method Posterior predictive model checking using network descriptors.
result The stochastic block model can accurately describe most empirical networks but struggles with large diameter and slow-mixing networks.
SBMs learn manifold-like structures by mixing samples with a non-conservative field.
problem How SBMs learn data distributions on low-dimensional manifolds.
method Investigating linear approximations and subspaces of local feature vectors during diffusion.
result SBMs mix samples by a non-conservative field within the manifold, maintaining manifold-like structure.
Enhances SBM with continuous attributes for better network analysis.
problem Community detection in networks with multiple continuous attributes.
method Augmented stochastic block model with multivariate Gaussian parameters.
result Satisfactory performance in link prediction and collaborative filtering tasks.
Paper characterizes optimal graph clustering limits under a new model.
problem Graph clustering under varying edge density signals.
method Introduced Popularity-Adjusted Block Model (PABM) to address SBM and DCBM limitations.
result Cluster recovery possible even when edge density signals vanish, highlighting local connectivity differences.
This paper tackles exact recovery of clusters in a stochastic Ising model on a SBM graph.
problem Recovering clusters in a stochastic Ising model on a SBM graph.
method Proposes a Stochastic Ising Block Model (SIBM) and establishes a sharp threshold for exact recovery.
result Sharp threshold m∗ for exact recovery of clusters in SIBM, with O(n) time complexity for m≥m∗. Smoothing graphons improve link prediction in Bayesian SBM without increasing computational complexity.
problem Accurate modeling of exchangeable relational data with flexible and computationally efficient graphons.
method Introducing smoothing procedures to piecewise-constant graphons to create smoothing graphons, which allow continuous intensity values for relations.
result Smoothing graphons improve AUC and precision for link prediction in real-world data sets.
SubSearch detects graph outliers and estimates SBM parameters robustly.
problem Real-world graphs often deviate from ideal SBM assumptions.
method Subgraph search to find subgraphs that align with SBM assumptions.
result SubSearch accurately estimates SBM parameters and detects outliers.
DeepWalk embeddings converge on SBM graphs, recovering cluster structure.
problem Theoretical guarantees for DeepWalk embeddings on complex graphs.
method Solving a nonconvex optimization problem using random walks.
result DeepWalk embeddings on SBM graphs recover cluster structure with high probability.
A new SBM for non-negative zero-inflated edge weights in networks.
problem Modeling international trading networks with non-negative zero-inflated edge weights.
method Restricted Tweedie distribution and nodal information accounting.
result Efficient two-step algorithm for estimating covariate effects.
New method for community detection in sparse directed SBMs with exact recovery guarantees.
problem Exact recovery in sparse directed SBMs, especially with growing communities.
method Two-stage procedure: neighborhood-smoothing followed by K-means clustering. result Exact recovery of all community labels with probability tending to one under mild sparsity and separation conditions.
Novel active learning detects network nodes for community detection.
problem Detecting community structure in networks.
method Maximal Expected Model Change (MEMC) criterion for querying network nodes.
result MEMC detects nodes that maximize community assignment likelihood changes.
New model improves community detection in networks with strong assortativity.
problem Classic SBMs fail to recover assortative communities in networks with reduced information.
method Introduced a constrained SBM with strong assortativity constraints and efficient algorithms.
result Significant boost in community recovery capabilities, especially close to information-theoretic threshold.
Unified algorithm for latent patterns in SBM and SWM models.
problem Invalid analysis due to misspecified models in graph analysis.
method Combining kernel learning, spectral graph theory, and dimensionality reduction.
result First statistically sound polynomial-time algorithm for latent patterns.
A new model adjusts for covariates in community detection.
problem Community detection in networks with covariate information.
method Pairwise covariates-adjusted stochastic block model (PCABM) with spectral clustering.
result Consistent community detection and coefficient estimates under sparsity conditions.
Paper introduces a new edge exchangeable block model for complex networks.
problem Limitations of the stochastic block model in analyzing complex networks.
method Develops a Bayesian nonparametric edge exchangeable block model.
result The new model outperforms state-of-the-art SBMs for link prediction.
Proposes a Nested Block Model to unify various network block models.
problem Lack of nested structure and differing parameter complexity among block models.
method Formulates a hierarchy of block models (NBM) that includes SBM, DCBM, and PABM as special cases.
result Allows clustering and estimation without preliminary testing, simplifying model selection.
New spectral clustering method improves community detection in sparse networks.
problem Community detection in sparse networks using spectral clustering.
method Data-driven regularization and novel spectral truncation for adjacency matrix.
result Consistency results for community detection in general SBM and beyond.
Paper shows SBMs are like surface tension problems, aiding network clustering.
problem Cluster network nodes into communities with dense internal connections.
method Used maximum likelihood estimation and network analogs of surface-tension algorithms.
result Successfully recovered planted community structure in synthetic networks.
A growing number of systems are represented as networks whose architecture conveys significant information and determines many of their properties. Examples of network architecture include modular, bipartite, and core-periphery structures. However inferring the network structure is a non trivial task and can depend som…
A new method for efficient inference and model selection in SBMs using OT.
problem Efficient inference and model selection in stochastic block models.
method Interpreting MLVI as srGW with entropic regularization, then unregularizing for sparse solutions, and adding a sparsity-promoting regularizer.
result The method consistently recovers SBM parameters and selects the number of clusters in finite samples.
New algorithm recovers communities in broader network models.
problem Finding communities in complex networks is challenging.
method Spectral clustering on Preference Frame Models with Normalized Laplacian.
result Spectral clustering works on broader network models with similar guarantees.
We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on n nodes, having i.i.d. weights (φu)u=1n (possibly heavy-tailed), partitioned into q≥2 asymptotically equal-sized clusters. The model parameters are two constants a,b>0 and the finite second moment of the weights $Φ^{…
Unified framework detects dynamic community structure in brain networks across individuals.
problem Detecting community structure in functional brain networks across multiple subjects and over time.
method Markov-switching stochastic block model (MSS-SBM) for multilayer brain networks.
result Captures dynamic reconfiguration of modular connectivity in brain networks across different task conditions.
Stochastic block model shows universal applicability to network inference problems.
problem Finding partitions in complex networks that maximize objective functions.
method Showed equivalence of popular algorithms to maximum likelihood formulation of SBM.
result SBM is nearly universal for solving MPE problems.
The stochastic block model (SBM) is a generative model revealing macroscopic structures in graphs. Bayesian methods are used for (i) cluster assignment inference and (ii) model selection for the number of clusters. In this paper, we study the behavior of Bayesian inference in the SBM in the large sample limit. Combinin…
Efficient algorithm for matching graphs with community structure.
problem Graph matching between correlated stochastic block models with constant correlation.
method Partition trees rooted from each vertex, comparing edge statistics to different communities.
result First low-order polynomial-time algorithm achieving exact matching with high probability in dense graphs.
Typical dimensionality reduction methods focus on directly reducing the number of random variables while retaining maximal variations in the data. In this paper, we consider the dimensionality reduction in parameter spaces of binary multivariate distributions. We propose a general Confident-Information-First (CIF) prin…
Meta-learning finds the best model in the space of all possible models.
problem No single learning algorithm performs best on all data.
method Searches for the best combination of parameters and procedures in the space of all possible models.
result Meta-learning approach finds the best method in all cases.
New algorithms detect categorical structures in high-dimensional data.
problem Detecting categorical structures in high-dimensional data.
method Low coordinate degree functions (LCDF) applied to categorical and stochastic block models.
result Unified analysis of LCDF performance for various SBMs and tight lower bounds.
Multilayer networks are a useful data structure for simultaneously capturing multiple types of relationships between a set of nodes. In such networks, each relational definition gives rise to a layer. While each layer provides its own set of information, community structure across layers can be collectively utilized to…
Improved sampling for network community detection.
problem Inefficient sampling from network partition posterior distributions.
method Merge-split Markov chain Monte Carlo for efficient sampling.
result Significantly improved mixing time and correct sampling.
This chapter provides a self-contained introduction to the use of Bayesian inference to extract large-scale modular structures from network data, based on the stochastic blockmodel (SBM), as well as its degree-corrected and overlapping generalizations. We focus on nonparametric formulations that allow their inference i…
Spectral algorithms solve optimal community detection and related problems.
problem Optimal detection of community structures and related substructures.
method Spectral algorithms applied to various planted substructures.
result Spectral algorithms achieve optimal performance for a wide range of planted substructures.
Paper tackles community recovery in binary symmetric SBM graphs.
problem Community detection in binary symmetric SBM graphs.
method Proposes a two-stage iterative method using projected power iterations and orthogonal iterations.
result Proposed method can exactly recover communities with high probability in logarithmic sparsity regime.