{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:40Z","timestamp":1740122380521,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["1918483","IIS1943364"],"award-info":[{"award-number":["1918483","IIS1943364"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s10618-021-00802-3","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T06:03:29Z","timestamp":1641276209000},"page":"414-447","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2789-8864","authenticated-orcid":false,"given":"Carlos H. C.","family":"Teixeira","sequence":"first","affiliation":[]},{"given":"Mayank","family":"Kakodkar","sequence":"additional","affiliation":[]},{"given":"Vin\u00edcius","family":"Dias","sequence":"additional","affiliation":[]},{"suffix":"Jr.","given":"Wagner","family":"Meira","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Ribeiro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"key":"802_CR1","unstructured":"Aldous D, Fill JA (2002) Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014. Available at http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html"},{"key":"802_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1090\/S0002-9947-1978-0511425-0","volume":"245","author":"KB Athreya","year":"1978","unstructured":"Athreya KB, Ney P (1978) A new approach to the limit theory of recurrent Markov chains. Trans Am Math Soc 245:493\u2013501","journal-title":"Trans Am Math Soc"},{"key":"802_CR3","doi-asserted-by":"crossref","unstructured":"Avrachenkov K, Ribeiro B, Sreedharan JK (2016) Inference in osns via lightweight partial crawls. In: ACM SIGMETRICS, pp 165\u2013177","DOI":"10.1145\/2964791.2901477"},{"issue":"1","key":"802_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s40649-017-0049-z","volume":"5","author":"K Avrachenkov","year":"2018","unstructured":"Avrachenkov K, Borkar VS, Kadavankandy A, Sreedharan JK (2018) Revisiting random walk based sampling in networks: evasion of burn-in period and frequent regenerations. Comput Soc Netw 5(1):1\u201319","journal-title":"Comput Soc Netw"},{"key":"802_CR5","doi-asserted-by":"crossref","unstructured":"Bhuiyan MA, Rahman M, Rahman M, Al Hasan M (2012) Guise: uniform sampling of graphlets for large graph analysis. In: IEEE 12th international conference on data mining. IEEE, pp 91\u2013100","DOI":"10.1109\/ICDM.2012.87"},{"key":"802_CR6","series-title":"Texts in applied mathematics","volume-title":"Markov chains: Gibbs Fields, Monte Carlo simulation, and queues","author":"P Bremaud","year":"2001","unstructured":"Bremaud P (2001) Markov chains: Gibbs Fields, Monte Carlo simulation, and queues. Texts in applied mathematics. Springer, New York"},{"key":"802_CR7","doi-asserted-by":"publisher","unstructured":"Bressan M, Chierichetti F, Kumar R, Leucci S, Panconesi A (2018) Motif counting beyond five nodes. ACM TKDD 12(4):1\u201325. https:\/\/doi.org\/10.1145\/3186586","DOI":"10.1145\/3186586"},{"key":"802_CR8","doi-asserted-by":"crossref","unstructured":"Bressan M, Leucci S, Panconesi A (2019) Motivo: fast motif counting via succinct color coding and adaptive sampling. In: Proc VLDB Endow","DOI":"10.14778\/3342263.3342640"},{"issue":"4","key":"802_CR9","first-page":"1","volume":"12","author":"X Chen","year":"2018","unstructured":"Chen X, Lui JC (2018) Mining graphlet counts in online social networks. ACM TKDD 12(4):1\u201338","journal-title":"ACM TKDD"},{"key":"802_CR10","doi-asserted-by":"publisher","unstructured":"Cooper C, Radzik T, Siantos Y (2016) Fast low-cost estimation of network properties using random walks. Internet Math 12:221\u2013238. https:\/\/doi.org\/10.1080\/15427951.2016.1164100","DOI":"10.1080\/15427951.2016.1164100"},{"key":"802_CR11","doi-asserted-by":"crossref","unstructured":"Diaconis P, Stroock DW (1991) Geometric bounds for eigenvalues of Markov chains. Ann Appl Probab 1:36\u201361","DOI":"10.1214\/aoap\/1177005980"},{"issue":"6","key":"802_CR12","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","volume":"6","author":"S Geman","year":"1984","unstructured":"Geman S, Geman D (1984) Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE PAMI PAMI 6(6):721\u2013741","journal-title":"IEEE PAMI PAMI"},{"key":"802_CR13","doi-asserted-by":"crossref","unstructured":"Geyer CJ (1992) Practical Markov chain Monte Carlo. Stat Sci 7:473\u2013483","DOI":"10.1214\/ss\/1177011137"},{"issue":"A","key":"802_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1239\/jap\/1417528487","volume":"51","author":"PW Glynn","year":"2014","unstructured":"Glynn PW, Rhee Ch (2014) Exact estimation for Markov chain equilibrium expectations. J Appl Probab 51(A):377\u2013389","journal-title":"J Appl Probab"},{"key":"802_CR15","doi-asserted-by":"crossref","unstructured":"Han G, Sethu H (2016) Waddling random walk: fast and accurate mining of motif statistics in large graphs. In: ICDM. IEEE, pp 181\u2013190","DOI":"10.1109\/ICDM.2016.0029"},{"key":"802_CR16","doi-asserted-by":"crossref","unstructured":"Hastings WK (1970) Monte Carlo sampling methods using Markov chains and their applications","DOI":"10.1093\/biomet\/57.1.97"},{"issue":"6","key":"802_CR17","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 16(6):372\u2013378","journal-title":"Commun ACM"},{"key":"802_CR18","unstructured":"Iyer AP, Liu Z, Jin X, Venkataraman S, Braverman V, Stoica I (2018) $$\\{$$ASAP$$\\}$$: fast, approximate graph pattern mining at scale. In: OSDI, pp 745\u2013761"},{"key":"802_CR19","doi-asserted-by":"crossref","unstructured":"Jacob PE, O\u2019Leary J, Atchad\u00e9 YF (2020) Unbiased Markov chain monte Carlo methods with couplings. JRSS Ser B 82(3):543\u2013600","DOI":"10.1111\/rssb.12336"},{"key":"802_CR20","doi-asserted-by":"crossref","unstructured":"Jain S, Seshadhri C (2017) A fast and provable method for estimating clique counts using tur\u00e1n\u2019s theorem. In: WWW, WWW \u201917, pp 441\u2013449","DOI":"10.1145\/3038912.3052636"},{"key":"802_CR21","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1145\/3366423.3380264","volume":"2020","author":"S Jain","year":"2020","unstructured":"Jain S, Seshadhri C (2020) Provably and efficiently approximating near-cliques using the tur\u00e1n shadow: peanuts. WWW 2020:1966\u20131976","journal-title":"WWW"},{"issue":"11","key":"802_CR22","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","volume":"20","author":"N Kashtan","year":"2004","unstructured":"Kashtan N, Itzkovitz S, Milo R, Alon U (2004) Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11):1746\u20131758","journal-title":"Bioinformatics"},{"key":"802_CR23","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"802_CR24","unstructured":"Liu G, Wong L (2008) Effective pruning techniques for mining quasi-cliques. In: ECML-PKDD"},{"key":"802_CR25","doi-asserted-by":"crossref","unstructured":"Massouli\u00e9 L, Le\u00a0Merrer E, Kermarrec AM, Ganesh A (2006) Peer counting and sampling in overlay networks: random walk methods. In: PODC","DOI":"10.1145\/1146381.1146402"},{"key":"802_CR26","doi-asserted-by":"crossref","unstructured":"Matsuno R, Gionis A (2020) Improved mixing time for k-subgraph sampling. In: Proceedings of the (2020) SIAM international SIAM, conference on data mining, pp 568\u2013576","DOI":"10.1137\/1.9781611976236.64"},{"issue":"429","key":"802_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1080\/01621459.1995.10476507","volume":"90","author":"P Mykland","year":"1995","unstructured":"Mykland P, Tierney L, Yu B (1995) Regeneration in Markov Chain samplers. J Am Stat Assoc 90(429):233\u2013241","journal-title":"J Am Stat Assoc"},{"key":"802_CR28","doi-asserted-by":"crossref","unstructured":"Neal RM (2001) Annealed importance sampling. Stat Comput 11(2):125\u2013139","DOI":"10.1023\/A:1008923215028"},{"key":"802_CR29","unstructured":"Neiswanger W, Wang C, Xing EP (2014) Asymptotically exact, embarrassingly parallel MCMC. UAI"},{"issue":"4","key":"802_CR30","first-page":"309","volume":"43","author":"E Nummelin","year":"1978","unstructured":"Nummelin E (1978) A splitting technique for Harris recurrent Markov Chains. Mag Probab Theory Relat Areas 43(4):309\u2013318","journal-title":"Mag Probab Theory Relat Areas"},{"key":"802_CR31","doi-asserted-by":"crossref","unstructured":"Pinar A, Seshadhri C, Vishal V (2017) Escape: efficiently counting all 5-vertex subgraphs. In: WWW, pp 1431\u20131440","DOI":"10.1145\/3038912.3052597"},{"key":"802_CR32","doi-asserted-by":"crossref","unstructured":"Propp JG, Wilson DB (1996) Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct Algor 9(1-2):223\u2013252","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O"},{"key":"802_CR33","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Towsley D (2012) On the estimation accuracy of degree distributions from graph sampling. In: CDC","DOI":"10.1109\/CDC.2012.6425857"},{"key":"802_CR34","unstructured":"Ribeiro P, Paredes P, Silva ME, Aparicio D, Silva F (2019) A survey on subgraph counting: concepts, algorithms and applications to network motifs and graphlets. arXiv:191013011"},{"key":"802_CR35","volume-title":"Monte Carlo statistical methods","author":"C Robert","year":"2013","unstructured":"Robert C, Casella G (2013) Monte Carlo statistical methods. Springer, Berlin"},{"key":"802_CR36","doi-asserted-by":"crossref","unstructured":"Rosenthal JS (1995) Minorization conditions and convergence rates for Markov Chain Monte Carlo. J Am Stat Assoc","DOI":"10.2307\/2291375"},{"key":"802_CR37","doi-asserted-by":"crossref","unstructured":"Savarese P, Kakodkar M, Ribeiro B (2018) From Monte Carlo to Las Vegas: Improving restricted Boltzmann machine training. In: AAAI","DOI":"10.1609\/aaai.v32i1.11821"},{"key":"802_CR38","doi-asserted-by":"crossref","unstructured":"Sinclair A (1992) Improved bounds for mixing rates of Markov Chains and multicommodity flow. Comb Probab Comput 1(4)","DOI":"10.1017\/S0963548300000390"},{"key":"802_CR39","doi-asserted-by":"crossref","unstructured":"Teixeira CH, Cotta L, Ribeiro B, Meira W (2018) Graph pattern mining and learning through user-defined relations. In: ICDM. IEEE, pp 1266\u20131271","DOI":"10.1109\/ICDM.2018.00170"},{"key":"802_CR40","doi-asserted-by":"crossref","unstructured":"Teixeira CHC, Kakodkar M, Dias V, Meira Jr W, Ribeiro B (2021) Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation. arXiv:2012.03879","DOI":"10.1007\/s10618-021-00802-3"},{"key":"802_CR41","doi-asserted-by":"crossref","unstructured":"Vitter JS (1985) Random sampling with a reservoir. ACM Trans Math Software (TOMS) 11(1):37\u201357","DOI":"10.1145\/3147.3165"},{"issue":"2","key":"802_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629564","volume":"9","author":"P Wang","year":"2014","unstructured":"Wang P, Lui JCS, Ribeiro B, Towsley D, Zhao J, Guan X (2014) Efficiently estimating motif statistics of large networks. ACM TKDD 9(2):1\u20137","journal-title":"ACM TKDD"},{"key":"802_CR43","doi-asserted-by":"crossref","unstructured":"Wang P, Zhao J, Zhang X, Li Z, Cheng J, Lui JCS, Towsley D, Tao J, Guan X (2017) MOSS-5: a fast method of approximating counts of 5-node graphlets in large graphs. IEEE Trans Knowl Data Eng 30(1):73\u201386","DOI":"10.1109\/TKDE.2017.2756836"},{"key":"802_CR44","doi-asserted-by":"crossref","unstructured":"Wernicke S (2006) Efficient detection of network motifs. IEEE\/ACM Trans Comput Biol Bioinf 3(4):347\u2013359","DOI":"10.1109\/TCBB.2006.51"},{"key":"802_CR45","first-page":"477","volume":"184","author":"DJ Wilkinson","year":"2006","unstructured":"Wilkinson DJ (2006) Parallel Bayesian computation. Statist Textbooks Monogr 184:477","journal-title":"Statist Textbooks Monogr"},{"key":"802_CR46","doi-asserted-by":"crossref","unstructured":"Yang C, Lyu M, Li Y, Zhao Q, Xu Y (2018) Ssrw: a scalable algorithm for estimating graphlet statistics based on random walk. In: International Springer, conference on database systems for advanced applications, pp 272\u2013288","DOI":"10.1007\/978-3-319-91452-7_18"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00802-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-021-00802-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00802-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T18:25:00Z","timestamp":1674325500000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-021-00802-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["802"],"URL":"https:\/\/doi.org\/10.1007\/s10618-021-00802-3","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2022,1]]},"assertion":[{"value":"23 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}