{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T18:53:54Z","timestamp":1770836034615,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T00:00:00Z","timestamp":1548115200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2019,11]]},"DOI":"10.1007\/s10115-019-01328-3","type":"journal-article","created":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T01:52:13Z","timestamp":1548294733000},"page":"847-871","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["PPR-partitioning: a distributed graph partitioning algorithm based on the personalized PageRank vectors in vertex-centric systems"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6061-714X","authenticated-orcid":false,"given":"Nasrin","family":"Mazaheri\u00a0Soudani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1184-5917","authenticated-orcid":false,"given":"Afsaneh","family":"Fatemi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4374-9228","authenticated-orcid":false,"given":"Mohammadali","family":"Nematbakhsh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,22]]},"reference":[{"key":"1328_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert R, Barab\u00e1si A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74:47\u201397","journal-title":"Rev Mod Phys"},{"key":"1328_CR2","doi-asserted-by":"crossref","unstructured":"Andersen R, Chung F, Lang K (2006) Local graph partitioning using PageRank vectors. In: 47th annual IEEE symposium on foundations of computer science (FOCS\u201906), pp 475\u2013486","DOI":"10.1109\/FOCS.2006.44"},{"issue":"1\u20132","key":"1328_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1080\/15427951.2008.10129297","volume":"5","author":"R Andersen","year":"2008","unstructured":"Andersen R, Chung F, Lang K (2008) Local partitioning for directed graphs using pagerank. Internet Math. 5(1\u20132):3\u201322","journal-title":"Internet Math."},{"issue":"3","key":"1328_CR4","first-page":"5","volume":"11","author":"C Avery","year":"2011","unstructured":"Avery C (2011) Giraph: large-scale graph processing infrastructure on hadoop. Proc Hadoop Summit Santa Clara 11(3):5\u20139","journal-title":"Proc Hadoop Summit Santa Clara"},{"issue":"2","key":"1328_CR5","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1137\/050643799","volume":"45","author":"K Avrachenkov","year":"2007","unstructured":"Avrachenkov K, Litvak N, Nemirovsky D, Osipova N (2007) Monte carlo methods in pagerank computation: when one iteration is sufficient. SIAM J Numer Anal 45(2):890\u2013904","journal-title":"SIAM J Numer Anal"},{"key":"1328_CR6","doi-asserted-by":"crossref","unstructured":"Aydin K, Bateni M, Mirrokni V (2016) Distributed balanced partitioning via linear embedding. In: Proceedings of the 9th international conference on web search and data mining, WSDM\u201916. ACM, pp 387\u2013396","DOI":"10.1145\/2835776.2835829"},{"issue":"3","key":"1328_CR7","doi-asserted-by":"publisher","first-page":"173","DOI":"10.14778\/1929861.1929864","volume":"4","author":"B Bahmani","year":"2010","unstructured":"Bahmani B, Chowdhury A, Goel A (2010) Fast incremental and personalized pagerank. Proc VLDB Endow 4(3):173\u2013184","journal-title":"Proc VLDB Endow"},{"key":"1328_CR8","doi-asserted-by":"publisher","unstructured":"Bulu\u00e7 A, Meyerhenke H, Safro I, Sanders P, Schulz C (2016) Recent advances in graph partitioning. In: Kliemann L, Sanders P (eds) Algorithm engineering: selected results and surveys, vol 9220. Springer, Cham, pp 117\u2013158. \n                    https:\/\/doi.org\/10.1007\/978-3-319-49487-6_4","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"1328_CR9","doi-asserted-by":"crossref","unstructured":"Chen R, Shi J, Chen Y, Chen H (2015) PowerLyra: differentiated graph computation and partitioning on skewed graphs. In: Proceedings of the 10th European conference on computer systems, EuroSys \u201915. ACM, pp 1:1\u20131:15","DOI":"10.1145\/2741948.2741970"},{"issue":"Supplement C","key":"1328_CR10","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ejc.2017.07.013","volume":"68","author":"F Chung","year":"2018","unstructured":"Chung F, Simpson O (2018) Computing heat kernel pagerank and a local clustering algorithm. Eur J Comb 68(Supplement C):96\u2013119","journal-title":"Eur J Comb"},{"issue":"2","key":"1328_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2","volume":"18","author":"A Condon","year":"2001","unstructured":"Condon A, Karp RM (2001) Algorithms for graph partitioning on the planted partition model. Random Struct Algorithms 18(2):116\u2013140","journal-title":"Random Struct Algorithms"},{"issue":"1","key":"1328_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S (2008) Mapreduce: simplified data processing on large clusters. Commun ACM 51(1):107\u2013113","journal-title":"Commun ACM"},{"issue":"11","key":"1328_CR13","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1109\/TPAMI.2007.1115","volume":"29","author":"IS Dhillon","year":"2007","unstructured":"Dhillon IS, Guan Y, Kulis B (2007) Weighted graph cuts without eigenvectors a multilevel approach. IEEE Trans Pattern Anal Mach Intell 29(11):1944\u20131957","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"3","key":"1328_CR14","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1080\/15427951.2005.10129104","volume":"2","author":"D Fogaras","year":"2005","unstructured":"Fogaras D, Rcz B, Csalogny K, Sarls T (2005) Towards scaling fully personalized pagerank: algorithms, lower bounds, and experiments. Internet Math 2(3):333\u2013358","journal-title":"Internet Math"},{"key":"1328_CR15","unstructured":"Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) PowerGraph: distributed graph-parallel computation on natural graphs. In: Proceedings of 10th USENIX symposium on operating systems design and implementation (OSDI), vol 12, pp 17\u201330"},{"issue":"3","key":"1328_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TPAMI.2006.57","volume":"28","author":"L Grady","year":"2006","unstructured":"Grady L, Schwartz EL (2006) Isoperimetric graph partitioning for image segmentation. IEEE Trans Pattern Anal Mach Intell 28(3):469\u2013475","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"1328_CR17","doi-asserted-by":"crossref","unstructured":"Guerrieri Alessio MA (2015) DFEP: distributed funding-based edge partitioning. In: Euro-Par: 21st international conference on parallel and distributed computing. Springer, Berlin, pp 346\u2013358","DOI":"10.1007\/978-3-662-48096-0_27"},{"key":"1328_CR18","doi-asserted-by":"crossref","unstructured":"Guo T, Cao X, Cong G, Lu J, Lin X (2017) Distributed algorithms on exact personalized PageRank. In: Proceedings of the international conference on management of data, SIGMOD \u201917. ACM, pp 479\u2013494","DOI":"10.1145\/3035918.3035920"},{"key":"1328_CR19","doi-asserted-by":"crossref","unstructured":"Jeh G, Widom J (2003) Scaling personalized web search. In: Proceedings of the 12th international conference on world wide web, WWW \u201903. ACM, pp 271\u2013279","DOI":"10.1145\/775152.775191"},{"issue":"1","key":"1328_CR20","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/92.748202","volume":"7","author":"G Karypis","year":"1999","unstructured":"Karypis G, Aggarwal R, Kumar V, Shekhar S (1999) Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans Very Large Scale Integr VLSI Syst 7(1):69\u201379","journal-title":"IEEE Trans Very Large Scale Integr VLSI Syst"},{"issue":"1","key":"1328_CR21","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359\u2013392","journal-title":"SIAM J Sci Comput"},{"key":"1328_CR22","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) KONECT: the Koblenz network collection. In: Proceedings of the 22th international conference on world wide web, WWW \u201913 companion. ACM, pp 1343\u20131350","DOI":"10.1145\/2487788.2488173"},{"key":"1328_CR23","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. \n                    http:\/\/snap.stanford.edu\/data"},{"key":"1328_CR24","doi-asserted-by":"crossref","unstructured":"Lofgren PA, Banerjee S, Goel A, Seshadhri C (2014) FAST-PPR: scaling personalized PageRank estimation for large graphs. In: Proceedings of the 20th SIGKDD international conference on knowledge discovery and data mining, KDD \u201914. ACM, pp 1436\u20131445","DOI":"10.1145\/2623330.2623745"},{"issue":"8","key":"1328_CR25","doi-asserted-by":"publisher","first-page":"716","DOI":"10.14778\/2212351.2212354","volume":"5","author":"Y Low","year":"2012","unstructured":"Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein JM (2012) Distributed graphlab: a framework for machine learning and data mining in the cloud. Proc VLDB Endow 5(8):716\u2013727","journal-title":"Proc VLDB Endow"},{"key":"1328_CR26","doi-asserted-by":"crossref","unstructured":"Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceedings of SIGMOD international conference on management of data, SIGMOD \u201910. ACM, pp 135\u2013146","DOI":"10.1145\/1807167.1807184"},{"key":"1328_CR27","doi-asserted-by":"crossref","unstructured":"Martella C, Logothetis D, Loukas A, Siganos G (2017) Spinner: scalable graph partitioning in the cloud. In: IEEE 33th international conference on data engineering (ICDE), pp 1083\u20131094","DOI":"10.1109\/ICDE.2017.153"},{"key":"1328_CR28","doi-asserted-by":"crossref","unstructured":"McSherry F (2001) Spectral partitioning of random graphs. In: Proceedings IEEE international conference on cluster computing, pp 529\u2013537","DOI":"10.1109\/SFCS.2001.959929"},{"issue":"9","key":"1328_CR29","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.1109\/TPDS.2017.2671868","volume":"28","author":"H Meyerhenke","year":"2017","unstructured":"Meyerhenke H, Sanders P, Schulz C (2017) Parallel graph partitioning for complex networks. IEEE Trans Parallel Distrib Syst 28(9):2625\u20132638","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"1328_CR30","doi-asserted-by":"publisher","unstructured":"Mofrad MH, Melhem R, Hammoud M (2018) Revolver: vertex-centric graph partitioning using reinforcement learning. In: 2018 IEEE 11th international conference on cloud computing (CLOUD), vol 00, pp 818\u2013821. \n                    https:\/\/doi.org\/10.1109\/CLOUD.2018.00111","DOI":"10.1109\/CLOUD.2018.00111"},{"key":"1328_CR31","doi-asserted-by":"publisher","unstructured":"Nishimura J, Ugander J (2013) Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In: Proceedings of the 19th SIGKDD international conference on knowledge discovery and data mining, KDD \u201913. ACM, pp 1106\u20131114. \n                    https:\/\/doi.org\/10.1145\/2487575.2487696","DOI":"10.1145\/2487575.2487696"},{"key":"1328_CR32","unstructured":"Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. Technical report 1999-66, Stanford InfoLab"},{"issue":"1","key":"1328_CR33","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s13278-014-0179-3","volume":"4","author":"B Perozzi","year":"2014","unstructured":"Perozzi B, McCubbin C, Halbert JT (2014) Scalable graph clustering with parallel approximate PageRank. Soc Netw Anal Min 4(1):179","journal-title":"Soc Netw Anal Min"},{"key":"1328_CR34","doi-asserted-by":"crossref","unstructured":"Rahimian F, Payberah AH, Girdzijauskas S, Haridi S (2014) Distributed vertex-cut partitioning. In: IFIP international conference on distributed applications and interoperable systems. Springer, pp 186\u2013200","DOI":"10.1007\/978-3-662-43352-2_15"},{"key":"1328_CR35","doi-asserted-by":"crossref","unstructured":"Rahimian F, Payberah AH, Girdzijauskas S, Jelasity M, Haridi S (2013) JA-BE-JA: a distributed algorithm for balanced graph partitioning. In: IEEE 7th international conference on self-adaptive and self-organizing systems, pp 51\u201360","DOI":"10.1109\/SASO.2013.13"},{"key":"1328_CR36","doi-asserted-by":"crossref","unstructured":"Sajjad HP, Payberah AH, Rahimian F, Vlassov V, Haridi S (2016) Boosting vertex-cut partitioning for streaming graphs. In: IEEE international congress on big data (BigData congress), pp 1\u20138","DOI":"10.1109\/BigDataCongress.2016.10"},{"key":"1328_CR37","doi-asserted-by":"crossref","unstructured":"Sala, A, Cao L, Wilson C, Zablit R, Zheng H, Zhao BY (2010) Measurement-calibrated graph models for social network experiments. In: Proceedings of the 19th international conference on world wide web, WWW \u201910. ACM, pp 861\u2013870","DOI":"10.1145\/1772690.1772778"},{"key":"1328_CR38","doi-asserted-by":"crossref","unstructured":"Spielman DA, Teng S-H (2004) Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the 36th symposium on theory of computing, STOC \u201904. ACM, pp 81\u201390","DOI":"10.1145\/1007352.1007372"},{"issue":"1","key":"1328_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/080744888","volume":"42","author":"DA Spielman","year":"2013","unstructured":"Spielman DA, Teng S-H (2013) A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J Comput 42(1):1\u201326","journal-title":"SIAM J Comput"},{"key":"1328_CR40","doi-asserted-by":"crossref","unstructured":"Stanton I (2014) Streaming balanced graph partitioning algorithms for random graphs. In: Proceedings of the 25th symposium on discrete algorithms. SIAM, pp 1287\u20131301","DOI":"10.1137\/1.9781611973402.95"},{"key":"1328_CR41","doi-asserted-by":"crossref","unstructured":"Stanton I, Kliot G (2012) Streaming graph partitioning for large distributed graphs. In: Proceedings of the 18th SIGKDD international conference on knowledge discovery and data mining, KDD \u201912. ACM, pp 1222\u20131230","DOI":"10.1145\/2339530.2339722"},{"issue":"22","key":"1328_CR42","doi-asserted-by":"publisher","first-page":"5772","DOI":"10.1016\/j.physa.2013.07.021","volume":"392","author":"SA Tabrizi","year":"2013","unstructured":"Tabrizi SA, Shakery A, Asadpour M, Abbasi M, Tavallaie MA (2013) Personalized pagerank clustering: a graph clustering algorithm based on random walks. Phys A Stat Mech Appl 392(22):5772\u20135785","journal-title":"Phys A Stat Mech Appl"},{"key":"1328_CR43","doi-asserted-by":"crossref","unstructured":"Tsourakakis C, Gkantsidis C, Radunovic B, Vojnovic M (2014) Fennel: streaming graph partitioning for massive scale graphs. In: Proceedings of the 7th international conference on web search and data mining, WSDM \u201914. ACM, pp 333\u2013342","DOI":"10.1145\/2556195.2556213"},{"key":"1328_CR44","doi-asserted-by":"crossref","unstructured":"Ugander J, Backstrom L (2013) Balanced label propagation for partitioning massive graphs. In: Proceedings of the 6th international conference on web search and data mining, WSDM \u201913. ACM, pp 507\u2013516","DOI":"10.1145\/2433396.2433461"},{"key":"1328_CR45","doi-asserted-by":"crossref","unstructured":"Wang L, Xiao Y, Shao B, Wang H (2014) How to partition a billion-node graph. In: IEEE 30th international conference on data engineering, pp 568\u2013579","DOI":"10.1109\/ICDE.2014.6816682"},{"issue":"5","key":"1328_CR46","doi-asserted-by":"publisher","first-page":"1272","DOI":"10.1109\/TKDE.2016.2518687","volume":"28","author":"JJ Whang","year":"2016","unstructured":"Whang JJ, Gleich DF, Dhillon IS (2016) Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans Knowl Data Eng 28(5):1272\u20131284","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1328_CR47","unstructured":"Xie C, Li W-J, Zhang Z (2015) S-PowerGraph: streaming graph partitioning for natural graphs by vertex-cut. CoRR \n                    arXiv:1511.02586"},{"issue":"1","key":"1328_CR48","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/s40537-016-0060-5","volume":"3","author":"H Zhang","year":"2016","unstructured":"Zhang H, Raitoharju J, Kiranyaz S, Gabbouj M (2016) Limited random walk algorithm for big graph data clustering. J Big Data 3(1):26","journal-title":"J Big Data"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01328-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-019-01328-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-019-01328-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T20:29:08Z","timestamp":1579638548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-019-01328-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,22]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["1328"],"URL":"https:\/\/doi.org\/10.1007\/s10115-019-01328-3","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,22]]},"assertion":[{"value":"24 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"No funding was received by the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}