Regular Decomposition: an information and graph theoretic approach to stochastic block models

Abstract

A method for compression of large graphs and non-negative matrices to a block structure is proposed. Szemerédi's regularity lemma is used as heuristic motivation of the significance of stochastic block models. Another ingredient of the method is Rissanen's minimum description length principle (MDL). We propose practical algorithms and provide theoretical results on the accuracy of the method.

Simulation example added. Poisson block model code length estimates changed

References in corpus (4)

• An information-theoretic framework for resolving community structure in complex networks
• Parsimonious module inference in large networks
• Community Detection in the Labelled Stochastic Block Model
• A Practical Regularity Partitioning Algorithm and its Applications in Clustering

Cited by in corpus (4)

• A network community detection method with integration of data from multiple layers and node attributes
• Towards analyzing large graphs with quantum annealing and quantum gate computers
• Analysis of large sparse graphs using regular decomposition of graph distance matrices
• Regular Partitions and Their Use in Structural Pattern Recognition