Graph clustering with surprise: complexity and exact solutions

DOI10.1007/978-3-319-04298-5_20MaRDI QIDQ2938102zbMATH OpenOpenAlexFDO

Authors Tobias Fleck, Andrea Kappes, Dorothea Wagner

Publication date 13 January 2015

Published in SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.6019

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: 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 popularity in the last decade. Recently, Aldecoa and Marin proposed a related, but slightly different approach leading to the quality measure surprise, and reported good behavior in the context of synthetic and real world benchmarks. We show that the problem of finding a clustering with optimum surprise is NP-hard. Moreover, a bicriterial view on the problem permits to compute optimum solutions for small instances by solving a small number of integer linear programs, and leads to a polynomial time algorithm on trees.

Recommendations

• On Finding Graph Clusterings with Maximum Modularity
• Graph clustering
• SOFSEM 2006: Theory and Practice of Computer Science
• The complexity of the simultaneous cluster problem
• Density-constrained graph clustering

This page was built for publication: Graph clustering with surprise: complexity and exact solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938102)