{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T02:05:35Z","timestamp":1762999535262},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T00:00:00Z","timestamp":1577750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,1]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>The paper provides statistical theory and intuition for personalized PageRank (called \u2018PPR\u2019): a popular technique that samples a small community from a massive network. We study a setting where the entire network is expensive to obtain thoroughly or to maintain, but we can start from a seed node of interest and \u2018crawl\u2019 the network to find other nodes through their connections. By crawling the graph in a designed way, the PPR vector can be approximated without querying the entire massive graph, making it an alternative to snowball sampling. Using the degree-corrected stochastic block model, we study whether the PPR vector can select nodes that belong to the same block as the seed node. We provide a simple and interpretable form for the PPR vector, highlighting its biases towards high degree nodes outside the target block. We examine a simple adjustment based on node degrees and establish consistency results for PPR clustering that allows for directed graphs. These results are enabled by recent technical advances showing the elementwise convergence of eigenvectors. We illustrate the method with the massive Twitter friendship graph, which we crawl by using the Twitter application programming interface. We find that the adjusted and unadjusted PPR techniques are complementary approaches, where the adjustment makes the results particularly localized around the seed node, and that the bias adjustment greatly benefits from degree regularization.<\/jats:p>","DOI":"10.1111\/rssb.12349","type":"journal-article","created":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T09:40:26Z","timestamp":1577785226000},"page":"99-126","source":"Crossref","is-referenced-by-count":7,"title":["Targeted Sampling from Massive Block Model Graphs with Personalized PageRank"],"prefix":"10.1093","volume":"82","author":[{"given":"Fan","family":"Chen","sequence":"first","affiliation":[{"name":"University of Wisconsin\u2014Madison \u00a0 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yini","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Wisconsin\u2014Madison \u00a0 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karl","family":"Rohe","sequence":"additional","affiliation":[{"name":"University of Wisconsin\u2014Madison \u00a0 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,12,31]]},"reference":[{"key":"2023022408362947000_","first-page":"1981","article-title":"Mixed membership stochastic blockmodels","volume":"9","author":"Airoldi","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"2023022408362947000_","first-page":"18","volume-title":"Proc. 10th Int. Conf. Data Mining","author":"Alamgir","year":"2010"},{"key":"2023022408362947000_","first-page":"475","volume-title":"Proc. 47th A. Symp. Foundations of Computer Science","author":"Andersen","year":"2006"},{"key":"2023022408362947000_","first-page":"223","volume-title":"Proc. 15th Int. Conf. World Wide Web, Edinburgh","author":"Andersen","year":"2006"},{"key":"2023022408362947000_","first-page":"235","volume-title":"Proc. Symp. Theory of Computing, Bethesda","author":"Andersen","year":"2009"},{"key":"2023022408362947000_","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":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1080\/15427951.2006.10129116","article-title":"Bookmark-coloring algorithm for personalized pagerank computing","volume":"3","author":"Berkhin","year":"2006","journal-title":"Internet Math."},{"key":"2023022408362947000_","first-page":"107","volume-title":"Proc. Int. Conf. World Wide Web","author":"Brin","year":"1998"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"2204","DOI":"10.1214\/18-AOS1745","article-title":"Spectral method and regularized MLE are both optimal for top-K ranking","volume":"47","author":"Chen","year":"2019","journal-title":"Ann. Statist."},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0707001","article-title":"The rotation of eigenvectors by a perturbation: iii","volume":"7","author":"Davis","year":"1970","journal-title":"SIAM J. Numer. Anal."},{"key":"2023022408362947000_","article-title":"\u00dcber Matrizen aus Nicht Negativen Elementen","volume-title":"K\u00f6nigliche Akademie der Wissenschaften","author":"Frobenius","year":"1912"},{"key":"2023022408362947000_","first-page":"187","volume-title":"Proc. 53rd A. Symp. Foundations of Computer Science","author":"Gharan","year":"2012"},{"key":"2023022408362947000_","article-title":"Ranking stability and super-stable nodes in complex networks","volume":"2","author":"Ghoshal","year":"2011","journal-title":"Nat. Communs"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1137\/140976649","article-title":"Pagerank beyond the web","volume":"57","author":"Gleich","year":"2015","journal-title":"SIAM Rev."},{"key":"2023022408362947000_","first-page":"505","volume-title":"Proc. 22nd Int. Conf. World Wide Web","author":"Gupta","year":"2013"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1109\/TKDE.2003.1208999","article-title":"Topic-sensitive pagerank: a context-sensitive ranking algorithm for web search","volume":"15","author":"Haveliwala","year":"2003","journal-title":"IEEE Trans. Knowl. Data Engng"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: first steps","volume":"5","author":"Holland","year":"1983","journal-title":"Socl Netwrks"},{"key":"2023022408362947000_","first-page":"271","volume-title":"Proc. 12th Int. Conf. World Wide Web, Budapest","author":"Jeh","year":"2003"},{"key":"2023022408362947000_","article-title":"Stochastic blockmodels and community structure in networks","volume":"83","author":"Karrer","year":"2011","journal-title":"Phys. Rev."},{"key":"2023022408362947000_","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. Para. Distrbtd Comput."},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1073\/pnas.1611275114","article-title":"Block models and personalized PageRank","volume":"114","author":"Kloumann","year":"2017","journal-title":"Proc. Natn. Acad. Sci. USA"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1214\/15-AOS1360","article-title":"Optimization via low-rank approximation for community detection in networks","volume":"44","author":"Le","year":"2016","journal-title":"Ann. Statist."},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"Isorankn: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023022408362947000_","first-page":"1","volume-title":"Combinatorics, Paul Erdos is Eighty","author":"Lov\u00e1sz","year":"1993"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1214\/13-EJS772","article-title":"Respondent-driven sampling on directed networks","volume":"7","author":"Lu","year":"2013","journal-title":"Electron. J. Statist."},{"key":"2023022408362947000_","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-10-283","article-title":"RRW: repeated random walks on genome-scale protein networks for local cluster discovery","volume":"10","author":"Macropol","year":"2009","journal-title":"BMC Bioinform."},{"key":"2023022408362947000_","volume-title":"The Structure and Dynamics of Networks","author":"Newman","year":"2006"},{"key":"2023022408362947000_","volume-title":"The pagerank citation ranking: bringing order to the web. Technical Report.","author":"Page","year":"1999"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/BF01449896","article-title":"Zur Theorie der Matrices","volume":"64","author":"Perron","year":"1907","journal-title":"Math. Ann."},{"key":"2023022408362947000_","first-page":"3120","volume-title":"Proc. 26th Int. Conf. Advances in Neural Information Processing Systems, Lake Tahoe","author":"Qin","year":"2013"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"1878","DOI":"10.1214\/11-AOS887","article-title":"Spectral clustering and the high-dimensional stochastic blockmodel","volume":"39","author":"Rohe","year":"2011","journal-title":"Ann. Statist."},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1111\/rssb.12245","article-title":"A block model for node popularity in networks with community structure","volume":"80","author":"Sengupta","year":"2018","journal-title":"J. R. Statist. Soc."},{"key":"2023022408362947000_","first-page":"96","volume-title":"Proc. 37th A. Symp. Foundations of Computer Science","author":"Spielman","year":"1996"},{"key":"2023022408362947000_","first-page":"81","volume-title":"Proc. 36th A. Symp. Theory of Computing","author":"Spielman","year":"2004"},{"key":"2023022408362947000_","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"2023022408362947000_","first-page":"1","article-title":"Oriented and degree-generated block models: generating and inferring communities with inhomogeneous degree distributions","volume":"2","author":"Zhu","year":"2013","journal-title":"J. Complx Netwrks"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Frssb.12349","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/82\/1\/99\/49321248\/jrsssb_82_1_99.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/82\/1\/99\/49321248\/jrsssb_82_1_99.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T14:11:04Z","timestamp":1695564664000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/82\/1\/99\/7056073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,31]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,12,31]]},"published-print":{"date-parts":[[2020,2,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12349","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,2]]},"published":{"date-parts":[[2019,12,31]]}}}