Consistency between ordering and clustering methods for graphs

Abstract

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.

30 pages, 26 figures

References in corpus (11)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Community detection in networks: A user guide
• Consistency of spectral clustering
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Nestedness in complex networks: Observation, emergence, and implications
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors

Cited by in corpus (2)

• Exact and rapid linear clustering of networks with dynamic programming
• Finding community structure using the ordered random graph model