Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Orca Reduction and ContrAction Graph Clustering
verfasst von : Daniel Delling, Robert Görke, Christian Schulz, Dorothea Wagner
Erschienen in: Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.