{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:17:09Z","timestamp":1765369029715,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,9]],"date-time":"2015-06-09T00:00:00Z","timestamp":1433808000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001729","name":"Swedish Foundation for Strategic Research","doi-asserted-by":"publisher","award":["RIT10-0043"],"award-info":[{"award-number":["RIT10-0043"]}],"id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2015,6,9]]},"abstract":"<jats:p>\n            Balanced graph partitioning is an NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems, including the optimal storage of large sets of graph-structured data over several hosts. However, in very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable because they typically involve frequent global operations over the entire graph. In this article, we propose a fully distributed algorithm called J\n            <jats:sc>A<\/jats:sc>\n            -\n            <jats:sc>BE<\/jats:sc>\n            -J\n            <jats:sc>A<\/jats:sc>\n            that uses local search and simulated annealing techniques for two types of graph partitioning:\n            <jats:italic>edge-cut<\/jats:italic>\n            partitioning and\n            <jats:italic>vertex-cut<\/jats:italic>\n            partitioning. The algorithm is massively parallel: There is no central coordination, each vertex is processed independently, and only the direct neighbors of a vertex and a small subset of random vertices in the graph need to be known locally. Strict synchronization is not required. These features allow J\n            <jats:sc>A<\/jats:sc>\n            -\n            <jats:sc>BE<\/jats:sc>\n            -J\n            <jats:sc>A<\/jats:sc>\n            to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We show that the minimal edge-cut value empirically achieved by J\n            <jats:sc>A<\/jats:sc>\n            -\n            <jats:sc>BE<\/jats:sc>\n            -J\n            <jats:sc>A<\/jats:sc>\n            is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks, J\n            <jats:sc>A<\/jats:sc>\n            -\n            <jats:sc>BE<\/jats:sc>\n            -J\n            <jats:sc>A<\/jats:sc>\n            outperforms Metis. We also show that J\n            <jats:sc>A<\/jats:sc>\n            -\n            <jats:sc>BE<\/jats:sc>\n            -J\n            <jats:sc>A<\/jats:sc>\n            computes very low vertex-cuts, which are proved significantly more effective than edge-cuts for processing most real-world graphs.\n          <\/jats:p>","DOI":"10.1145\/2714568","type":"journal-article","created":{"date-parts":[[2015,6,12]],"date-time":"2015-06-12T18:26:28Z","timestamp":1434133588000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["A Distributed Algorithm for Large-Scale Graph Partitioning"],"prefix":"10.1145","volume":"10","author":[{"given":"Fatemeh","family":"Rahimian","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology and SICS Swedish ICT, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir H.","family":"Payberah","sequence":"additional","affiliation":[{"name":"SICS Swedish ICT, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarunas","family":"Girdzijauskas","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jelasity","sequence":"additional","affiliation":[{"name":"MTA SZTE Research Group on AI, Hungarian Academy of Sciences and University of Szeged, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seif","family":"Haridi","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology and SICS Swedish ICT, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899055"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"volume-title":"Error and attack tolerance of complex networks. Nature 406, 6794","year":"2000","author":"Albert R\u00e9ka","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007931"},{"volume-title":"Partitioning graph databases-a quantitative evaluation. arXiv preprint arXiv:1301.5121","year":"2013","author":"Averbuch Alex","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.126"},{"volume-title":"Montoya","year":"2003","author":"Ba\u00f1os Raul","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.10.007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2011.2136346"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.508322"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.70760"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"David Dominguez-Sal P. Urb\u00f3n-Bayes Aleix Gim\u00e9nez-Va\u00f1\u00f3 Sergio G\u00f3mez-Villamor Norbert Mart\u00ednez-Baz\u00e1n and Josep-Lluis Larriba-Pey. 2010. Survey of graph database performance on the HPC scalable graph analysis benchmark. (2010) 37--48.   David Dominguez-Sal P. Urb\u00f3n-Bayes Aleix Gim\u00e9nez-Va\u00f1\u00f3 Sergio G\u00f3mez-Villamor Norbert Mart\u00ednez-Baz\u00e1n and Josep-Lluis Larriba-Pey. 2010. Survey of graph database performance on the HPC scalable graph analysis benchmark. (2010) 37--48.","DOI":"10.1007\/978-3-642-16720-1_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2012.19"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/30.7.1575"},{"volume-title":"Proceedings of Workshop on Online Social Networks (WOSN). USENIX Association, 3--3.","year":"2010","author":"Galuba Wojciech","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470922"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of USENIX Symposium on Operating System Design and Implementation (OSDI)","volume":"12","author":"Gonzalez Joseph E.","year":"2012"},{"volume-title":"Distributed edge partitioning for graph processing. arXiv preprint arXiv:1403.6270","year":"2014","author":"Guerrieri Alessio","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646012.677019"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224228"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082469.1082470"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2011.11.004"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITC.2010.5608727"},{"volume-title":"Stanford Large Network Dataset collection. URL http:\/\/snap.stanford.edu\/data\/index. html","year":"2011","author":"Leskovec Jure","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"volume-title":"Parallel Genetic Algorithms: Theory and Real World Applications","author":"Luque Gabriel","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146402"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536237"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2009.09.006"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2009.5284506"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022090.2022091"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43352-2_15"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2013.13"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.101"},{"volume-title":"Algorithms (ESA\u201911)","author":"Sanders Peter","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790265.2790267"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOGO.0000042115.44455.f3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1718024"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/109025.109102"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03869-3_50"},{"volume-title":"Van Laarhoven and Emile H. L. Aarts","year":"1987","author":"Peter J.","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10922-005-4441-x"},{"key":"e_1_2_1_51_1","unstructured":"C. Walshaw. 2012a. FocusWare NetWorks MNO\u2014A commercialised version of JOSTLE. Retrieved from http:\/\/http:\/\/focusware.co.uk.  C. Walshaw. 2012a. FocusWare NetWorks MNO\u2014A commercialised version of JOSTLE. Retrieved from http:\/\/http:\/\/focusware.co.uk."},{"key":"e_1_2_1_52_1","unstructured":"C. Walshaw. 2012b. The Graph Partitioning Archive. Retrieved from http:\/\/staffweb.cms.gre.ac.uk\/&sim;wc06\/partition.  C. Walshaw. 2012b. The Graph Partitioning Archive. Retrieved from http:\/\/staffweb.cms.gre.ac.uk\/&sim;wc06\/partition."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598337373"},{"volume-title":"Strogatz","year":"1998","author":"Watts Duncan J.","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"volume-title":"Proceedings of USENIX Conference on Networked Systems Design and Implementation (NSDI\u201912)","year":"2012","author":"Zaharia Matei","key":"e_1_2_1_56_1"},{"volume-title":"Proceedings of USENIX Workshop on Hot Topics in Cloud Computing (HotCloud\u201910)","year":"2010","author":"Zaharia Matei","key":"e_1_2_1_57_1"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2714568","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2714568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:56:14Z","timestamp":1750272974000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2714568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,9]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,9]]}},"alternative-id":["10.1145\/2714568"],"URL":"https:\/\/doi.org\/10.1145\/2714568","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2015,6,9]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}