{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T05:05:08Z","timestamp":1749531908202,"version":"3.37.3"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T00:00:00Z","timestamp":1649721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61602354","61876138"],"award-info":[{"award-number":["61602354","61876138"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Information Technology Research Center","award":["IITP-2022-2020-0-01462"],"award-info":[{"award-number":["IITP-2022-2020-0-01462"]}]},{"name":"Institute of Information and Communications Technology Planning & Evaluation","award":["2014-3-00123"],"award-info":[{"award-number":["2014-3-00123"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,7,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Graph partitioning is an NP-hard combinatorial optimization problem, and is a fundamental step in distributing workloads on parallel compute systems, circuit placement, and sparse matrix reordering. The proposed heuristic algorithms such as streaming graph partitioning provide solutions to large-scale graph in a reasonable amount of time. However, the ability of breaking out of local minima in existing these methods is very limited as they are simple in reflecting the connectivity between vertices in real graphs with power-law distribution characteristic. As hill climbing algorithm is a local search method, it can be adopted to improve the result of graph partitioning. However, directly adopting the existing hill climbing algorithm to graph partitioning will result in local minima and poor convergence speed during the iterative process. In this paper, we propose an improved hill climbing graph partitioning algorithm based on clustering. Instead of taking a single vertex as a basic unit, the proposed method considers a cluster consisting of a series of vertices as a hill to move during each iteration. The method uses a new metric that considers both balance and edgecuts to look for the most beneficial cluster as the hill. With these improvements, the method provides a strong power to break out of local minima and achieve an adaptive tradeoff between balance and edgecuts. Experimental results on real-world graphs show that the proposed algorithm substantially reduces edgecuts within a controlled imbalance range.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac039","type":"journal-article","created":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T12:18:20Z","timestamp":1647346700000},"page":"1761-1776","source":"Crossref","is-referenced-by-count":5,"title":["An Improved Hill Climbing Algorithm for Graph Partitioning"],"prefix":"10.1093","volume":"66","author":[{"given":"He","family":"Li","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology , Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanna","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology , Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuqi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology , Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishuai","family":"Lin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology , Xidian University, Xi\u2019an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Information and Communication Engineering , Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaesoo","family":"Yoo","sequence":"additional","affiliation":[{"name":"Chungbuk National University , Cheongju, Chungcheongbuk-do, KR"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,4,12]]},"reference":[{"volume-title":"Proceedings of the 1995 ACM\/IEEE conference on Supercomputing, San Diego, CA, USA, 8-8 December","year":"1995","author":"Bruce","key":"2023071709115995400_ref1"},{"key":"2023071709115995400_ref2","first-page":"242","volume-title":"Proceedings of ICA3PP, Vietri sul Mare, Italy, 18\u201320 December","author":"Hu","year":"2019"},{"key":"2023071709115995400_ref3","first-page":"1269","volume-title":"Proceedings of ISPA\/IUCC, Guangzhou, China, 12-15 December","author":"Li","year":"2017"},{"key":"2023071709115995400_ref4","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","article-title":"An efficient heuristic procedure for partitioning graphs","volume":"49","author":"Kernighan","year":"1970","journal-title":"Bell Syst. Tech. J."},{"key":"2023071709115995400_ref5","first-page":"175","volume-title":"19th Conference on Design Automation, Las Vegas, Nevada, USA, 14\u201316 June","author":"Fiduccia","year":"1982"},{"key":"2023071709115995400_ref6","first-page":"512","volume-title":"Proceedings of ICCAD 98, San Jose, CA, USA, 8-12 November","author":"Gong","year":"1998"},{"key":"2023071709115995400_ref7","first-page":"234","volume-title":"Proceedings of ICPP, Philadelphia, PA, USA, 16-19 August","author":"Lasalle","year":"2016"},{"key":"2023071709115995400_ref8","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","article-title":"Multilevel k-way partitioning scheme for irregular graphs","volume":"48","author":"Karypis","year":"1998","journal-title":"J. Parallel Distributed Comput."},{"key":"2023071709115995400_ref9","first-page":"1222","volume-title":"Proceedings of SIGKDD, Beijing, China, 12-16 August","author":"Stanton","year":"2012"},{"key":"2023071709115995400_ref10","first-page":"183","volume-title":"Proceedings of CCGRID, Washington, DC, USA, 1-4 May","author":"Zhang","year":"2018"},{"key":"2023071709115995400_ref11","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","article-title":"Recent advances in graph partitioning","volume":"9220","author":"Buluas","year":"2016","journal-title":"Algorithm Engineering, LNCS"},{"key":"2023071709115995400_ref12","first-page":"333","volume-title":"Proceedings of WSDM, New York, NY, USA, 24-28 February","author":"Tsourakakis","year":"2014"},{"key":"2023071709115995400_ref13","first-page":"1","volume-title":"Proceedings of ACSW, Sydney, NSW, Australia, 29-31 January","author":"Patwary","year":"2019"},{"key":"2023071709115995400_ref14","first-page":"1106","volume-title":"Proceedings of SIGKDD, Chicago, IL, USA, 11-14 August","author":"Nishimura","year":"2013"},{"key":"2023071709115995400_ref15","doi-asserted-by":"crossref","first-page":"1288","DOI":"10.1109\/9.940936","article-title":"A convergence analysis of generalized hill climbing algorithms","volume":"46","author":"Sullivan","year":"1999","journal-title":"IEEE Trans. Autom. Control."},{"key":"2023071709115995400_ref16","first-page":"17","volume-title":"Proceedings of OSDI 12, Hollywood, CA, USA, 8-10 October","author":"Gonzalez","year":"2012"},{"key":"2023071709115995400_ref17","first-page":"1","volume-title":"IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, 8-13 July","author":"Hernando","year":"2018"},{"key":"2023071709115995400_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2021.3090373","article-title":"Edge repartitioning via structure-aware group migration","author":"Li","year":"2021","journal-title":"IEEE Trans. Comput. Soc. Syst., online"},{"key":"2023071709115995400_ref19","first-page":"18","volume-title":"Proceedings of BigData Congress, San Francisco, CA, USA, June 27 - July 2","author":"Abdolrashidi","year":"2016"},{"key":"2023071709115995400_ref20","doi-asserted-by":"crossref","first-page":"540","DOI":"10.14778\/2904483.2904486","article-title":"Leopard: Lightweight edge-oriented partitioning and replication for dynamic graphs","volume":"9","author":"Huang","year":"2016","journal-title":"Proc. VLDB Endow."},{"key":"2023071709115995400_ref21","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/3078597.3078606","volume-title":"Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing (HPDC), Washington, DC, USA, 26-30 June","author":"Dai","year":"2017"},{"key":"2023071709115995400_ref22","first-page":"458","volume-title":"Proceedings of Supercomputing\u201994, Washington, DC, USA, 14-18 November","author":"Ou","year":"1994"},{"key":"2023071709115995400_ref23","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.14778\/3389133.3389142","article-title":"Incrementalization of graph partitioning algorithms","volume":"13","author":"Fan","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"2023071709115995400_ref24","first-page":"144","volume-title":"Proceedings of ICDCS, Madrid, Spain, June 30 - July 3","author":"Vaquero","year":"2014"},{"key":"2023071709115995400_ref25","first-page":"25","volume-title":"Proceedings of EDBT, Brussels, Belgium, 23-27 March","author":"Nicoara","year":"2015"},{"author":"Neubauer","key":"2023071709115995400_ref26"},{"key":"2023071709115995400_ref27","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1587\/transinf.2020EDL8018","article-title":"An efficient method for graph repartitioning in distributed environments","volume":"E103-D","author":"Li","year":"2020","journal-title":"IEICE Trans.Inf. Syst."},{"key":"2023071709115995400_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2021.3070194","article-title":"A two-phase method to balance the result of distributed graph repartitioning","author":"Li","year":"2021","journal-title":"IEEE Transactions on Big Data, online."},{"key":"2023071709115995400_ref29","first-page":"359","article-title":"A class of convergent generalized hill climbing algorithms","volume":"125","author":"Johnson","year":"2002","journal-title":"Appl. Math Comput."},{"key":"2023071709115995400_ref30","first-page":"313","volume-title":"First International Conference on Future Information Networks, Beijing, China, 14-17 October","author":"Pang","year":"2009"},{"key":"2023071709115995400_ref31","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.76.036106","article-title":"Near linear time algorithm to detect community structures in large-scale networks","volume":"76","author":"Raghavan","year":"2007","journal-title":"Phys. Rev. E"},{"volume-title":"The underlying principle of priorityqueue","author":"Iyelaoi","key":"2023071709115995400_ref32"},{"volume-title":"Stanford large network dataset collection","author":"Jure","key":"2023071709115995400_ref33"},{"volume-title":"The network data repository with interactive graph analytics and visualization","author":"Ryan","key":"2023071709115995400_ref34"},{"key":"2023071709115995400_ref35","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1761\/50876378\/bxac039.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/7\/1761\/50876378\/bxac039.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T09:18:59Z","timestamp":1689585539000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/7\/1761\/6566842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,12]]},"references-count":35,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,4,12]]},"published-print":{"date-parts":[[2023,7,13]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac039","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2022,4,12]]}}}