Consistency between ordering and clustering methods for graphs
This work addresses a gap in graph analysis by comparing clustering and ordering methods, but it is incremental as it builds on existing spectral techniques without introducing a new paradigm.
The study investigated the methodological relationships between clustering and ordering methods for graph data, proposing a label continuity error measure to quantify consistency, and evaluated their performance on synthetic and real-world datasets.
A relational dataset is often analyzed by optimally assigning a label to each element through clustering or ordering. While similar characterizations of a dataset would be achieved by both clustering and ordering methods, the former has been studied much more actively than the latter, particularly for the data represented as graphs. This study fills this gap by investigating methodological relationships between several clustering and ordering methods, focusing on spectral techniques. Furthermore, we evaluate the resulting performance of the clustering and ordering methods. To this end, we propose a measure called the label continuity error, which generically quantifies the degree of consistency between a sequence and partition for a set of elements. Based on synthetic and real-world datasets, we evaluate the extents to which an ordering method identifies a module structure and a clustering method identifies a banded structure.