{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T10:25:48Z","timestamp":1777285548705,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T00:00:00Z","timestamp":1632355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2016YFB1000901"],"award-info":[{"award-number":["2016YFB1000901"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61806065, 91746209, and 62076087"],"award-info":[{"award-number":["61806065, 91746209, and 62076087"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["JZ2020HGQA0186"],"award-info":[{"award-number":["JZ2020HGQA0186"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>Graph edge partitioning, which is essential for the efficiency of distributed graph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local Graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local Graph Edge Partitioning model, two local graph edge partitioning algorithms\u2014Two-stage Local Partitioning and Adaptive Local Partitioning\u2014are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system GraphX.<\/jats:p>","DOI":"10.1145\/3466685","type":"journal-article","created":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T14:48:38Z","timestamp":1632494918000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Local Graph Edge Partitioning"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4942-9767","authenticated-orcid":false,"given":"Shengwei","family":"Ji","sequence":"first","affiliation":[{"name":"Key Laboratory of Knowledge Engineering with Big Data, Ministry of Education, China, and School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China, and Institute of Big Knowledge Science, Hefei University of Technology, Hefei, China, and Institute of Big Knowledge Science, Hefei University of Technology, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8203-0956","authenticated-orcid":false,"given":"Chenyang","family":"Bu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Knowledge Engineering with Big Data, Ministry of Education, China, and School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China, and Institute of Big Knowledge Science, Hefei University of Technology, Hefei, China, and Mininglamp Academy of Sciences, Mininglamp Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[{"name":"Key Laboratory of Knowledge Engineering with Big Data, Ministry of Education, China, and School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China, and Institute of Big Knowledge Science, Hefei University of Technology, Hefei, Anhui, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xindong","family":"Wu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Knowledge Engineering with Big Data, Ministry of Education, China, and School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China, and Institute of Big Knowledge Science, Hefei University of Technology, Hefei, China, and Mininglamp Academy of Sciences, Mininglamp Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364222"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018730110112519"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685048.2685096"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.02.003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00031"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1403"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_13_1","first-page":"1","article-title":"Multi-fuzzy-objective graph pattern matching in big graph environments with reliability, trust and social relationship","volume":"23","author":"Li Lei","year":"2019","unstructured":"Lei Li , Fang Zhang , Zan Zhang , Peipei Li , and Chenyang Bu . 2019 . Multi-fuzzy-objective graph pattern matching in big graph environments with reliability, trust and social relationship . World Wide Web 23 , 1 (Aug. 2019), 649\u2013669. Lei Li, Fang Zhang, Zan Zhang, Peipei Li, and Chenyang Bu. 2019. Multi-fuzzy-objective graph pattern matching in big graph environments with reliability, trust and social relationship. World Wide Web 23, 1 (Aug. 2019), 649\u2013669.","journal-title":"World Wide Web"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3023549.3023589"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2866863"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl562"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TETC.2017.2751101"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TFUZZ.2018.2812148"},{"key":"e_1_2_1_19_1","article-title":"Multiscale local community detection in social networks (early access)","volume":"58","author":"Luo Wenjian","year":"2019","unstructured":"Wenjian Luo , Daofu Zhang , Li Ni , and Nannan Lu . 2019 . Multiscale local community detection in social networks (early access) . IEEE Transactions on Knowledge and Data Engineering 58 , 1( Aug. 2019), 1. https:\/\/doi.org\/10.1109\/TKDE.2019.2938173 10.1109\/TKDE.2019.2938173 Wenjian Luo, Daofu Zhang, Li Ni, and Nannan Lu. 2019. Multiscale local community detection in social networks (early access). IEEE Transactions on Knowledge and Data Engineering 58, 1(Aug. 2019), 1. https:\/\/doi.org\/10.1109\/TKDE.2019.2938173","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824046"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"e_1_2_1_23_1","volume-title":"GAP: Generalizable approximate graph partitioning framework. arXiv:1903.00614.","author":"Nazi Azade","year":"2019","unstructured":"Azade Nazi , Will Hang , Anna Goldie , Sujith Ravi , and Azalia Mirhoseini . 2019 . GAP: Generalizable approximate graph partitioning framework. arXiv:1903.00614. Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. 2019. GAP: Generalizable approximate graph partitioning framework. arXiv:1903.00614."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3361739"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926718"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2327037"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-018-1282-y"},{"key":"e_1_2_1_33_1","first-page":"1","article-title":"Knowledge engineering with big data (BigKE): A 54-month, 45-million RMB, 15-institution national grand project","volume":"5","author":"Wu Xindong","year":"2014","unstructured":"Xindong Wu , Huanhuan Chen , Jun Liu , Gongqing Wu , Ruqian Lu , and Nanning Zheng . 2014 . Knowledge engineering with big data (BigKE): A 54-month, 45-million RMB, 15-institution national grand project . IEEE Access 5 , 1 (July 2014), 12696\u201312701. Xindong Wu, Huanhuan Chen, Jun Liu, Gongqing Wu, Ruqian Lu, and Nanning Zheng. 2014. Knowledge engineering with big data (BigKE): A 54-month, 45-million RMB, 15-institution national grand project. IEEE Access 5, 1 (July 2014), 12696\u201312701.","journal-title":"IEEE Access"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2979681"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2968826.2969013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2015.56"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3454561"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098033"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3466685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3466685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:52Z","timestamp":1750195492000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3466685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,23]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3466685"],"URL":"https:\/\/doi.org\/10.1145\/3466685","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,23]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}