Community detection (graph clustering) is the task of partitioning the vertex set of a graph into groups, where nodes in the same group are more densely connected than nodes in other groups.

The Stochastic Block Model (SBM) is a natural generative model commonly used in network science and graph theory to describe the formation of communities or clusters in a network [1]. Under this model, the probability of an edge existing between two nodes depends on their respective community assignments.

A common drawback of the SBM is that the degrees of the nodes are binomially distributed, while real graphs tend to have power-tailed distributions of the degrees. Various models have been proposed in the literature to correct this [2,3].

The goal of this project is to investigate whether the detection of the communities is easier or harder with non-binomial degrees.

[1] Abbe, E. (2017). Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1), 6446-6531.

[2] Karrer, B., & Newman, M. E. (2011). Stochastic blockmodels and community structure in networks. Physical review E, 83(1), 016107.

[3] Sengupta, S., & Chen, Y. (2018). A block model for node popularity in networks with community structure. Journal of the Royal Statistical Society Series B: Statistical Methodology, 80(2), 365-386.

[4] Chao Gao, Zongming Ma, Anderson Y. Zhang, Harrison H. Zhou. Community detection in degree-corrected block models. The Annals of Statistics, 46(5) 2153-2185 October 2018.