Structure-aware Distance Measures for Comparing Clusterings in Graphs

Abstract. Clustering in graphs aims to group vertices with similar pat-terns of connections. Applications include discovering communities and latent structures in graphs. Many algorithms have been proposed to find graph clusterings, but an open problem is the need for suitable com-parison measures to quantitatively validate these algorithms, performing consensus clustering and to track evolving (graph) clusters across time. To date, most comparison measures have focused on comparing the ver-tex groupings, and completely ignore the difference in the structural ap-proximations in the clusterings, which can lead to counter-intuitive com-parisons. In this paper, we propose new measures that account for differ-ences in the approximations. We focus on comparison measures for two important graph clustering approaches, community detection and block-modelling, and propose comparison measures that work for weighted (and unweighted) graphs