Graph Clustering with Surprise: Complexity and Exact Solutions

Tobias Fleck, Andrea Kappes, Dorothea Wagner

Clustering graphs based on a comparison of the number of links within clusters and the expected value of this quantity in a random graph has gained a lot of attention and popularit…