Orca Reduction and ContrAction Graph Clustering
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 prese...
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Published: |
2009
|
Subjects: | |
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 |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.164.2905 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.164.2905 2023-05-15T17:53:07+02:00 Orca Reduction and ContrAction Graph Clustering Daniel Delling Robert Görke Christian Schulz Dorothea Wagner The Pennsylvania State University CiteSeerX Archives 2009 application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2905 http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2905 http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf text 2009 ftciteseerx 2016-01-07T15:48:55Z 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. Text Orca Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
description |
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. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Daniel Delling Robert Görke Christian Schulz Dorothea Wagner |
spellingShingle |
Daniel Delling Robert Görke Christian Schulz Dorothea Wagner Orca Reduction and ContrAction Graph Clustering |
author_facet |
Daniel Delling Robert Görke Christian Schulz Dorothea Wagner |
author_sort |
Daniel Delling |
title |
Orca Reduction and ContrAction Graph Clustering |
title_short |
Orca Reduction and ContrAction Graph Clustering |
title_full |
Orca Reduction and ContrAction Graph Clustering |
title_fullStr |
Orca Reduction and ContrAction Graph Clustering |
title_full_unstemmed |
Orca Reduction and ContrAction Graph Clustering |
title_sort |
orca reduction and contraction graph clustering |
publishDate |
2009 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2905 http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf |
genre |
Orca |
genre_facet |
Orca |
op_source |
http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2905 http://i11www.ira.uka.de/extra/publications/dgsw-orca-09.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766160835470688256 |