Advertisement
Published in:
2009 | OriginalPaper | Chapter
Orca Reduction and ContrAction Graph Clustering
Authors : Daniel Delling, Robert Görke, Christian Schulz, Dorothea Wagner
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.