{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:09Z","timestamp":1779174849985,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,9,23]],"date-time":"2014-09-23T00:00:00Z","timestamp":1411430400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute"},{"name":"Application Foundation Research Program of SuZhou"},{"DOI":"10.13039\/501100002338","name":"Ministry of Education of the People's Republic of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002338","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-1065133"],"award-info":[{"award-number":["CNS-1065133"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"U.S. Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>\n            Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and Online Social Networks (OSNs). Nowadays, the massive size of some critical networks\u2014often stored in already overloaded relational databases\u2014effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose\n            <jats:italic>sampling methods<\/jats:italic>\n            to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no precomputation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known datasets and show that, for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.\n          <\/jats:p>","DOI":"10.1145\/2629564","type":"journal-article","created":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T13:34:59Z","timestamp":1412170499000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":71,"title":["Efficiently Estimating Motif Statistics of Large Networks"],"prefix":"10.1145","volume":"9","author":[{"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[{"name":"Huawei Noah's Ark Lab, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Ribeiro","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junzhou","family":"Zhao","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohong","family":"Guan","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth402"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150418"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452520.1452528"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_2_1_8_1","volume-title":"Butts","author":"Gjoka Minas","year":"2013","unstructured":"Minas Gjoka , Emily Smith , and Carter T . Butts . 2013 . Estimating clique composition and size distributions from sampled network data. ArXiv e-prints (Aug. 2013). Minas Gjoka, Emily Smith, and Carter T. Butts. 2013. Estimating clique composition and size distributions from sampled network data. ArXiv e-prints (Aug. 2013)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of WWW","author":"Stephen","year":"2013","unstructured":"Stephen J. Hardiman and Liran Katzir. 2013. Estimating clustering coefficients and size of social networks via random walk . In Proceedings of WWW 2013 . 539--550. Stephen J. Hardiman and Liran Katzir. 2013. Estimating clustering coefficients and size of social networks via random walk. In Proceedings of WWW 2013. 539--550."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687710"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.016127"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000051"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-318"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth163"},{"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\/1526709.1526809"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz . 1993 . Random walks on graphs: A survey . Combinatorics 2 (1993), 1 -- 46 . Issue \u201cPaul Erd\u00f6s is Eighty.\u201d L. Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics 2 (1993), 1--46. Issue \u201cPaul Erd\u00f6s is Eighty.\u201d","journal-title":"Combinatorics"},{"key":"e_1_2_1_21_1","volume-title":"Congressus Numerantium 30","author":"McKay Brendan D.","year":"1981","unstructured":"Brendan D. McKay . 1981 . Practical graph isomorphism . Congressus Numerantium 30 (1981), 45--87. Brendan D. McKay. 1981. Practical graph isomorphism. Congressus Numerantium 30 (1981), 45--87."},{"key":"e_1_2_1_23_1","volume-title":"Tweedie","author":"Meyn Sean","year":"2009","unstructured":"Sean Meyn and Richard L . Tweedie . 2009 . Markov Chains and Stochastic Stability. Cambridge University Press . Sean Meyn and Richard L. Tweedie. 2009. Markov Chains and Stochastic Stability. Cambridge University Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/259573.259582"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1266\/ggs.84.385"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"e_1_2_1_30_1","volume-title":"Ribeiro and Don Towsley","author":"Bruno","year":"2012","unstructured":"Bruno F. Ribeiro and Don Towsley . 2012 . On the estimation accuracy of degree distributions from graph sampling. In CDC. 5240--5247. Bruno F. Ribeiro and Don Towsley. 2012. On the estimation accuracy of degree distributions from graph sampling. In CDC. 5240--5247."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39718-2_23"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000024"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/ng881"},{"key":"e_1_2_1_34_1","volume-title":"International Scientific Conference and International Workshop Present Day Trends of Innovations. 1--6.","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky . 2012 . Data analysis in public social networks . In International Scientific Conference and International Workshop Present Day Trends of Innovations. 1--6. Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In International Scientific Conference and International Workshop Present Day Trends of Innovations. 1--6."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488502"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.51"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of IEEE INFOCOM NetSciCom","author":"Zhao Junzhou","year":"2011","unstructured":"Junzhou Zhao , John C. S. Lui , Don Towsley , Xiaohong Guan , and Yadong Zhou . 2011 . Empirical analysis of the evolution of follower network: A case study on Douban . In Proceedings of IEEE INFOCOM NetSciCom 2011. 941--946. Junzhou Zhao, John C. S. Lui, Don Towsley, Xiaohong Guan, and Yadong Zhou. 2011. Empirical analysis of the evolution of follower network: A case study on Douban. In Proceedings of IEEE INFOCOM NetSciCom 2011. 941--946."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629564","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629564","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:29Z","timestamp":1750227209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,23]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2629564"],"URL":"https:\/\/doi.org\/10.1145\/2629564","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,23]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}