umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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 Flow-Based Community Detection for Large-Scale Network Analysis
Umeå University, Faculty of Science and Technology, Department of Physics.
Show others and affiliations
2013 (English)In: 2013 IEEE 13TH INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOPS (ICDMW) / [ed] Ding, W Washio, T Xiong, H Karypis, G Thuraisingham, B Cook, D Wu, X, IEEE, 2013, p. 303-310Conference paper, Published paper (Refereed)
Abstract [en]

Community-detection is a powerful approach to uncover important structures in large networks. Since networks often describe flow of some entity, flow-based community-detection methods are particularly interesting. One such algorithm is called Infomap, which optimizes the objective function known as the map equation. While Infomap is known to be an effective algorithm, its serial implementation cannot take advantage of multicore processing in modern computers. In this paper, we propose a novel parallel generalization of Infomap called RelaxMap. This algorithm relaxes concurrency assumptions to avoid lock overhead, achieving 70% parallel efficiency in shared-memory multicore experiments while exhibiting similar convergence properties and finding similar community structures as the serial algorithm. We evaluate our approach on a variety of real graph datasets as well as synthetic graphs produced by a popular graph generator used for benchmarking community detection algorithms. We describe the algorithm, the experiments, and some emerging research directions in high-performance community detection on massive graphs.

Place, publisher, year, edition, pages
IEEE, 2013. p. 303-310
Series
International Conference on Data Mining Workshops, ISSN 2375-9232
National Category
Other Physics Topics Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-142771DOI: 10.1109/ICDMW.2013.138ISI: 000343602800040ISBN: 978-0-7695-5109-8 (print)OAI: oai:DiVA.org:umu-142771DiVA, id: diva2:1166640
Conference
IEEE 13th International Conference on Data Mining (ICDM), DEC 07-10, 2013, Dallas, TX
Funder
Swedish Research Council, 2012-3729Available from: 2017-12-15 Created: 2017-12-15 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Halperin, DanielWest, JevinRosvall, MartinHowe, Bill

Search in DiVA

By author/editor
Halperin, DanielWest, JevinRosvall, MartinHowe, Bill
By organisation
Department of Physics
Other Physics TopicsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 72 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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