{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T01:36:45Z","timestamp":1774834605805,"version":"3.50.1"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T00:00:00Z","timestamp":1746403200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T00:00:00Z","timestamp":1746403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2025,8]]},"DOI":"10.1007\/s11222-025-10620-y","type":"journal-article","created":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T09:34:52Z","timestamp":1746437692000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Graph sub-sampling for divide-and-conquer algorithms in large networks"],"prefix":"10.1007","volume":"35","author":[{"given":"Eric","family":"Yanchenko","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,5]]},"reference":[{"key":"10620_CR1","doi-asserted-by":"crossref","unstructured":"Adamic, L.A., Glance, N.: The political blogosphere and the 2004 US election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery, pp. 36\u201343 (2005)","DOI":"10.1145\/1134271.1134277"},{"issue":"2","key":"10620_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601438","volume":"8","author":"NK Ahmed","year":"2013","unstructured":"Ahmed, N.K., Neville, J., Kompella, R.: Network sampling: from static to streaming graphs. ACM Trans. Knowl. Discov. Data 8(2), 1\u201356 (2013)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"10620_CR3","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 44\u201354 (2006)","DOI":"10.1145\/1150402.1150412"},{"issue":"3\u20134","key":"10620_CR4","first-page":"137","volume":"21","author":"S Beamer","year":"2013","unstructured":"Beamer, S., Asanovi\u0107, K., Patterson, D.: Direction-optimizing breadth-first search. Sci. Program. 21(3\u20134), 137\u2013148 (2013)","journal-title":"Sci. Program."},{"issue":"50","key":"10620_CR5","doi-asserted-by":"publisher","first-page":"21068","DOI":"10.1073\/pnas.0907096106","volume":"106","author":"PJ Bickel","year":"2009","unstructured":"Bickel, P.J., Chen, A.: A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. 106(50), 21068\u201321073 (2009)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"4","key":"10620_CR6","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0378-8733(99)00019-2","volume":"21","author":"SP Borgatti","year":"2000","unstructured":"Borgatti, S.P., Everett, M.G.: Models of core\/periphery structures. Social Netw. 21(4), 375\u2013395 (2000)","journal-title":"Social Netw."},{"key":"10620_CR7","doi-asserted-by":"crossref","unstructured":"Bundy, A., Wallen, L.: Breadth-first search. In: Catalogue of Artificial Intelligence Tools, pp. 13\u201313 (1984)","DOI":"10.1007\/978-3-642-96868-6_25"},{"issue":"5","key":"10620_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3446216","volume":"15","author":"P Burkhardt","year":"2021","unstructured":"Burkhardt, P.: Optimal algebraic breadth-first search for sparse graphs. ACM Trans. Knowl. Discov. Data 15(5), 1\u201319 (2021)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"3","key":"10620_CR9","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1214\/14-AOS1290","volume":"43","author":"TT Cai","year":"2015","unstructured":"Cai, T.T., Li, X.: Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann. Stat. 43(3), 1027\u20131059 (2015)","journal-title":"Ann. Stat."},{"issue":"4","key":"10620_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s11222-024-10451-3","volume":"34","author":"DO Cardoso","year":"2024","unstructured":"Cardoso, D.O., da Silva Junior, J., Oliveira, C.S., Marques, C., de Assis, L.S.: Greedy recursive spectral bisection for modularity-bound hierarchical divisive community detection. Stat. Comput. 34(4), 145 (2024)","journal-title":"Stat. Comput."},{"issue":"3","key":"10620_CR11","first-page":"1","volume":"35","author":"S Chakrabarty","year":"2025","unstructured":"Chakrabarty, S., Sengupta, S., Chen, Y.: Subsampling-based community detection for large networks. Stat. Sin. 35(3), 1\u201342 (2025)","journal-title":"Stat. Sin."},{"key":"10620_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10618600.2024.2432974","volume":"8","author":"K Chakraborty","year":"2025","unstructured":"Chakraborty, K., Sengupta, S., Chen, Y.: Scalable estimation and two-sample testing for large networks via subsampling. J. Comput. Graph. Stat. 8, 1\u201313 (2025)","journal-title":"J. Comput. Graph. Stat."},{"issue":"5","key":"10620_CR13","doi-asserted-by":"publisher","first-page":"6181","DOI":"10.1109\/TCSS.2024.3381777","volume":"11","author":"D Chen","year":"2024","unstructured":"Chen, D., Su, H.: Extracting high-fidelity smaller scale subgraphs of complex networks by edge-reinforced random walk. IEEE Trans. Comput. Soc. Syst. 11(5), 6181\u20136191 (2024)","journal-title":"IEEE Trans. Comput. Soc. Syst."},{"key":"10620_CR14","doi-asserted-by":"crossref","unstructured":"Chiericetti, F., Dasgupta, A., Kumar, R., Lattanzi, S., Sarl\u00f3s, T.: On sampling nodes in a network. In: Proceedings of the 25th International Conference on World Wide Web, pp. 471\u2013481 (2016)","DOI":"10.1145\/2872427.2883045"},{"key":"10620_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A Clauset","year":"2004","unstructured":"Clauset, A., Newman, M., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)","journal-title":"Phys. Rev. E"},{"key":"10620_CR16","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2022)"},{"key":"10620_CR17","unstructured":"Cs\u00e1rdi, G., Nepusz, T., Traag, V., Horv\u00e1t, S., Zanini, F., Noom, D., M\u00fcller, K.: igraph: network analysis and visualization in R. R package version, vol. 2(1), p. 4 (2025)"},{"issue":"1","key":"10620_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s11222-023-10342-z","volume":"34","author":"G Fang","year":"2024","unstructured":"Fang, G., Ward, O.G., Zheng, T.: Online estimation and community detection of network point processes for event streams. Stat. Comput. 34(1), 35 (2024)","journal-title":"Stat. Comput."},{"key":"10620_CR19","first-page":"24","volume":"31","author":"D Ghoshdastidar","year":"2018","unstructured":"Ghoshdastidar, D., Von Luxburg, U.: Practical methods for graph two-sample testing. Adv. Neural Inf. Process. Syst. 31, 24 (2018)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"12","key":"10620_CR20","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821\u20137826 (2002)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"10620_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic block models: first steps. Social Netw. 5, 109\u2013137 (1983)","journal-title":"Social Netw."},{"key":"10620_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2, 193\u2013218 (1985)","journal-title":"J. Classif."},{"issue":"9","key":"10620_CR23","doi-asserted-by":"publisher","first-page":"2428","DOI":"10.1109\/TPDS.2017.2672739","volume":"28","author":"C Jain","year":"2017","unstructured":"Jain, C., Flick, P., Pan, T., Green, O., Aluru, S.: An adaptive parallel algorithm for computing connected components. IEEE Trans. Parallel Distrib. Syst. 28(9), 2428\u20132439 (2017)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10620_CR24","doi-asserted-by":"crossref","unstructured":"Jordan, M.I.: Divide-and-conquer and statistical inference for big data. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 4\u20134 (2012)","DOI":"10.1145\/2339530.2339534"},{"key":"10620_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10732-017-9331-3","volume":"23","author":"R Jovanovic","year":"2017","unstructured":"Jovanovic, R., Nishi, T., Vo\u00df, S.: A heuristic approach for dividing graphs into bi-connected components with a size constraint. J. Heurist. 23, 111\u2013136 (2017)","journal-title":"J. Heurist."},{"issue":"4","key":"10620_CR26","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/aab547","volume":"20","author":"S Kojaku","year":"2018","unstructured":"Kojaku, S., Masuda, N.: Core-periphery structure requires something else in the network. New J. Phys. 20(4), 043012 (2018)","journal-title":"New J. Phys."},{"key":"10620_CR27","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, V., Faloutsos, M., Chrobak, M., Lao, L., Cui, J.-H., Percus, A.G.: Reducing large internet topologies for faster simulations. In: International Conference on Research in Networking, pp. 328\u2013341. Springer (2005)","DOI":"10.1007\/11422778_27"},{"key":"10620_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2020.124289","volume":"553","author":"A Kumar","year":"2020","unstructured":"Kumar, A., Singh, S.S., Singh, K., Biswas, B.: Link prediction techniques, applications, and performance: a survey. Physica A 553, 124289 (2020)","journal-title":"Physica A"},{"key":"10620_CR29","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Faloutsos, C.: Sampling from large graphs. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 631\u2013636 (2006)","DOI":"10.1145\/1150402.1150479"},{"key":"10620_CR30","unstructured":"Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection (2014). http:\/\/snap.stanford.edu\/data. Accessed 24 Feb 2025"},{"key":"10620_CR31","first-page":"66","volume":"25","author":"J Leskovec","year":"2012","unstructured":"Leskovec, J., Mcauley, J.: Learning to discover social circles in ego networks. Adv. Neural Inf. Process. Syst. 25, 66 (2012)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10620_CR32","doi-asserted-by":"crossref","unstructured":"Li, R.-H., Yu, J.X., Qin, L., Mao, R., Jin, T.: On random walk based graph sampling. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 927\u2013938. IEEE (2015)","DOI":"10.1109\/ICDE.2015.7113345"},{"key":"10620_CR33","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link prediction problem for social networks. In: Proceedings of the Twelfth International Conference on Information and Knowledge Management, pp. 556\u2013559 (2003)","DOI":"10.1145\/956863.956972"},{"issue":"1\u201346","key":"10620_CR34","first-page":"4","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random walks on graphs. Combin. Paul Erd\u0151s Eighty 2(1\u201346), 4 (1993)","journal-title":"Combin. Paul Erd\u0151s Eighty"},{"key":"10620_CR35","doi-asserted-by":"crossref","unstructured":"Mukherjee, S.S., Sarkar, P., Bickel, P.J.: Two provably consistent divide-and-conquer clustering algorithms for large networks. In: Proceedings of the National Academy of Sciences, vol. 118(44) (2021)","DOI":"10.1073\/pnas.2100482118"},{"issue":"1","key":"10620_CR36","doi-asserted-by":"publisher","first-page":"1814","DOI":"10.1214\/21-EJS1819","volume":"15","author":"C Naik","year":"2021","unstructured":"Naik, C., Caron, F., Rousseau, J.: Sparse networks with core-periphery structure. Electron. J. Stat. 15(1), 1814\u20131868 (2021)","journal-title":"Electron. J. Stat."},{"issue":"23","key":"10620_CR37","doi-asserted-by":"publisher","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"ME Newman","year":"2006","unstructured":"Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577\u20138582 (2006)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"10620_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"ME Newman","year":"2004","unstructured":"Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)","journal-title":"Phys. Rev. E"},{"key":"10620_CR39","unstructured":"Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: analysis and an algorithm. In: Advances in Neural Information Processing Systems, pp. 849\u2013856 (2002)"},{"key":"10620_CR40","doi-asserted-by":"crossref","unstructured":"Pons, P., Latapy, M.: Computing communities in large networks using random walks. In: Computer and Information Sciences-ISCIS 2005, pp. 284\u2013293. Springer (2005)","DOI":"10.1007\/11569596_31"},{"issue":"336","key":"10620_CR41","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1080\/01621459.1971.10482356","volume":"66","author":"WM Rand","year":"1971","unstructured":"Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846\u2013850 (1971)","journal-title":"J. Am. Stat. Assoc."},{"key":"10620_CR42","doi-asserted-by":"crossref","unstructured":"Ribeiro, B., Wang, P., Murai, F., Towsley, D.: Sampling directed graphs with random walks. In: 2012 Proceedings IEEE INFOCOM, pp. 1692\u20131700. IEEE (2012)","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"10620_CR43","doi-asserted-by":"crossref","unstructured":"Richardson, M., Agrawal, R., Domingos, P.: Trust management for the semantic web. In: International Semantic Web Conference, pp. 351\u2013368. Springer (2003)","DOI":"10.1007\/978-3-540-39718-2_23"},{"key":"10620_CR44","doi-asserted-by":"crossref","unstructured":"Ro\u017eanec, J.M., Ro\u017eanec, M.: Go-network: a graph sampling library written in Go. In: Companion of the 15th ACM\/SPEC International Conference on Performance Engineering, pp. 151\u2013155 (2024)","DOI":"10.1145\/3629527.3652903"},{"key":"10620_CR45","doi-asserted-by":"crossref","unstructured":"Rozemberczki, B., Kiss, O., Sarkar, R.: Little ball of fur: a python library for graph sampling. In: Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM \u201920), pp. 3133\u20133140. ACM (2020)","DOI":"10.1145\/3340531.3412758"},{"issue":"2","key":"10620_CR46","first-page":"14","volume":"9","author":"B Rozemberczki","year":"2021","unstructured":"Rozemberczki, B., Allen, C., Sarkar, R.: Multi-scale attributed node embedding. J. Complex Netw. 9(2), 14 (2021)","journal-title":"J. Complex Netw."},{"issue":"2","key":"10620_CR47","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10620_CR48","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1089\/brain.2011.0055","volume":"1","author":"QK Telesford","year":"2011","unstructured":"Telesford, Q.K., Simpson, S.L., Burdette, J.H., Hayasaka, S., Laurienti, P.J.: The brain as a complex system: using network science as a tool for understanding the brain. Brain Connect. 1(4), 295\u2013308 (2011)","journal-title":"Brain Connect."},{"issue":"1","key":"10620_CR49","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/s13278-023-01157-x","volume":"14","author":"K Wang","year":"2023","unstructured":"Wang, K.: An adaptive graph sampling framework for graph analytics. Soc. Netw. Anal. Min. 14(1), 4 (2023)","journal-title":"Soc. Netw. Anal. Min."},{"key":"10620_CR50","first-page":"1","volume":"8","author":"J Wang","year":"2022","unstructured":"Wang, J., Xie, Y., Xie, S., Chen, X.: Cooperative particle swarm optimizer with depth first search strategy for global optimization of multimodal functions. Appl. Intell. 8, 1\u201320 (2022)","journal-title":"Appl. Intell."},{"key":"10620_CR51","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2023.122554","volume":"240","author":"X Wang","year":"2024","unstructured":"Wang, X., Shi, J.-H., Zou, J.-J., Shen, L.-Z., Lan, Z., Fang, Y., Xie, W.-B.: Supports estimation via graph sampling. Expert Syst. Appl. 240, 122554 (2024)","journal-title":"Expert Syst. Appl."},{"issue":"1","key":"10620_CR52","doi-asserted-by":"publisher","DOI":"10.1002\/sta4.475","volume":"11","author":"E Yanchenko","year":"2022","unstructured":"Yanchenko, E.: A divide-and-conquer algorithm for core-periphery identification in large networks. Stat 11(1), e475 (2022)","journal-title":"Stat"},{"key":"10620_CR53","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1214\/23-SS141","volume":"17","author":"E Yanchenko","year":"2023","unstructured":"Yanchenko, E., Sengupta, S.: Core-periphery structure in networks: a statistical exposition. Stat. Surv. 17, 42\u201374 (2023)","journal-title":"Stat. Surv."},{"key":"10620_CR54","first-page":"66","volume":"31","author":"M Zhang","year":"2018","unstructured":"Zhang, M., Chen, Y.: Link prediction based on graph neural networks. Adv. Neural Inf. Process. Syst. 31, 66 (2018)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"401","key":"10620_CR55","first-page":"1","volume":"24","author":"S Zhang","year":"2023","unstructured":"Zhang, S., Song, R., Lu, W., Zhu, J.: Distributed community detection in large networks. J. Mach. Learn. Res. 24(401), 1\u201328 (2023)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-025-10620-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-025-10620-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-025-10620-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:04:01Z","timestamp":1750212241000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-025-10620-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,5]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10620"],"URL":"https:\/\/doi.org\/10.1007\/s11222-025-10620-y","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,5]]},"assertion":[{"value":"4 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2025","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 author declares no Conflict of interest nor have any funding to report.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"87"}}