{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:26Z","timestamp":1773895286167,"version":"3.50.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["ERC 652976"],"award-info":[{"award-number":["ERC 652976"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Society Wolfson Research Merit Award","award":["WRM\/R1\/180014"],"award-info":[{"award-number":["WRM\/R1\/180014"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s00778-022-00736-2","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T19:08:21Z","timestamp":1649704101000},"page":"149-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Application-driven graph partitioning"],"prefix":"10.1007","volume":"32","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[]},{"given":"Ruiqi","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3398-8345","authenticated-orcid":false,"given":"Qiang","family":"Yin","sequence":"additional","affiliation":[]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"736_CR1","unstructured":"Gunrock. https:\/\/github.com\/gunrock\/gunrock\/tree\/master\/ examples (2020)"},{"key":"736_CR2","unstructured":"Livejournal. http:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html (2009)"},{"key":"736_CR3","unstructured":"Traffic. http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml (2010)"},{"key":"736_CR4","unstructured":"Twitter. http:\/\/twitter.com\/ (2012)"},{"key":"736_CR5","unstructured":"UKWeb. http:\/\/law.di.unimi.it\/webdata\/uk union-2006-06-2007-05 (2006)"},{"key":"736_CR6","unstructured":"Graphscope. https:\/\/graphscope.io\/ (2020)"},{"key":"736_CR7","doi-asserted-by":"crossref","unstructured":"Andreev, K., Racke, H.: Balanced graph partitioning. TCS 39(6): 929\u2013939 (2006)","DOI":"10.1007\/s00224-006-1350-7"},{"issue":"8","key":"736_CR8","first-page":"906","volume":"12","author":"D Avdiukhin","year":"2019","unstructured":"Avdiukhin, D., Pupyrev, S., Yaroslavtsev, G.: Multi-dimensional balanced graph partitioning via projected gradient descent. PVLDB 12(8), 906\u2013919 (2019)","journal-title":"PVLDB"},{"key":"736_CR9","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications. Springer (2008)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"736_CR10","doi-asserted-by":"crossref","unstructured":"Bichot, C.E., Siarry, P.: Graph Partitioning. Wiley (2013)","DOI":"10.1002\/9781118601181"},{"key":"736_CR11","unstructured":"Bishop, C.M.: Pattern Recognition and Machine Learning. Springer (2006)"},{"key":"736_CR12","doi-asserted-by":"crossref","unstructured":"Bourse, F., Lelarge, M., Vojnovic, M.: Balanced graph edge partition. In: SIGKDD, pp. 1456\u20131465 (2014)","DOI":"10.1145\/2623330.2623660"},{"key":"736_CR13","doi-asserted-by":"crossref","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. In: WWW, pp. 107\u2013117 (1998)","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"736_CR14","doi-asserted-by":"crossref","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Algorithm Engineering\u2014Selected Results and Surveys, pp. 117\u2013158 (2016)","DOI":"10.1007\/978-3-319-49487-6_4"},{"issue":"1","key":"736_CR15","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.compeleceng.2013.11.024","volume":"40","author":"G Chandrashekar","year":"2014","unstructured":"Chandrashekar, G., Sahin, F.: A survey on feature selection methods. Comput. Electr. Eng. 40(1), 16\u201328 (2014)","journal-title":"Comput. Electr. Eng."},{"key":"736_CR16","doi-asserted-by":"crossref","unstructured":"Chen, R., Shi, J., Chen, Y., Chen, H.: PowerLyra: differentiated graph computation and partitioning on skewed graphs. In: EuroSys, pp. 1:1\u20131:15 (2015)","DOI":"10.1145\/2741948.2741970"},{"issue":"3","key":"736_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"736_CR18","doi-asserted-by":"crossref","unstructured":"Cukierski, W., Hamner, B., Yang, B.: Graph-based features for supervised link prediction. In: INCC, pp. 1237\u20131244. IEEE (2011)","DOI":"10.1109\/IJCNN.2011.6033365"},{"key":"736_CR19","doi-asserted-by":"crossref","unstructured":"Dai, D., Zhang, W., Chen, Y.: IOGP: An incremental online graph partitioning algorithm for distributed graph databases. In: HPDC, pp. 219\u2013230 (2017)","DOI":"10.1145\/3078597.3078606"},{"key":"736_CR20","doi-asserted-by":"crossref","unstructured":"Fan, W., Jin, R., Liu, M., Lu, P., Luo, X., Xu, R., Yin, Q., Yu, W., Zhou, J.: Application driven graph partitioning. In: SIGMOD, pp. 1765\u20131779. ACM (2020)","DOI":"10.1145\/3318464.3389745"},{"key":"736_CR21","doi-asserted-by":"crossref","unstructured":"Fan, W., Liu, M., Lu, P., Yin, Q.: Graph algorithms with partition transparency. IEEE Trans Knowl data Eng pp. 1\u20131 (2021). https:\/\/doi.org\/10.1109\/TKDE.2021.3097998","DOI":"10.1109\/TKDE.2021.3097998"},{"key":"736_CR22","doi-asserted-by":"crossref","unstructured":"Fan, W., Yu, W., Xu, J., Zhou, J., Luo, X., Yin, Q., Lu, P., Cao, Y., Xu, R.: Parallelizing sequential graph computations. TODS 43(4), 18:1-18:39 (2018)","DOI":"10.1145\/3282488"},{"key":"736_CR23","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)"},{"key":"736_CR24","unstructured":"Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs. In: OSDI, pp. 17\u201330 (2012)"},{"key":"736_CR25","doi-asserted-by":"crossref","unstructured":"Huang, J., Abadi, D.: LEOPARD: lightweight edge-oriented partitioning and replication for dynamic graphs. proc. VLDB endow. 9(7): 540\u2013551(2016)","DOI":"10.14778\/2904483.2904486"},{"key":"736_CR26","unstructured":"Huang, L., Jia, J., Yu, B., gon Chun, B., Maniatis, P., Naik, M.: Predicting execution time of computer programs using sparse polynomial regression. In: NIPS (2010)"},{"issue":"4","key":"736_CR27","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"736_CR28","doi-asserted-by":"crossref","unstructured":"Jain, N., Liao, G., Willke, T.L.: Graphbuilder: scalable graph ETL framework. Graph Data Manag. Exp. Syst. pp. 1\u20136 (2013). https:\/\/doi.org\/ 10.1145\/2484425.2484429","DOI":"10.1145\/2484425.2484429"},{"key":"736_CR29","doi-asserted-by":"crossref","unstructured":"Karypis, G.: Metis and parmetis. In: Encyclopedia of Parallel Computing, pp. 1117\u20131124 (2011)","DOI":"10.1007\/978-0-387-09766-4_500"},{"key":"736_CR30","unstructured":"Karypis, G., Kumar, V.: Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0. pp. 1\u201316 (1995)"},{"key":"736_CR31","unstructured":"Karypis, G., Kumar, V.: METIS a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4. pp. 1\u201344 (1998)"},{"issue":"1","key":"736_CR32","first-page":"96","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevelk-way partitioning scheme for irregular graphs. JPDC 48(1), 96\u2013129 (1998)","journal-title":"JPDC"},{"key":"736_CR33","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.datak.2011.11.004","volume":"72","author":"M Kim","year":"2012","unstructured":"Kim, M., Candan, K.S.: SBV-Cut: vertex-cut based graph partitioning using structural balance vertices. DKE 72, 285\u2013303 (2012)","journal-title":"DKE"},{"key":"736_CR34","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Naor, J., Schwartz, R.: Partitioning graphs into balanced components. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.102"},{"issue":"8","key":"736_CR35","first-page":"891","volume":"12","author":"D Li","year":"2019","unstructured":"Li, D., Zhang, Y., Wang, J., Tan, K.: TopoX: topology refactorization for efficient graph partitioning and processing. PVLDB 12(8), 891\u2013905 (2019)","journal-title":"PVLDB"},{"key":"736_CR36","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: CIKM (2003)","DOI":"10.1145\/956863.956972"},{"key":"736_CR37","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: SIGMOD (2010)","DOI":"10.1145\/1583991.1584010"},{"issue":"12","key":"736_CR38","first-page":"1478","volume":"8","author":"DW Margo","year":"2015","unstructured":"Margo, D.W., Seltzer, M.I.: A scalable distributed graph partitioner. PVLDB 8(12), 1478\u20131489 (2015)","journal-title":"PVLDB"},{"key":"736_CR39","doi-asserted-by":"crossref","unstructured":"Mondal, J., Deshpande, A.: Managing large dynamic graphs efficiently. In: SIGMOD, pp. 145\u2013156 (2012)","DOI":"10.1145\/2213836.2213854"},{"issue":"1","key":"736_CR40","doi-asserted-by":"publisher","first-page":"2566","DOI":"10.1073\/pnas.012582999","volume":"99","author":"ME Newman","year":"2002","unstructured":"Newman, M.E., Watts, D.J., Strogatz, S.H.: Random graph models of social networks. Proc. Natl. Acad. Sci. 99(1), 2566\u20132572 (2002)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"736_CR41","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0167-7152(98)00088-1","volume":"40","author":"H Park","year":"1998","unstructured":"Park, H., Stefanski, L.: Relative-error prediction. Stat. Probab. Lett. 40(3), 227\u2013236 (1998)","journal-title":"Stat. Probab. Lett."},{"key":"736_CR42","unstructured":"Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in PyTorch. In: NIPS Autodiff Workshop (2017)"},{"key":"736_CR43","doi-asserted-by":"crossref","unstructured":"Petroni, F., Querzoni, L., Daudjee, K., Kamali, S., Iacoboni, G.: HDRF: stream-based partitioning for power-law graphs. In: CIKM (2015)","DOI":"10.1145\/2806416.2806424"},{"issue":"3","key":"736_CR44","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIMAX 11(3), 430\u2013452 (1990)","journal-title":"SIMAX"},{"key":"736_CR45","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of np. In: STOC, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"736_CR46","unstructured":"Slota, G.M., Rajamanickam, S., Madduri, K.: Pulp\/xtrapulp: partitioning tools for extreme-scale graphs. Tech. Rep., Sandia National Lab.(SNL-NM), Albuquerque, NM (United States) (2017)"},{"key":"736_CR47","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Gkantsidis, C., Radunovic, B., Vojnovic, M.: FENNEL: streaming graph partitioning for massive scale graphs. In: WSDM, pp. 333\u2013342 (2014)","DOI":"10.1145\/2556195.2556213"},{"key":"736_CR48","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","DOI":"10.1145\/79173.79181"},{"key":"736_CR49","doi-asserted-by":"crossref","unstructured":"Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., Owens, J.D.: Gunrock: a high-performance graph processing library on the GPU. In: Proceedings of the 21st ACM SIGPLAN symposium on principles and practice of parallel programming, pp. 1\u201312 (2016)","DOI":"10.1145\/2851141.2851145"},{"key":"736_CR50","doi-asserted-by":"crossref","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440 (1998)","DOI":"10.1038\/30918"},{"key":"736_CR51","unstructured":"Wikipedia: Stone-Weierstrass Theorem. https:\/\/en.wikipedia.org\/wiki\/Stone-Weierstrass_theorem"},{"key":"736_CR52","doi-asserted-by":"crossref","unstructured":"Yang, S., Yan, X., Zong, B., Khan, A.: Towards effective partition management for large graphs. In: SIGMOD, p. 517 (2012)","DOI":"10.1145\/2213836.2213895"},{"key":"736_CR53","doi-asserted-by":"crossref","unstructured":"Zhang, C., Wei, F., Liu, Q., Tang, Z.G., Li, Z.: Graph edge partitioning via neighborhood heuristic. In: KDD (2017)","DOI":"10.1145\/3097983.3098033"},{"key":"736_CR54","unstructured":"Zhu, X., Chen, W., Zheng, W., Ma, X.: Gemini: a computation-centric distributed graph processing system. In: OSDI, pp. 301\u2013316 (2016)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00736-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00736-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00736-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:10:24Z","timestamp":1673953824000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00736-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,11]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["736"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00736-2","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,11]]},"assertion":[{"value":"27 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}