{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:05:59Z","timestamp":1792109159933,"version":"4.4.0"},"reference-count":67,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2020,4,4]],"date-time":"2020-04-04T00:00:00Z","timestamp":1585958400000},"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\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,1]]},"abstract":"<jats:title>Summary<\/jats:title>\n                  <jats:p>While many statistical models and methods are now available for network analysis, resampling of network data remains a challenging problem. Cross-validation is a useful general tool for model selection and parameter tuning, but it is not directly applicable to networks since splitting network nodes into groups requires deleting edges and destroys some of the network structure. In this paper we propose a new network resampling strategy, based on splitting node pairs rather than nodes, that is applicable to cross-validation for a wide range of network model selection tasks. We provide theoretical justification for our method in a general setting and examples of how the method can be used in specific network model selection and parameter tuning tasks. Numerical results on simulated networks and on a statisticians\u2019 citation network show that the proposed cross-validation approach works well for model selection.<\/jats:p>","DOI":"10.1093\/biomet\/asaa006","type":"journal-article","created":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T07:11:54Z","timestamp":1579936314000},"page":"257-276","source":"Crossref","is-referenced-by-count":127,"title":["Network cross-validation by edge sampling"],"prefix":"10.1093","volume":"107","author":[{"given":"Tianxi","family":"Li","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Virginia, B005 Halsey Hall, 148 Amphitheater Way, Charlottesville, Virginia 22904, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elizaveta","family":"Levina","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Michigan, 459 West Hall, 1085 South University Avenue, Ann Arbor, Michigan 48105, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji","family":"Zhu","sequence":"additional","affiliation":[{"name":"Department of Statistics, University of Michigan, 459 West Hall, 1085 South University Avenue, Ann Arbor, Michigan 48105, U.S.A"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,4,4]]},"reference":[{"key":"2021040615344564700_B1","first-page":"1","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe,","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B2","author":"Abbe,","year":"2017","journal-title":"Entrywise eigenvector analysis of random matrices with low expected rank"},{"key":"2021040615344564700_B3","first-page":"1981","article-title":"Mixed membership stochastic blockmodels","volume":"9","author":"Airoldi,","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B4","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/0047-259X(81)90099-3","article-title":"Representations for partially exchangeable arrays of random variables","volume":"11","author":"Aldous,","year":"1981","journal-title":"J. Mult. Anal."},{"key":"2021040615344564700_B5","doi-asserted-by":"crossref","first-page":"2097","DOI":"10.1214\/13-AOS1138","article-title":"Pseudo-likelihood methods for community detection in large sparse networks","volume":"41","author":"Amini,","year":"2013","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B6","author":"Athreya,","year":"2017","journal-title":"Statistical inference on random dot product graphs: A survey"},{"key":"2021040615344564700_B7","first-page":"1","article-title":"1-bit matrix completion under exact low-rank constraint","volume-title":"Proc. 49th Annu. Conf. Information Sciences and Systems (CISS)","author":"Bhaskar,","year":"2015"},{"key":"2021040615344564700_B8","doi-asserted-by":"crossref","first-page":"1922","DOI":"10.1214\/13-AOS1124","article-title":"Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels","volume":"41","author":"Bickel,","year":"2013","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B9","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1111\/rssb.12117","article-title":"Hypothesis testing for automated community detection in networks","volume":"B 78","author":"Bickel,","year":"2016","journal-title":"J. R. Statist. Soc."},{"key":"2021040615344564700_B10","first-page":"3619","article-title":"A max-norm constrained minimization approach to 1-bit matrix completion","volume":"14","author":"Cai,","year":"2013","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B11","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","article-title":"Matrix completion with noise","volume":"98","author":"Cand\u00e8s,","year":"2010","journal-title":"Proc. IEEE"},{"key":"2021040615344564700_B12","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","article-title":"Exact matrix completion via convex optimization","volume":"9","author":"Cand\u00e8s,","year":"2009","journal-title":"Foundat. Comp. Math."},{"key":"2021040615344564700_B13","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","article-title":"The power of convex relaxation: Near-optimal matrix completion","volume":"56","author":"Cand\u00e8s,","year":"2010","journal-title":"IEEE Trans. Info. Theory"},{"key":"2021040615344564700_B14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1214\/14-AOS1272","article-title":"Matrix estimation by universal singular value thresholding","volume":"43","author":"Chatterjee,","year":"2015","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B15","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1080\/01621459.2016.1246365","article-title":"Network cross-validation for determining the number of communities in network data","volume":"113","author":"Chen,","year":"2018","journal-title":"J. Am. Statist. Assoc."},{"key":"2021040615344564700_B16","first-page":"2999","article-title":"Completing any low-rank matrix, provably","volume":"16","author":"Chen,","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B17","doi-asserted-by":"crossref","first-page":"e1469","DOI":"10.1002\/wics.1469","article-title":"Matrix completion from a computational statistics perspective","volume":"11","author":"Chi,","year":"2019","journal-title":"WIREs Comp. Statist."},{"key":"2021040615344564700_B18","first-page":"391","article-title":"Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery","volume":"40","author":"Chin,","year":"2015","journal-title":"Proc. Mach. Learn. Res."},{"key":"2021040615344564700_B19","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1214\/13-AOS1173","article-title":"Co-clustering separately exchangeable network data","volume":"42","author":"Choi,","year":"2014","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B20","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung,","year":"2002","journal-title":"Proc. Nat. Acad. Sci."},{"key":"2021040615344564700_B21","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1080\/01621459.2017.1341413","article-title":"Edge exchangeable models for interaction networks","volume":"113","author":"Crane,","year":"2018","journal-title":"J. Am. Statist. Assoc."},{"key":"2021040615344564700_B22","first-page":"189","article-title":"1-bit matrix completion","volume":"3","author":"Davenport,","year":"2014","journal-title":"Info. Infer."},{"key":"2021040615344564700_B23","author":"Diaconis,","year":"2007","journal-title":"Graph limits and exchangeable random graphs"},{"key":"2021040615344564700_B24","author":"Eldridge,","year":"2017","journal-title":"Unperturbed: Spectral analysis beyond Davis-Kahan"},{"key":"2021040615344564700_B25","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s,","year":"1960","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"2021040615344564700_B26","first-page":"1","article-title":"Optimal estimation and completion of matrices with biclustering structures","volume":"17","author":"Gao,","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B27","doi-asserted-by":"crossref","first-page":"2624","DOI":"10.1214\/15-AOS1354","article-title":"Rate-optimal graphon estimation","volume":"43","author":"Gao,","year":"2015","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B28","first-page":"657","article-title":"Modeling homophily and stochastic equivalence in symmetric relational data","volume-title":"Advances in Neural Information Processing Systems 20 (NIPS 2007)","author":"Hoff,","year":"2008"},{"key":"2021040615344564700_B29","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent space approaches to social network analysis","volume":"97","author":"Hoff,","year":"2002","journal-title":"J. Am. Statist. Assoc."},{"key":"2021040615344564700_B30","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":"Social Networks"},{"key":"2021040615344564700_B31","first-page":"1779","article-title":"Coauthorship and citation networks for statisticians","volume":"10","author":"Ji,","year":"2016","journal-title":"Ann. Appl. Statist."},{"key":"2021040615344564700_B32","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1214\/14-AOS1265","article-title":"Fast community detection by SCORE","volume":"43","author":"Jin,","year":"2015","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B33","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1214\/16-AOS1447","article-title":"Impact of regularization on spectral clustering","volume":"44","author":"Joseph,","year":"2016","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B34","first-page":"10","article-title":"Rank selection in low-rank matrix approximations: A study of crossvalidation for NMFs","volume-title":"Advances in Neural Information Processing Systems","author":"Kanagal,","year":"2010"},{"key":"2021040615344564700_B35","first-page":"016107","article-title":"Stochastic blockmodels and community structure in networks","volume":"E 83","author":"Karrer,","year":"2011","journal-title":"Phys. Rev."},{"key":"2021040615344564700_B36","first-page":"952","article-title":"Matrix completion from noisy entries","volume-title":"Advances in Neural Information Processing Systems 22 (NIPS 2009)","author":"Keshavan,","year":"2009"},{"key":"2021040615344564700_B37","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1177\/1471082X1001200105","article-title":"Variational Bayesian inference and complexity control for stochastic block models","volume":"12","author":"Latouche,","year":"2012","journal-title":"Statist. Mod."},{"key":"2021040615344564700_B38","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1111\/rssb.12266","article-title":"Random networks, graphical models and exchangeability","volume":"B 80","author":"Lauritzen,","year":"2018","journal-title":"J. R. Statist. Soc."},{"key":"2021040615344564700_B39","author":"Le,","year":"2019","journal-title":"Estimating the number of communities in networks by spectral methods"},{"key":"2021040615344564700_B40","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1002\/rsa.20713","article-title":"Concentration and regularization of random graphs","volume":"51","author":"Le,","year":"2017","journal-title":"Random Struct. Algor."},{"key":"2021040615344564700_B41","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1214\/15-AOS1370","article-title":"A goodness-of-fit test for stochastic block models","volume":"44","author":"Lei,","year":"2016","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B42","author":"Lei,","year":"2017","journal-title":"Cross-validation with confidence"},{"key":"2021040615344564700_B43","first-page":"215","article-title":"Consistency of spectral clustering in stochastic block models","volume":"43","author":"Lei,","year":"2014","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B44","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1214\/18-AOAS1205","article-title":"Prediction models for network-linked data","volume":"13","author":"Li,","year":"2019","journal-title":"Ann. Appl. Statist."},{"key":"2021040615344564700_B45","first-page":"2287","article-title":"Spectral regularization algorithms for learning large incomplete matrices","volume":"11","author":"Mazumder,","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"2021040615344564700_B46","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.csda.2012.10.021","article-title":"Improved Bayesian inference for the stochastic block model with application to large networks","volume":"60","author":"McDaid,","year":"2013","journal-title":"Comp. Statist. Data Anal."},{"key":"2021040615344564700_B47","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1111\/j.1467-9868.2010.00740.x","article-title":"Stability selection","volume":"B 72","author":"Meinshausen,","year":"2010","journal-title":"J. R. Statist. Soc."},{"key":"2021040615344564700_B48","doi-asserted-by":"crossref","first-page":"11863","DOI":"10.1038\/ncomms11863","article-title":"Structure and inference in annotated networks","volume":"7","author":"Newman,","year":"2016","journal-title":"Nature Commun."},{"key":"2021040615344564700_B49","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1214\/08-AOAS227","article-title":"Bi-cross-validation of the SVD and the nonnegative matrix factorization","volume":"3","author":"Owen,","year":"2009","journal-title":"Ann. Appl. Statist"},{"key":"2021040615344564700_B50","first-page":"3120","article-title":"Regularized spectral clustering under the degree-corrected stochastic blockmodel","volume-title":"Proc. 26th Int. Conf. Neural Information Processing Systems","author":"Qin,","year":"2013"},{"key":"2021040615344564700_B51","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":"2021040615344564700_B52","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1080\/10618600.2015.1096790","article-title":"How many communities are there?","volume":"26","author":"Saldana,","year":"2017","journal-title":"J. Comp. Graph. Statist."},{"key":"2021040615344564700_B53","doi-asserted-by":"crossref","first-page":"962","DOI":"10.1214\/14-AOS1285","article-title":"Role of normalization in spectral clustering for stochastic blockmodels","volume":"43","author":"Sarkar,","year":"2015","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B54","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":"B 80","author":"Sengupta,","year":"2018","journal-title":"J. R. Statist. Soc."},{"key":"2021040615344564700_B55","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1080\/01621459.1993.10476299","article-title":"Linear model selection by cross-validation","volume":"88","author":"Shao,","year":"1993","journal-title":"J. Am. Statist. Assoc."},{"key":"2021040615344564700_B56","author":"Su,","year":"2019","journal-title":"Strong consistency of spectral clustering for stochastic block models"},{"key":"2021040615344564700_B57","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/TPAMI.2013.135","article-title":"Consistent latent position estimation and vertex classification for random dot product graphs","volume":"36","author":"Sussman,","year":"2014","journal-title":"IEEE Trans. Pat. Anal. Mach. Intel."},{"key":"2021040615344564700_B58","doi-asserted-by":"crossref","first-page":"1599","DOI":"10.3150\/15-BEJ789","article-title":"A nonparametric two-sample hypothesis testing problem for random graphs","volume":"23","author":"Tang,","year":"2017","journal-title":"Bernoulli"},{"key":"2021040615344564700_B59","doi-asserted-by":"crossref","first-page":"2360","DOI":"10.1214\/17-AOS1623","article-title":"Limit theorems for eigenvectors of the normalized Laplacian for random graphs","volume":"46","author":"Tang,","year":"2018","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B60","doi-asserted-by":"crossref","first-page":"1820","DOI":"10.1214\/16-AOAS977","article-title":"Discussion of \u201cCoauthorship and citation networks for statisticians\u201d","volume":"10","author":"Wang,","year":"2016","journal-title":"Ann. Appl. Statist."},{"key":"2021040615344564700_B61","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1214\/16-AOS1457","article-title":"Likelihood-based model selection for stochastic block models","volume":"45","author":"Wang,","year":"2017","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B62","author":"Wolfe,","year":"2013","journal-title":"Nonparametric graphon estimation"},{"key":"2021040615344564700_B63","doi-asserted-by":"crossref","first-page":"2450","DOI":"10.1214\/009053607000000514","article-title":"Consistency of cross validation for comparing regression procedures","volume":"35","author":"Yang,","year":"2007","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B64","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-540-77004-6_11","article-title":"Random dot product graph models for social networks","volume-title":"International Workshop on Algorithms and Models for the Web-Graph","author":"Young,","year":"2007"},{"key":"2021040615344564700_B65","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1214\/aos\/1176349027","article-title":"Model selection via multifold cross validation","volume":"21","author":"Zhang,","year":"1993","journal-title":"Ann. Statist."},{"key":"2021040615344564700_B66","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1093\/biomet\/asx042","article-title":"Estimating network edge probabilities by neighbourhood smoothing","volume":"104","author":"Zhang,","year":"2017","journal-title":"Biometrika"},{"key":"2021040615344564700_B67","doi-asserted-by":"crossref","first-page":"2266","DOI":"10.1214\/12-AOS1036","article-title":"Consistency of community detection in networks under degree-corrected stochastic block models","volume":"40","author":"Zhao,","year":"2012","journal-title":"Ann. Statist."}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/107\/2\/257\/33218033\/asaa006.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/107\/2\/257\/33218033\/asaa006.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T12:38:36Z","timestamp":1617712716000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/107\/2\/257\/5816043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,4]]},"references-count":67,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,4,4]]},"published-print":{"date-parts":[[2020,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaa006","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,6]]},"published":{"date-parts":[[2020,4,4]]}}}