Parsimonious module inference in large networks

Abstract

We investigate the detectability of modules in large networks when the number of modules is not known in advance. We employ the minimum description length (MDL) principle which seeks to minimize the total amount of information required to describe the network, and avoid overfitting. According to this criterion, we obtain general bounds on the detectability of any prescribed block structure, given the number of nodes and edges in the sampled network. We also obtain that the maximum number of detectable blocks scales as $\sqrt{N}$, where $N$ is the number of nodes in the network, for a fixed average degree $<k>$. We also show that the simplicity of the MDL approach yields an efficient multilevel Monte Carlo inference algorithm with a complexity of $O(\tau N\log N)$, if the number of blocks is unknown, and $O(\tau N)$ if it is known, where $\tau$ is the mixing time of the Markov chain. We illustrate the application of the method on a large network of actors and films with over $10^6$ edges, and a dissortative, bipartite block structure.

5 pages, 4 figures + Supplemental Material

References in corpus (17)

• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• A Bayesian Approach to Network Modularity
• The entropy of network ensembles
• Community Detection as an Inference Problem
• Maximum likelihood: extracting unbiased information from complex networks
• Clique Graphs and Overlapping Communities
• Role models for complex networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models