A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Spectral clustering achieves strong consistency in the stochastic block model under certain conditions.
In the present paper we study a sparse stochastic network enabled with a block structure. The popular Stochastic Block Model (SBM) and the Degree Corrected Block Model (DCBM) address sparsity by placing an upper bound on the maximum probability of connections between any pair of nodes. As a result, sparsity describes o…
We generalize the stochastic block model to the important case in which edges are annotated with weights drawn from an exponential family distribution. This generalization introduces several technical difficulties for model estimation, which we solve using a Bayesian approach. We introduce a variational algorithm that …
A central problem in analyzing networks is partitioning them into modules or communities. One of the best tools for this is the stochastic block model, which clusters vertices into blocks with statistically homogeneous pattern of links. Despite its flexibility and popularity, there has been a lack of principled statist…
Efficient algorithm for robust recovery in stochastic block models.
New method improves community detection for large networks.
Paper introduces a new edge exchangeable block model for complex networks.
There exist various types of network block models such as the Stochastic Block Model (SBM), the Degree Corrected Block Model (DCBM), and the Popularity Adjusted Block Model (PABM). While this leads to a variety of choices, the block models do not have a nested structure. In addition, there is a substantial jump in the …
We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recovery of the latent communities, up to the information-theoretic limits determined by Abbe and Sandon (…
To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model generalizes the random geometric graphs in the same way that the well-studied stochastic block model generalizes the …
Spectral clustering for directed graphs using likelihood estimation.
Tests if vertices in graphs have the same latent positions.
We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the network can consistently recover hidden communities even when the order of the maximum expected degree is as small as $\l…
New algorithm optimally clusters networks with side information.
Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We pro…
Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The s…
A main task in data analysis is to organize data points into coherent groups or clusters. The stochastic block model is a probabilistic model for the cluster structure. This model prescribes different probabilities for the presence of edges within a cluster and between different clusters. We assume that the cluster ass…
The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks…
The stochastic block model (SBM) is a probabilistic model for community structure in networks. Typically, only the adjacency matrix is used to perform SBM parameter inference. In this paper, we consider circumstances in which nodes have an associated vector of continuous attributes that are also used to learn the node-…
The tree reconstruction problem is to collect and analyze massive data at the th level of the tree, to identify whether there is non-vanishing information of the root, as goes to infinity. Its connection to the clustering problem in the setting of the stochastic block model, which has wide applications in machin…
Network clustering reveals the organization of a network or corresponding complex system with elements represented as vertices and interactions as edges in a (directed, weighted) graph. Although the notion of clustering can be somewhat loose, network clusters or groups are generally considered as nodes with enriched in…
We propose and analyze a generic method for community recovery in stochastic block models and degree corrected block models. This approach can exactly recover the hidden communities with high probability when the expected node degrees are of order or higher. Starting from a roughly correct community partition …
A new method speeds up community detection in graphs.
ALMA improves clustering of multilayer networks.
We analyze the information-theoretic limits for the recovery of node labels in several network models. This includes the Stochastic Block Model, the Exponential Random Graph Model, the Latent Space Model, the Directed Preferential Attachment Model, and the Directed Small-world Model. For the Stochastic Block Model, the…
Sharp thresholds and contiguity for community detection in contextual SBM.
Efficient private algorithms for estimating block models and mixture models.
A test for comparing networks using stochastic block models.
We consider the problem of estimating the location of a single change point in a dynamic stochastic block model. We propose two methods of estimating the change point, together with the model parameters. The first employs a least squares criterion function and takes into consideration the full structure of the stochast…
One of the most fundamental problems in network study is community detection. The stochastic block model (SBM) is a widely used model, for which various estimation methods have been developed with their community detection consistency results unveiled. However, the SBM is restricted by the strong assumption that all no…
Estimates social network structure from random walk subgraphs.
The stochastic block model accurately describes most empirical networks but struggles with large diameter and slow-mixing networks.
VEC-SBM detects communities using side information like texts and images.
Randomized spectral co-clustering speeds up large-scale directed networks.
New model for community detection with side information improves recovery accuracy.
New model for clustering graphs with multiple data sources.
Study information limits for community detection in sub-hypergraphs.
New model improves community detection in networks with strong assortativity.
Paper characterizes optimal graph clustering limits under a new model.
A new model detects complex network communities using node attributes.
Study community detection in multi-view data with various types of information.
The stochastic block model is a powerful tool for inferring community structure from network topology. However, it predicts a Poisson degree distribution within each community, while most real-world networks have a heavy-tailed degree distribution. The degree-corrected block model can accommodate arbitrary degree distr…
Sharp threshold for exact recovery in non-uniform hypergraph stochastic block model.
Efficient algorithm for graph matching in correlated stochastic block models.
Inference of hidden classes in stochastic block model is a classical problem with important applications. Most commonly used methods for this problem involve naïve mean field approaches or heuristic spectral methods. Recently, belief propagation was proposed for this problem. In this contribution we perform a comparati…
New algorithm recovers communities in broader network models.
A new method clusters data from multiple sources using a mixture of multilayer SBMs.
New algorithm detects communities even with corrupted data, reaching Kesten-Stigum threshold.