Orca Reduction and ContrAction Graph Clustering

• Main Authors: Daniel Delling, Robert Görke, Christian Schulz, Dorothea Wagner
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2009
• Subjects: Orca
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2905; http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf

During the last years, a wide range of huge networks has been made available to researchers. The discovery of natural groups, a task called graph clustering, in such datasets is a challenge arising in many applications such as the analysis of neural, social, and communication networks. We here present Orca, a new graph clustering algorithm, which operates locally and hierarchically contracts the input. In contrast to most existing graph clustering algorithms, which operate globally, Orca is able to cluster inputs with hundreds of millions of edges in less than 2.5 hours, identifying clusterings with measurably high quality. Our approach explicitly avoids maximizing any single index value such as modularity, but instead relies on simple and sound structural operations. We present and discuss the Orca algorithm and evaluate its performance with respect to both clustering quality and running time, compared to other graph clustering algorithms.