CommunityDetection.png

Bayesian community detection

We introduce a Bayesian estimator of the underlying class structure in the stochastic block model, when the number of classes is known, and show strong consistency.

Summary

The stochastic block model (SBM) is a model for network data in which individual nodes are considered members of classes or communities, and the probability of a connection occurring between two individuals depends solely on their class membership. It has been applied to social, biological and communication networks.

 

Two main SBM research directions are the recovery of the class labels (community detection) and recovery of the remaining model parameters, consisting of the probability vector generating the class labels, and the class-dependent probabilities of creating an edge between nodes. In this paper, we focused on community detection, noting that once strong consistency of a community detection method has been established, consistency of the natural plug-in estimators for the remaining parameters follows directly. We provided theoretical results on community detection, establishing that the Bayesian posterior mode is strongly consistent for the class labels if the expected degree is at least of order (log n)^2, where n is the number of nodes.

Related papers

Van der Pas, S. L., & Van der Vaart, A. (2018). Bayesian community detection. Bayesian Analysis, 13(3), 767-796. [link]