Self-similarity of Communities of the ABCD Model
Jordan Barrett Bogumil Kaminski Pawel Pralat Francois Theberge
The Artificial Benchmark for Community Detection (ABCD) graph is a random
graph model with community structure and power-law distribution for both
degrees and community sizes. The model generates graphs similar to the
well-known LFR model but it is faster and can be investigated analytically.
  In this paper, we show that the ABCD model exhibits some interesting
self-similar behaviour, namely, the degree distribution of ground-truth
communities is asymptotically the same as the degree distribution of the whole
graph (appropriately normalized based on their sizes). As a result, we can not
only estimate the number of edges induced by each community but also the number
of self-loops and multi-edges generated during the process. Understanding these
quantities is important as (a) rewiring self-loops and multi-edges to keep the
graph simple is an expensive part of the algorithm, and (b) every rewiring
causes the underlying configuration models to deviate slightly from uniform
simple graphs on their corresponding degree sequences.