{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:16:40Z","timestamp":1779175000043,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p>\n            Graphlets are induced subgraph patterns and have been frequently applied to characterize the local topology structures of graphs across various domains, e.g., online social networks (OSNs) and biological networks. Discovering and computing graphlet statistics are highly challenging. First, the massive size of real-world graphs makes the exact computation of graphlets extremely expensive. Secondly, the graph topology may not be readily available so one has to resort to web crawling using the available application programming interfaces (APIs). In this work, we propose a general and novel framework to estimate graphlet statistics of \"\n            <jats:italic>any size.<\/jats:italic>\n            \" Our framework is based on collecting samples through consecutive steps of random walks. We derive an analytical bound on the sample size (via the Chernoff-Hoeffding technique) to guarantee the convergence of our unbiased estimator. To further improve the accuracy, we introduce two novel optimization techniques to reduce the lower bound on the sample size. Experimental evaluations demonstrate that our methods outperform the state-of-the-art method up to an order of magnitude both in terms of accuracy and time cost.\n          <\/jats:p>","DOI":"10.14778\/3021924.3021940","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T15:29:41Z","timestamp":1485271781000},"page":"253-264","source":"Crossref","is-referenced-by-count":56,"title":["A general framework for estimating graphlet statistics via random walk"],"prefix":"10.14778","volume":"10","author":[{"given":"Xiaowei","family":"Chen","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongkun","family":"Li","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pinghui","family":"Wang","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"KONECT Datasets: The koblenz network collection. http:\/\/konect.uni-koblenz.de 2015.  KONECT Datasets: The koblenz network collection. http:\/\/konect.uni-koblenz.de 2015."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_7_1","volume-title":"A general framework for estimating graphlet statistics via random walk. arXiv:1603.07504","author":"Chen X.","year":"2016","unstructured":"X. Chen , Y. Li , P. Wang , and J. Lui . A general framework for estimating graphlet statistics via random walk. arXiv:1603.07504 , 2016 . X. Chen, Y. Li, P. Wang, and J. Lui. A general framework for estimating graphlet statistics via random walk. arXiv:1603.07504, 2016."},{"key":"e_1_2_1_8_1","first-page":"124","volume-title":"STACS","author":"Chung K.-M.","year":"2012","unstructured":"K.-M. Chung , H. Lam , Z. Liu , and M. Mitzenmacher . Chernoff-hoeffding bounds for markov chains: Generalized and simplified . STACS , pages 124 -- 135 , 2012 . K.-M. Chung, H. Lam, Z. Liu, and M. Mitzenmacher. Chernoff-hoeffding bounds for markov chains: Generalized and simplified. STACS, pages 124--135, 2012."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783413"},{"key":"e_1_2_1_10_1","volume-title":"Spring Quarter","author":"Geyer C. J.","year":"1998","unstructured":"C. J. Geyer . Markov chain monte carlo lecture notes. Course notes , Spring Quarter , 1998 . C. J. Geyer. Markov chain monte carlo lecture notes. Course notes, Spring Quarter, 1998."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833840"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488436"},{"key":"e_1_2_1_13_1","first-page":"559","volume-title":"Bioinformatics","author":"Ho\u010devar T.","year":"2014","unstructured":"T. Ho\u010devar and J. Dem\u0161ar . A combinatorial approach to graphlet counting . Bioinformatics , pages 559 -- 565 , 2014 . T. Ho\u010devar and J. Dem\u0161ar. A combinatorial approach to graphlet counting. Bioinformatics, pages 559--565, 2014."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254795"},{"key":"e_1_2_1_18_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data 2014."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113345"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"Combinatorics","author":"Lov\u00b4sz L.","year":"1993","unstructured":"L. Lov\u00b4sz . Random walks on graphs: A survey . In Combinatorics , pages 1 -- 46 . 1993 . L. Lov\u00b4sz. Random walks on graphs: A survey. In Combinatorics, pages 1--46. 1993."},{"key":"e_1_2_1_21_1","first-page":"257","article-title":"Uncovering biological network function via graphlet degree signatures","volume":"6","author":"Milenkovi\u00e6 T.","year":"2008","unstructured":"T. Milenkovi\u00e6 and N. Pr\u017eulj . Uncovering biological network function via graphlet degree signatures . Cancer Informatics , 6 : 257 -- 273 , 2008 . T. Milenkovi\u00e6 and N. Pr\u017eulj. Uncovering biological network function via graphlet degree signatures. Cancer Informatics, 6:257--273, 2008.","journal-title":"Cancer Informatics"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2009.0192"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_2_1_26_1","volume-title":"Finite Markov Chains and Algorithmic Applications","author":"H.","year":"2000","unstructured":"H. OLLE. Finite Markov Chains and Algorithmic Applications . Cambridge University Press , 2000 . H. OLLE. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2000."},{"key":"e_1_2_1_27_1","volume-title":"methods and examples","author":"Owen A. B.","year":"2013","unstructured":"A. B. Owen . Monte Carlo theory , methods and examples . 2013 . A. B. Owen. Monte Carlo theory, methods and examples. 2013."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq091"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398454"},{"key":"e_1_2_1_30_1","unstructured":"R. A. Rossi and N. K. Ahmed. Social network collection - networkrepository. http:\/\/networkrepository.com\/soc.php 2013.  R. A. Rossi and N. K. Ahmed. Social network collection - networkrepository. http:\/\/networkrepository.com\/soc.php 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.2"},{"key":"e_1_2_1_32_1","first-page":"488","volume-title":"Artificial Intelligence and Statistics","author":"Shervashidze N.","year":"2009","unstructured":"N. Shervashidze , S. Vishwanathan , T. Petri , K. Mehlhorn , and K. Borgwardt . Efficient graphlet kernels for large graph comparison . In Artificial Intelligence and Statistics , pages 488 -- 495 , 2009 . N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pages 488--495, 2009."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488502"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498312"},{"key":"e_1_2_1_37_1","volume-title":"Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. arXiv:1509.08089","author":"Wang P.","year":"2015","unstructured":"P. Wang , J. Tao , J. Zhao , and X. Guan . Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. arXiv:1509.08089 , 2015 . P. Wang, J. Tao, J. Zhao, and X. Guan. Moss: A scalable tool for efficiently sampling and counting 4-and 5-node graphlets. arXiv:1509.08089, 2015."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848229"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794373"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3021924.3021940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:30:19Z","timestamp":1672219819000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3021924.3021940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.14778\/3021924.3021940"],"URL":"https:\/\/doi.org\/10.14778\/3021924.3021940","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}