Parsimonious Module Inference in Large Networks

• https://arxiv.org/pdf/1212.4794.pdf
• Tiago Peixoto

An application of Minimum description length principle to the Community detection.

The description length is defined by $$\Sigma = \mathcal{S} + \mathcal{L},$$ where $\mathcal{S} = \ln \Omega$ is the microcanonical entropy ($\Omega$ is the total number of network realizations) and $\mathcal{L}$ is the information necessary to describe the model (the $\mathbf{M}$ and $\mathbf{z}$).

The extreme case $\mathbf{M} = \mathbf{A}$ will have $\mathcal{S} = 0$ (network is fully specified) but large value of $\mathcal{L}$ because there are $N^2$ entries of $\mathbf{M}$ + $N$ entries of $\mathbf{z}$ to be specified.