{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T17:02:27Z","timestamp":1781110947963,"version":"3.54.1"},"reference-count":39,"publisher":"National Academy of Sciences","issue":"1","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"vor","delay-in-days":182,"URL":"http:\/\/www.pnas.org\/site\/misc\/userlicense.xhtml"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons Investigator Award"],"award-info":[{"award-number":["Simons Investigator Award"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"DOD | Army Research Office","doi-asserted-by":"publisher","award":["MURI grant"],"award-info":[{"award-number":["MURI grant"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005801","name":"Facebook","doi-asserted-by":"publisher","award":["Faculty Research Grant"],"award-info":[{"award-number":["Faculty Research Grant"]}],"id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Focused Research Award"],"award-info":[{"award-number":["Focused Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"David Morgenthaler","award":["Faculty Fellowship"],"award-info":[{"award-number":["Faculty Fellowship"]}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2017,1,3]]},"abstract":"<jats:title>Significance<\/jats:title>\n                  <jats:p>Methods based on PageRank have been fundamental to work on identifying communities in networks, but, to date, there has been little formal basis for the effectiveness of these methods. We establish a surprising connection between the personalized PageRank algorithm and the stochastic block model for random graphs, showing that personalized PageRank, in fact, provides the optimal geometric discriminant function for separating the communities in stochastic block models over a wide class of functions. Building on this result, we develop stronger classifiers that, although scalable, are competitive with computationally much more demanding methods such as belief propagation.<\/jats:p>","DOI":"10.1073\/pnas.1611275114","type":"journal-article","created":{"date-parts":[[2016,12,20]],"date-time":"2016-12-20T21:00:29Z","timestamp":1482267629000},"page":"33-38","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":55,"title":["Block models and personalized PageRank"],"prefix":"10.1073","volume":"114","author":[{"given":"Isabel M.","family":"Kloumann","sequence":"first","affiliation":[{"name":"Center for Applied Mathematics, Cornell University, Ithaca, NY 14853;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johan","family":"Ugander","sequence":"additional","affiliation":[{"name":"Department of Management Science &amp; Engineering, Stanford University, Stanford, CA 94305;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY 14853"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2016,12,20]]},"reference":[{"key":"e_1_3_3_1_2","unstructured":"L Page S Brin R Motwani T Winograd The PageRank citation ranking: Bringing order to the web. Technical Report (Stanford InfoLab Stanford CA). (1998)."},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/140976649"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135814"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/05\/P05001"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1514888.1514890"},{"key":"e_1_3_3_8_2","unstructured":"J Riedy DA Bader K Jiang P Pande R Sharma Detecting communities from given seeds in social networks. Technical Report GT-CSE-11-01 (Georgia Institute of Technology Atlanta). (2011)."},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"2099","DOI":"10.1145\/2505515.2505535","volume-title":"Proceedings of the 22nd ACM International Conference on Information & Knowledge Management","author":"Whang JJ","year":"2013","unstructured":"JJ Whang, DF Gleich, IS Dhillon, Overlapping community detection using seed set expansion. Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (American Association for Computing Machinery, New York), pp. 2099\u20132108 (2013)."},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","unstructured":"J Yang J Leskovec Defining and evaluating network communities based on ground-truth. Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics (American Association for Computing Machinery New York) Article No 3. (2012).","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623621"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0708838104"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623706"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-1809.1936.tb02137.x"},{"key":"e_1_3_3_17_2","unstructured":"SD Kamvar TH Haveliwala CD Manning GH Golub Exploiting the block structure of the Web for computing PageRank. Technical Report. (Stanford University Stanford CA). (2003)."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_3_3_19_2","first-page":"346","volume-title":"Proceedings of the 31st Annual Symposium on Foundations of Computer Science","author":"Lov\u00e1sz L","year":"1990","unstructured":"L Lov\u00e1sz, M Simonovits, The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. Proceedings of the 31st Annual Symposium on Foundations of Computer Science (American Association for Computing Machinery, New York) Vol 1, 346\u2013354 (1990)."},{"key":"e_1_3_3_20_2","first-page":"475","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"Andersen R","year":"2006","unstructured":"R Andersen, F Chung, K Lang, Local graph partitioning using PageRank vectors. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (American Association for Computing Machinery, New York), pp. 475\u2013486 (2006)."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10390643"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_3_3_23_2","first-page":"121","volume-title":"Proceedings of the 28th International Conference on Machine Learning","author":"Mahoney MW","year":"2011","unstructured":"MW Mahoney, L Orecchia, Implementing regularization implicitly via approximate eigenvector computation. Proceedings of the 28th International Conference on Machine Learning (International Machine Learning Society, Bellevue, WA), pp. 121\u2013128 (2011)."},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/1055558.1055579","volume-title":"Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database System","author":"Zhou H","year":"2004","unstructured":"H Zhou, D Woodruff, Clustering via matrix powering. Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database System (American Association for Computing Machinery, New York), pp. 136\u2013142 (2004)."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2817946.2817950"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erd\u0151s P","year":"1959","unstructured":"P Erd\u0151s, A R\u00e9nyi, On random graphs. Publ Math Debrecen 6, 290\u2013297 (1959).","journal-title":"Publ Math Debrecen"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1982.10477895"},{"key":"e_1_3_3_31_2","volume-title":"Spectral Graph Theory","author":"Chung FRK","year":"1997","unstructured":"FRK Chung Spectral Graph Theory (American Mathematical Society, New York, 1997)."},{"key":"e_1_3_3_32_2","first-page":"1423","volume-title":"Proceedings of the 28th Conference on Learning Theory, JMLR Workshop and Conference Proceedings","author":"Peng R","year":"2015","unstructured":"R Peng, H Sun, L Zanetti, Partitioning well-clustered graphs: Spectral clustering works! Proceedings of the 28th Conference on Learning Theory, JMLR Workshop and Conference Proceedings (JMLR Inc, Lafayette, LA) Vol 40, 1423\u20131455 (2015)."},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1109\/SFCS.2001.959929","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science","author":"McSherry F","year":"2001","unstructured":"F McSherry, Spectral partitioning of random graphs. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (American Association for Computing Machinery, New York), pp. 529 (2001)."},{"key":"e_1_3_3_34_2","unstructured":"L Becchetti AEF Clementi E Natale F Pasquale L Trevisan Find your place: Simple distributed algorithms for community detection. arXiv:1511.03927. (2015)."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_3_36_2","first-page":"1","volume-title":"Proceedings of the 27th Conference on Learning Theory, JMLR: Workshop and Conference Proceedings","author":"Mossel E","year":"2014","unstructured":"E Mossel, J Neeman, A Sly, Belief propagation, robust reconstruction, and optimal recovery of block models. Proceedings of the 27th Conference on Learning Theory, JMLR: Workshop and Conference Proceedings (JMLR Inc, Lafayette, LA) Vol 35, 1\u201315 (2014)."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1409770111"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"},{"key":"e_1_3_3_39_2","first-page":"406","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems","author":"Saade A","year":"2014","unstructured":"A Saade, F Krzakala, L Zdeborov\u00e1, Spectral clustering of graphs with the Bethe Hessian. Proceedings of the 27th International Conference on Neural Information Processing Systems (American Association for Computing Machinery, New York), pp. 406\u2013414 (2014)."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1611275114","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1611275114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T07:06:46Z","timestamp":1692601606000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1611275114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,20]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,3]]}},"alternative-id":["10.1073\/pnas.1611275114"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1611275114","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,20]]},"assertion":[{"value":"2016-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}