ID: 1711.05150

Fast and reliable inference algorithm for hierarchical stochastic block models

November 14, 2017

View on ArXiv

Similar papers 2

Mixture Models and Networks -- Overview of Stochastic Blockmodelling

May 19, 2020

90% Match
Nicola Giacomo De, Benjamin Sischka, Göran Kauermann
Methodology
Applications

Mixture models are probabilistic models aimed at uncovering and representing latent subgroups within a population. In the realm of network data analysis, the latent subgroups of nodes are typically identified by their connectivity behaviour, with nodes behaving similarly belonging to the same community. In this context, mixture modelling is pursued through stochastic blockmodelling. We consider stochastic blockmodels and some of their variants and extensions from a mixture mo...

Find SimilarView on arXiv

Clustering in networks with the collapsed Stochastic Block Model

March 14, 2012

90% Match
Aaron F. McDaid, Thomas Brendan Murphy, ... , Hurley Neil J
Computation

An efficient MCMC algorithm is presented to cluster the nodes of a network such that nodes with similar role in the network are clustered together. This is known as block-modelling or block-clustering. The model is the stochastic blockmodel (SBM) with block parameters integrated out. The resulting marginal distribution defines a posterior over the number of clusters and cluster memberships. Sampling from this posterior is simpler than from the original SBM as transdimensional...

Find SimilarView on arXiv

Distributed Community Detection in Large Networks

March 12, 2022

90% Match
Sheng Zhang, Rui Song, ... , Zhu Ji
Computation

Community detection for large networks is a challenging task due to the high computational cost as well as the heterogeneous community structure. Stochastic block model (SBM) is a popular model to analyze community structure where nodes belonging to the same communities are connected with equal probability. Modularity optimization methods provide a fast and effective way for community detection under SBM with assortative community structure, where nodes within communities are...

Find SimilarView on arXiv

Nonparametric weighted stochastic block models

August 4, 2017

90% Match
Tiago P. Peixoto
Machine Learning
Data Analysis, Statistics an...
Physics and Society

We present a Bayesian formulation of weighted stochastic block models that can be used to infer the large-scale modular structure of weighted networks, including their hierarchical organization. Our method is nonparametric, and thus does not require the prior knowledge of the number of groups or other dimensions of the model, which are instead inferred from data. We give a comprehensive treatment of different kinds of edge weights (i.e. continuous or discrete, signed or unsig...

Find SimilarView on arXiv

Data clustering using stochastic block models

July 24, 2017

90% Match
Nina Mrzelj, Pavlin Gregor Poličar
Social and Information Netwo...

It has been shown that community detection algorithms work better for clustering tasks than other, more popular methods, such as k-means. In fact, network analysis based methods often outperform more widely used methods and do not suffer from some of the drawbacks we notice elsewhere e.g. the number of clusters k usually has to be known in advance. However, stochastic block models which are known to perform well for community detection, have not yet been tested for this task....

Find SimilarView on arXiv

Reconstructing networks with unknown and heterogeneous errors

June 9, 2018

90% Match
Tiago P. Peixoto
Social and Information Netwo...
Machine Learning
Data Analysis, Statistics an...
Machine Learning

The vast majority of network datasets contains errors and omissions, although this is rarely incorporated in traditional network analysis. Recently, an increasing effort has been made to fill this methodological gap by developing network reconstruction approaches based on Bayesian inference. These approaches, however, rely on assumptions of uniform error rates and on direct estimations of the existence of each edge via repeated measurements, something that is currently unavai...

Find SimilarView on arXiv

Nonparametric Bayesian inference of the microcanonical stochastic block model

October 9, 2016

90% Match
Tiago P. Peixoto
Data Analysis, Statistics an...
Physics and Society
Machine Learning

A principled approach to characterize the hidden structure of networks is to formulate generative models, and then infer their parameters from data. When the desired structure is composed of modules or "communities", a suitable choice for this task is the stochastic block model (SBM), where nodes are divided into groups, and the placement of edges is conditioned on the group memberships. Here, we present a nonparametric Bayesian method to infer the modular structure of empiri...

Find SimilarView on arXiv

Fast Network Community Detection with Profile-Pseudo Likelihood Methods

November 1, 2020

90% Match
Jiangzhou Wang, Jingfei Zhang, Binghui Liu, ... , Guo Jianhua
Methodology
Statistics Theory
Machine Learning
Statistics Theory

The stochastic block model is one of the most studied network models for community detection. It is well-known that most algorithms proposed for fitting the stochastic block model likelihood function cannot scale to large-scale networks. One prominent work that overcomes this computational challenge is Amini et al.(2013), which proposed a fast pseudo-likelihood approach for fitting stochastic block models to large sparse networks. However, this approach does not have converge...

Find SimilarView on arXiv

Scalable and Robust Community Detection with Randomized Sketching

May 25, 2018

90% Match
Mostafa Rahmani, Andre Beckus, ... , Atia George
Social and Information Netwo...
Machine Learning
Machine Learning

This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a reduced graph sketch constructed using random sampling. Then, the clusters of the full graph are inferred based on the clusters extracted from the sketch using a ...

Find SimilarView on arXiv

Blockmodels: A R-package for estimating in Latent Block Model and Stochastic Block Model, with various probability functions, with or without covariates

February 24, 2016

90% Match
Jean-Benoist Leger
Computation

Analysis of the topology of a graph, regular or bipartite one, can be done by clustering for regular ones or co-clustering for bipartite ones. The Stochastic Block Model and the Latent Block Model are two models, which are very similar for respectively regular and bipartite graphs, based on probabilistic models. Initially developed for binary graphs, these models have been extended to valued networks with optional covariates on the edges. This paper present a implementation o...

Find SimilarView on arXiv