{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T02:30:40Z","timestamp":1768703440783,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100019190","name":"Intel Science and Technology Center for Big Data","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100019190","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1247469"],"award-info":[{"award-number":["1247469"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/2992785","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T14:12:04Z","timestamp":1488895924000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis"],"prefix":"10.1145","volume":"11","author":[{"given":"Seung-Hee","family":"Bae","sequence":"first","affiliation":[{"name":"University of Washington, Western Michigan University, Kalamazoo, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Halperin","sequence":"additional","affiliation":[{"name":"University of Washington, WA, Google"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jevin D.","family":"West","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Rosvall","sequence":"additional","affiliation":[{"name":"Ume\u00e5 University, Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bill","family":"Howe","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Exploring the limits of community detection strategies in complex networks. Scientific Reports 3, 2216","author":"Aldecoa Rodrigo","year":"2013","unstructured":"Rodrigo Aldecoa and Ignacio Mar\u00edn. 2013. Exploring the limits of community detection strategies in complex networks. Scientific Reports 3, 2216 (2013)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.138"},{"key":"e_1_2_1_3_1","volume-title":"Dynamics On and Of Complex Networks","author":"Bhowmick Sanjukta","unstructured":"Sanjukta Bhowmick and Sriram Srinivasan. 2013. A template for parallelizing the Louvain method for modularity maximization. In Dynamics On and Of Complex Networks, Volume 2. Animesh Mukherjee, Monojit Choudhury, Fernando Peruani, Niloy Ganguly, and Bivas Mitra (Eds.). Springer, New York, NY, 111--124."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/373515.373517"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/P09008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851593"},{"key":"e_1_2_1_11_1","volume-title":"Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge Workshop","volume":"588","author":"Auer Bas Fagginger","unstructured":"Bas Fagginger Auer and Rob H. Bisseling. 2013. Graph coarsening and clustering on the GPU. In Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge Workshop, vol. 588. American Mathematical Society."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04532"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of 2005 IEEE SuperComputing Conference (Poster).","author":"David","unstructured":"David F. Gleich and Leonid Zhukov. 2005. Scalable computing with power-law graphs: Experience with parallel PageRank. In Proceedings of 2005 IEEE SuperComputing Conference (Poster)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03288"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.025101"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.012809"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_2_1_22_1","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection. (2014). Retrieved","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (2014). Retrieved June 2014 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_1_24_1","volume-title":"Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications 389, 7","author":"Liu Xin","year":"2010","unstructured":"Xin Liu and Tsuyoshi Murata. 2010. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications 389, 7 (2010), 1493--1500."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2514\/1.2556"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986537"},{"key":"e_1_2_1_29_1","volume-title":"OpenMP Application Program Interface Version 3.0. (2008). Retrieved","author":"Architecture Review Board MP","year":"2008","unstructured":"OpenMP Architecture Review Board. 2008. OpenMP Application Program Interface Version 3.0. (2008). Retrieved May 2008 from http:\/\/www.openmp.org\/mp-documents\/spec30.pdf."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31464-3_29"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.203"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2010-01179-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018209"},{"key":"e_1_2_1_34_1","volume-title":"Memory in network flows and its effects on spreading dynamics and community detection. Nature Communications 5","author":"Rosvall Martin","year":"2014","unstructured":"Martin Rosvall, Alcides V. Esquivel, Andrea Lancichinetti, Jevin D. West, and Renaud Lambiotte. 2014. Memory in network flows and its effects on spreading dynamics and community detection. Nature Communications 5 (2014)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2891460.2891623"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2390633"},{"key":"e_1_2_1_39_1","unstructured":"Christian L. Staudt Aleksejs Sazonovs and Henning Meyerhenke. 2014. NetworKit: A Tool Suite for Large-scale Complex Network Analysis. arXiv:1403.3005 https:\/\/arxiv.org\/abs\/1403.3005."},{"key":"e_1_2_1_40_1","volume-title":"Bergstrom","author":"West Jevin D.","year":"2010","unstructured":"Jevin D. West, Theodore C. Bergstrom, and Carl T. Bergstrom. 2010. The eigenfactor metrics<sup>TM<\/sup>: A network approach to assessing scholarly journals. College 8 Research Libraries 71, 3 (2010), 236--244."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2228298.2228301"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038929"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557127"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2992785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2992785","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2992785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:37:49Z","timestamp":1763458669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2992785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/2992785"],"URL":"https:\/\/doi.org\/10.1145\/2992785","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}