{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T05:28:50Z","timestamp":1768714130768,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Johns Hopkins Mathematical Institute for Data Science"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a dynamic network sampling scheme to optimize block recovery for stochastic blockmodel in the case where it is prohibitively expensive to observe the entire graph. Theoretically, we provide justification of our proposed Chernoff-optimal dynamic sampling scheme via the Chernoff information. Practically, we evaluate the performance, in terms of block recovery, of our method on several real datasets from different domains. Both theoretically and practically results suggest that our method can identify vertices that have the most impact on block structure so that one can only check whether there are edges between them to save significant resources but still recover the block structure.<\/jats:p>","DOI":"10.1007\/s41109-022-00528-1","type":"journal-article","created":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T13:05:47Z","timestamp":1673615147000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic network sampling for community detection"],"prefix":"10.1007","volume":"8","author":[{"given":"Cong","family":"Mu","sequence":"first","affiliation":[]},{"given":"Youngser","family":"Park","sequence":"additional","affiliation":[]},{"given":"Carey E.","family":"Priebe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,13]]},"reference":[{"issue":"2","key":"528_CR1","doi-asserted-by":"publisher","first-page":"3230","DOI":"10.1214\/20-EJS1744","volume":"14","author":"J Agterberg","year":"2020","unstructured":"Agterberg J, Park Y, Larson J, White C, Priebe CE, Lyzinski V (2020) Vertex nomination, consistent estimation, and adversarial modification. Electron J Stat 14(2):3230\u20133267","journal-title":"Electron J Stat"},{"issue":"1","key":"528_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13171-015-0071-x","volume":"78","author":"A Athreya","year":"2016","unstructured":"Athreya A, Priebe CE, Tang M, Lyzinski V, Marchette DJ, Sussman DL (2016) A limit theorem for scaled eigenvectors of random dot product graphs. Sankhya A 78(1):1\u201318","journal-title":"Sankhya A"},{"issue":"1","key":"528_CR3","first-page":"8393","volume":"18","author":"A Athreya","year":"2017","unstructured":"Athreya A, Fishkind DE, Tang M, Priebe CE, Park Y, Vogelstein JT, Levin K, Lyzinski V, Qin Y (2017) Statistical inference on random dot product graphs: a survey. J Mach Learn Res 18(1):8393\u20138484","journal-title":"J Mach Learn Res"},{"issue":"2","key":"528_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1093\/biomet\/asx008","volume":"104","author":"N Binkiewicz","year":"2017","unstructured":"Binkiewicz N, Vogelstein JT, Rohe K (2017) Covariate-assisted spectral clustering. Biometrika 104(2):361\u2013377","journal-title":"Biometrika"},{"issue":"4","key":"528_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff H (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann Math Stat 23(4):493\u2013507","journal-title":"Ann Math Stat"},{"issue":"1","key":"528_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/aoms\/1177728347","volume":"27","author":"H Chernoff","year":"1956","unstructured":"Chernoff H (1956) Large-sample theory: parametric case. Ann Math Stat 27(1):1\u201322","journal-title":"Ann Math Stat"},{"issue":"2","key":"528_CR7","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1093\/biomet\/asr053","volume":"99","author":"DS Choi","year":"2012","unstructured":"Choi DS, Wolfe PJ, Airoldi EM (2012) Stochastic blockmodels with a growing number of classes. Biometrika 99(2):273\u2013284","journal-title":"Biometrika"},{"key":"528_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","volume":"659","author":"S Fortunato","year":"2016","unstructured":"Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1\u201344","journal-title":"Phys Rep"},{"key":"528_CR9","unstructured":"Gallagher I, Bertiger A, Priebe C, Rubin-Delanchy P (2019) Spectral clustering in the weighted stochastic block model. arXiv:1910.05534"},{"key":"528_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The elements of statistical learning: data mining, inference, and prediction","author":"T Hastie","year":"2009","unstructured":"Hastie T, Tibshirani R, Friedman J (2009) The elements of statistical learning: data mining, inference, and prediction. Springer, New York"},{"issue":"2","key":"528_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland PW, Laskey KB, Leinhardt S (1983) Stochastic blockmodels: first steps. Soc Netw 5(2):109\u2013137","journal-title":"Soc Netw"},{"key":"528_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411","volume-title":"Matrix Analysis","author":"RA Horn","year":"2012","unstructured":"Horn RA, Johnson CR (2012) Matrix Analysis. Cambridge University Press, New York"},{"key":"528_CR13","unstructured":"Huang S, Feng Y (2018) Pairwise covariates-adjusted block model for community detection. arXiv:1807.03469"},{"issue":"2065","key":"528_CR14","doi-asserted-by":"publisher","first-page":"20150202","DOI":"10.1098\/rsta.2015.0202","volume":"374","author":"IT Jolliffe","year":"2016","unstructured":"Jolliffe IT, Cadima J (2016) Principal component analysis: a review and recent developments. Philos Trans R Soc A Math Phys Eng Sci 374(2065):20150202","journal-title":"Philos Trans R Soc A Math Phys Eng Sci"},{"issue":"1","key":"528_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.016107","volume":"83","author":"B Karrer","year":"2011","unstructured":"Karrer B, Newman ME (2011) Stochastic blockmodels and community structure in networks. Phys Rev E 83(1):016107","journal-title":"Phys Rev E"},{"key":"528_CR16","doi-asserted-by":"crossref","unstructured":"Kiar G, Bridgeford EW, Gray\u00a0Roncal WR, Chandrashekhar V, Mhembere D, Ryman S, Zuo X-N, Margulies DS, Craddock RC, Priebe CE, Jung R, Calhoun VD, Caffo B, Burns R, Milham MP, Vogelstein JT (2018) A high-throughput pipeline identifies robust connectomes but troublesome variability. bioRxiv, 188706","DOI":"10.1101\/188706"},{"key":"528_CR17","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"2","key":"528_CR18","doi-asserted-by":"publisher","first-page":"2905","DOI":"10.1214\/14-EJS978","volume":"8","author":"V Lyzinski","year":"2014","unstructured":"Lyzinski V, Sussman DL, Tang M, Athreya A, Priebe CE (2014) Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding. Electron J Stat 8(2):2905\u20132922","journal-title":"Electron J Stat"},{"issue":"1","key":"528_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/TNSE.2016.2634322","volume":"4","author":"V Lyzinski","year":"2016","unstructured":"Lyzinski V, Tang M, Athreya A, Park Y, Priebe CE (2016) Community detection and classification in hierarchical stochastic blockmodels. IEEE Trans Netw Sci Eng 4(1):13\u201326","journal-title":"IEEE Trans Netw Sci Eng"},{"key":"528_CR20","doi-asserted-by":"crossref","unstructured":"McSherry F (2001) Spectral partitioning of random graphs. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp 529\u2013537. IEEE","DOI":"10.1109\/SFCS.2001.959929"},{"key":"528_CR21","doi-asserted-by":"crossref","unstructured":"Mele A, Hao L, Cape J, Priebe CE (2022) Spectral inference for large stochastic blockmodels with nodal covariates. J Bus Econ Stat","DOI":"10.1080\/07350015.2022.2139709"},{"key":"528_CR22","doi-asserted-by":"crossref","unstructured":"Mu C, Mele A, Hao L, Cape J, Athreya A, Priebe CE (2022) On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates. IEEE Trans Netw Sci Eng","DOI":"10.1109\/TNSE.2022.3177708"},{"issue":"13","key":"528_CR23","doi-asserted-by":"publisher","first-page":"5995","DOI":"10.1073\/pnas.1814462116","volume":"116","author":"CE Priebe","year":"2019","unstructured":"Priebe CE, Park Y, Vogelstein JT, Conroy JM, Lyzinski V, Tang M, Athreya A, Cape J, Bridgeford E (2019) On a two-truths phenomenon in spectral graph clustering. Proc Natl Acad Sci 116(13):5995\u20136000","journal-title":"Proc Natl Acad Sci"},{"key":"528_CR24","doi-asserted-by":"crossref","unstructured":"Purohit S, Choudhury S, Holder LB (2017) Application-specific graph sampling for frequent subgraph mining and community detection. In: 2017 IEEE International Conference on Big Data (Big Data), pp 1000\u20131005. IEEE","DOI":"10.1109\/BigData.2017.8258022"},{"issue":"4","key":"528_CR25","doi-asserted-by":"publisher","first-page":"1878","DOI":"10.1214\/11-AOS887","volume":"39","author":"K Rohe","year":"2011","unstructured":"Rohe K, Chatterjee S, Yu B (2011) Spectral clustering and the high-dimensional stochastic blockmodel. Ann Stat 39(4):1878\u20131915","journal-title":"Ann Stat"},{"issue":"3","key":"528_CR26","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1080\/10618600.2018.1554486","volume":"28","author":"S Roy","year":"2019","unstructured":"Roy S, Atchad\u00e9 Y, Michailidis G (2019) Likelihood inference for large scale stochastic blockmodels with covariates based on a divide-and-conquer parallelizable algorithm with communication. J Comput Graph Stat 28(3):609\u2013619","journal-title":"J Comput Graph Stat"},{"key":"528_CR27","unstructured":"Rozemberczki B, Allen C, Sarkar R (2019) Multi-scale attributed node embedding. arXiv:1909.13021"},{"key":"528_CR28","doi-asserted-by":"crossref","unstructured":"Rozemberczki B, Sarkar R (2020) Characteristic functions on graphs: birds of a feather, from statistical descriptors to parametric models. In: Proceedings of the 29th ACM International conference on information and knowledge management (CIKM \u201920), pp 1325\u20131334. ACM","DOI":"10.1145\/3340531.3411866"},{"key":"528_CR29","doi-asserted-by":"crossref","unstructured":"Rubin-Delanchy P, Priebe CE, Tang M, Cape J (2022) A statistical interpretation of spectral embedding: the generalised random dot product graph. J R Stat Soc","DOI":"10.1111\/rssb.12509"},{"issue":"499","key":"528_CR30","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1080\/01621459.2012.699795","volume":"107","author":"DL Sussman","year":"2012","unstructured":"Sussman DL, Tang M, Fishkind DE, Priebe CE (2012) A consistent adjacency spectral embedding for stochastic blockmodel graphs. J Am Stat Assoc 107(499):1119\u20131128","journal-title":"J Am Stat Assoc"},{"issue":"6","key":"528_CR31","doi-asserted-by":"publisher","first-page":"635","DOI":"10.3102\/1076998615606110","volume":"40","author":"TM Sweet","year":"2015","unstructured":"Sweet TM (2015) Incorporating covariates into stochastic blockmodels. J Educ Behav Stat 40(6):635\u2013664","journal-title":"J Educ Behav Stat"},{"issue":"5","key":"528_CR32","doi-asserted-by":"publisher","first-page":"2360","DOI":"10.1214\/17-AOS1623","volume":"46","author":"M Tang","year":"2018","unstructured":"Tang M, Priebe CE (2018) Limit theorems for eigenvectors of the normalized laplacian for random graphs. Ann Stat 46(5):2360\u20132415","journal-title":"Ann Stat"},{"issue":"4","key":"528_CR33","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Von Luxburg","year":"2007","unstructured":"Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395\u2013416","journal-title":"Stat Comput"},{"key":"528_CR34","unstructured":"Yun S-Y, Proutiere A (2014) Community detection via random and adaptive sampling. In: Conference on Learning Theory, pp 138\u2013175. PMLR"},{"issue":"2","key":"528_CR35","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.csda.2005.09.010","volume":"51","author":"M Zhu","year":"2006","unstructured":"Zhu M, Ghodsi A (2006) Automatic dimensionality selection from the scree plot via the use of profile likelihood. Comput Stati Data Anal 51(2):918\u2013930","journal-title":"Comput Stati Data Anal"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-022-00528-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-022-00528-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-022-00528-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T13:10:20Z","timestamp":1673615420000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-022-00528-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,13]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["528"],"URL":"https:\/\/doi.org\/10.1007\/s41109-022-00528-1","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,13]]},"assertion":[{"value":"31 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"5"}}