umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis
Umeå University, Faculty of Science and Technology, Department of Physics.
Show others and affiliations
2017 (English)In: ACM Transactions on Knowledge Discovery from Data, ISSN 1556-4681, E-ISSN 1556-472X, Vol. 11, no 3, 32Article in journal (Refereed) Published
Abstract [en]

Community detection is an increasingly popular approach to uncover important structures in large networks. Flow-based community detection methods rely on communication patterns of the network rather than structural properties to determine communities. The Infomap algorithm in particular optimizes a novel objective function called the map equation and has been shown to outperform other approaches in third-party benchmarks. However, Infomap and its variants are inherently sequential, limiting their use for large-scale graphs. In this article, we propose a novel algorithm to optimize the map equation called RelaxMap. RelaxMap provides two important improvements over Infomap: parallelization, so that the map equation can be optimized over much larger graphs, and prioritization, so that the most important work occurs first, iterations take less time, and the algorithm converges faster. We implement these techniques using OpenMP on shared-memory multicore systems, and evaluate our approach on a variety of graphs from standard graph clustering benchmarks as well as real graph datasets. Our evaluation shows that both techniques are effective: RelaxMap achieves 70% parallel efficiency on eight cores, and prioritization improves algorithm performance by an additional 20-50% on average, depending on the graph properties. Additionally, RelaxMap converges in the similar number of iterations and provides solutions of equivalent quality as the serial Infomap implementation.

Place, publisher, year, edition, pages
2017. Vol. 11, no 3, 32
National Category
Other Physics Topics
Identifiers
URN: urn:nbn:se:umu:diva-134746DOI: 10.1145/2992785ISI: 000399725200007OAI: oai:DiVA.org:umu-134746DiVA: diva2:1094868
Available from: 2017-05-11 Created: 2017-05-11 Last updated: 2017-05-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Rosvall, Martin
By organisation
Department of Physics
In the same journal
ACM Transactions on Knowledge Discovery from Data
Other Physics Topics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf