Bayesian Community Detection

• Activity Number: 492
• Type: Contributed
• Date/Time: Wednesday, August 12, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Bayesian Statistical Science
• Author(s): Stephanie van der Pas* and Aad van der Vaart
• Companies: Leiden University and Leiden University
• Keywords: stochastic block model ; Bayesian statistics ; consistency ; community detection

Abstract

In the stochastic block model, nodes in a graph are partitioned into classes ('communities') and it is assumed that the probability of the presence of an edge between two nodes solely depends on their class labels. We are interested in recovering the class labels, and employ the Bayesian posterior mode for this purpose. We present results on weak consistency (where the fraction of misclassified nodes converges to zero) and strong consistency (where the number of misclassified nodes converges to zero) of the posterior mode, in the 'dense' regime where the probability of an edge occurring between two nodes remains bounded away from zero, and in the 'sparse' regime where this probability does go to zero as the number of nodes increases.