{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:31Z","timestamp":1750220071080,"version":"3.41.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T00:00:00Z","timestamp":1670889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CAREER IIS 1553528, SI2-SSE 1716828"],"award-info":[{"award-number":["CAREER IIS 1553528, SI2-SSE 1716828"]}]},{"name":"U.S. DOE Exascale Computing Project\u2019s","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm\u00a0(DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm\u00a0(LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of\n            <jats:italic>frontiers<\/jats:italic>\n            and alternates between label\n            <jats:italic>push<\/jats:italic>\n            and label\n            <jats:italic>pull<\/jats:italic>\n            operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2\u00d7 speedup over the Shiloach-Vishkin algorithm, and up to 1.6\u00d7 speedup over Afforest on an Intel Xeon processor using 40 threads.\n          <\/jats:p>","DOI":"10.1145\/3564593","type":"journal-article","created":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T12:26:45Z","timestamp":1666873605000},"page":"1-31","source":"Crossref","is-referenced-by-count":3,"title":["Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3980-9803","authenticated-orcid":false,"given":"Xu","family":"Liu","sequence":"first","affiliation":[{"name":"Washington State University, Pullman, USA, and Pacific Northwest National Lab, Richland, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9153-6622","authenticated-orcid":false,"given":"Andrew","family":"Lumsdaine","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA, and Pacific Northwest National Lab, Richland, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2323-4753","authenticated-orcid":false,"given":"Mahantesh","family":"Halappanavar","sequence":"additional","affiliation":[{"name":"Pacific Northwest National Lab, Richland, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4947-0559","authenticated-orcid":false,"given":"Kevin","family":"Barker","sequence":"additional","affiliation":[{"name":"Pacific Northwest National Lab, Richland, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5383-8032","authenticated-orcid":false,"given":"Assefaw","family":"Gebremedhin","sequence":"additional","affiliation":[{"name":"Washington State University, Pullman, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00012"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4355"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7163-9_23-1"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.026129"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.3233\/SPR-130370"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078616"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626421500213"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2634535"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436923"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05411-3_14"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.106060"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2019.122058"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127412501714"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/AISP.2015.7123488"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208040.3208041"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/133889"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933108"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091040"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623621"},{"key":"e_1_3_2_26_2","series-title":"Proceedings of the 31st Conference On Learning Theory","first-page":"1966","volume":"75","author":"Klusowski J. M.","year":"2018","unstructured":"J. M. Klusowski and Y. Wu. 2018. Counting motifs with graph sampling. In Proceedings of the 31st Conference On Learning Theory(Proceedings of Machine Learning Research, Vol. 75), S. Bubeck, V. Perchet, and P. Rigollet (Eds.). PMLR, 1966\u20132011. http:\/\/proceedings.mlr.press\/v75\/klusowski18a.html."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132960"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1155\/2015\/461362"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387884"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810534"},{"key":"e_1_3_2_34_2","unstructured":"J. Leskovec and A. Krevl. 2016. SNAP datasets: Stanford large network dataset collection; 2014. http:\/\/snap.stanford.edu\/data (2016)."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.79.066107"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2014.09.023"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.3"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2009.12.019"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916215"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3387902.3392634"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.03.003"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161100"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2010.77"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145832"},{"key":"e_1_3_2_45_2","volume-title":"On Distributed Verification and Verified Distribution","author":"Orzan S. M.","year":"2004","unstructured":"S. M. Orzan. 2004. On Distributed Verification and Verified Distribution. Ph.D. thesis. VRIJE UNIVERSITEIT. http:\/\/dare.ubvu.vu.nl\/handle\/1871\/10338."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.37"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2008.12.021"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612692"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.057101"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.61"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2390633"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159696"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380275"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00012"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3404397.3404455"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518687"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48096-0_34"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/NSW.2013.6609210"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1155\/2014\/627581"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2017.12.146"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688507"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2016.06.002"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0217979215500290"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.04.009"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2015.11.125"},{"key":"e_1_3_2_74_2","volume-title":"Learning from Labeled and Unlabeled Data with Label Propagation","author":"Zhu X.","year":"2002","unstructured":"X. Zhu and Z. Ghahramani. 2002. Learning from Labeled and Unlabeled Data with Label Propagation. Technical Report. CMU."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564593","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:11Z","timestamp":1750183751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,13]]},"references-count":73,"alternative-id":["10.1145\/3564593"],"URL":"https:\/\/doi.org\/10.1145\/3564593","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,12,13]]}}}