{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:57:56Z","timestamp":1755838676589,"version":"3.37.3"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T00:00:00Z","timestamp":1521072000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T00:00:00Z","timestamp":1521072000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-12-1-0385"],"award-info":[{"award-number":["W911NF-12-1-0385"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005423","name":"Association of Research Libraries","doi-asserted-by":"publisher","award":["W911NF-09-2-0053"],"award-info":[{"award-number":["W911NF-09-2-0053"]}],"id":[{"id":"10.13039\/100005423","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1301254","61603290"],"award-info":[{"award-number":["U1301254","61603290"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61602371"],"award-info":[{"award-number":["61602371"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Education&China Mobile Research Fund","award":["MCM20160311"],"award-info":[{"award-number":["MCM20160311"]}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["SBK2014021758"],"award-info":[{"award-number":["SBK2014021758"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]},{"name":"111 International Collaboration Program of China"},{"name":"the Prospective Joint Research of Industry-Academia-Research Joint Innovation Funding of Jiangsu Province","award":["BY2014074"],"award-info":[{"award-number":["BY2014074"]}]},{"name":"Shenzhen Basic Research Grant","award":["JCYJ20160229195940462"],"award-info":[{"award-number":["JCYJ20160229195940462"]}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"crossref","award":["2015M582663"],"award-info":[{"award-number":["2015M582663"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Basic Research Plan in Shaanxi Province of China","award":["2016JQ6034"],"award-info":[{"award-number":["2016JQ6034"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s10115-018-1178-x","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T08:08:57Z","timestamp":1521101337000},"page":"67-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast crawling methods of exploring content distributed over large graphs"],"prefix":"10.1007","volume":"59","author":[{"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junzhou","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohong","family":"Guan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"1178_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas D et al (2005) On the bias of traceroute sampling or, power-law degree distributions in regular graphs. In: STOC, pp 694\u2013703","DOI":"10.1145\/1060590.1060693"},{"key":"1178_CR2","doi-asserted-by":"crossref","unstructured":"Ahmed N et al (2014) Graph sample and hold: a framework for big-graph analytics. In: SIGKDD, pp 1446\u20131455","DOI":"10.1145\/2623330.2623757"},{"key":"1178_CR3","doi-asserted-by":"crossref","unstructured":"Avrachenkov K et al (2010) Improving random walk estimation accuracy with uniform restarts. In: WAW, pp 98\u2013109","DOI":"10.1007\/978-3-642-18009-5_10"},{"key":"1178_CR4","unstructured":"Bar-Yossef Z et al (2002) Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA, pp 623\u2013632"},{"issue":"3","key":"1178_CR5","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/1839490.1839494","volume":"4","author":"L Becchetti","year":"2010","unstructured":"Becchetti L et al (2010) Efficient algorithms for large-scale local triangle counting. TKDD 4(3):13:1\u201313:28","journal-title":"TKDD"},{"key":"1178_CR6","doi-asserted-by":"crossref","unstructured":"Bhuiyan MA et al (2012) Guise: uniform sampling of graphlets for large graph analysis. In: ICDM, pp. 91\u2013100","DOI":"10.1109\/ICDM.2012.87"},{"issue":"4","key":"1178_CR7","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1137\/S0036144503423264","volume":"46","author":"S Boyd","year":"2004","unstructured":"Boyd S et al (2004) Fastest mixing Markov chain on a graph. SIAM Rev 46(4):667\u2013689","journal-title":"SIAM Rev"},{"key":"1178_CR8","doi-asserted-by":"crossref","unstructured":"Buriol LS et al (2006) Counting triangles in data streams. In: PODS, pp 253\u2013262","DOI":"10.1145\/1142351.1142388"},{"key":"1178_CR9","unstructured":"Chen X et al (2017) A general framework for estimating graphlet statistics via random walk. In: PVLDB, pp 253\u2013264"},{"issue":"4","key":"1178_CR10","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1080\/00031305.1995.10476177","volume":"49","author":"S Chib","year":"1995","unstructured":"Chib S, Greenberg E (1995) Understanding the metropolis-hastings algorithm. Am. Stat. 49(4):327\u2013335","journal-title":"Am. Stat."},{"key":"1178_CR11","doi-asserted-by":"crossref","unstructured":"Dasgupta A et al (2012) Social sampling. In: SIGKDD, pp 235\u2013243","DOI":"10.1145\/2339530.2339572"},{"key":"1178_CR12","doi-asserted-by":"crossref","unstructured":"Duffield N et al (2003) Estimating flow distributions from sampled flow statistics. In: SIGCOMM, pp 325\u2013336","DOI":"10.1145\/863955.863992"},{"issue":"9","key":"1178_CR13","first-page":"1893","volume":"29","author":"M Gjoka","year":"2011","unstructured":"Gjoka M et al (2011) Multigraph sampling of online social networks. JSAC 29(9):1893\u20131905","journal-title":"JSAC"},{"key":"1178_CR14","doi-asserted-by":"crossref","unstructured":"Gjoka M et al (2010) Walking in facebook: a case study of unbiased sampling of OSNs. In: INFOCOM, pp 2498\u20132506","DOI":"10.1109\/INFCOM.2010.5462078"},{"issue":"3","key":"1178_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1023\/A:1011122126881","volume":"12","author":"J Goldenberg","year":"2001","unstructured":"Goldenberg J et al (2001) Talk of the network: a complex systems look at the underlying process of word-of-mouth. Mark. Lett. 12(3):211\u2013223","journal-title":"Mark. Lett."},{"issue":"1","key":"1178_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings WK (1970) Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1):97\u2013109","journal-title":"Biometrika"},{"issue":"1","key":"1178_CR17","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1525\/sp.2002.49.1.11","volume":"49","author":"DD Heckathorn","year":"2002","unstructured":"Heckathorn DD (2002) Respondent-driven sampling II: deriving valid population estimates from chain-referral samples of hidden populations. Soc Probl 49(1):11\u201334","journal-title":"Soc Probl"},{"issue":"260","key":"1178_CR18","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1080\/01621459.1952.10483446","volume":"47","author":"D Horvitz","year":"1952","unstructured":"Horvitz D, Thompson D (1952) A generalization of sampling without replacement from a finite universe. JASA 47(260):663\u2013685","journal-title":"JASA"},{"key":"1178_CR19","doi-asserted-by":"crossref","unstructured":"Jha M et al (2013) A space efficient streaming algorithm for triangle counting using the birthday paradox. In: SIGKDD, pp 589\u2013597","DOI":"10.1145\/2487575.2487678"},{"key":"1178_CR20","doi-asserted-by":"crossref","unstructured":"Jowhari H, Ghodsi M (2005) New streaming algorithms for counting triangles in graphs. In: COCOON, pp 710\u2013716","DOI":"10.1007\/11533719_72"},{"issue":"11","key":"1178_CR21","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","volume":"20","author":"N Kashtan","year":"2004","unstructured":"Kashtan N et al (2004) Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11):1746\u20131758","journal-title":"Bioinformatics"},{"key":"1178_CR22","doi-asserted-by":"crossref","unstructured":"Katzir L et al (2011) Estimating sizes of social networks via biased sampling. In: WWW, pp 597\u2013606","DOI":"10.1145\/1963405.1963489"},{"key":"1178_CR23","doi-asserted-by":"crossref","unstructured":"Kurant M et al (2011) Walking on a graph with a magnifying glass: stratified sampling via weighted random walks. In: SIGMETRICS, pp 281\u2013292","DOI":"10.1145\/1993744.1993773"},{"key":"1178_CR24","doi-asserted-by":"crossref","unstructured":"Kurant M et al (2012) Coarse-grained topology estimation via graph sampling. In: WOSN, pp. 25\u201330","DOI":"10.1145\/2342549.2342556"},{"key":"1178_CR25","unstructured":"Kurant M et al (2010) On the bias of bfs (breadth first search) and of other graph sampling techniques. In: ITC, pp 1\u20139"},{"issue":"9","key":"1178_CR26","first-page":"1799","volume":"29","author":"M Kurant","year":"2011","unstructured":"Kurant M et al (2011) Towards unbiased bfs sampling. JSAC 29(9):1799\u20131809","journal-title":"JSAC"},{"key":"1178_CR27","doi-asserted-by":"crossref","unstructured":"Kutzkov K, Pagh R (2013) On the streaming complexity of computing local clustering coefficients. In: WSDM, pp 677\u2013686","DOI":"10.1145\/2433396.2433480"},{"key":"1178_CR28","doi-asserted-by":"crossref","unstructured":"Li Z et al (2012) Socialtube: P2P-assisted video sharing in online social networks. In: INFOCOM mini conference, pp 2886\u20132890","DOI":"10.1109\/INFCOM.2012.6195721"},{"key":"1178_CR29","doi-asserted-by":"crossref","unstructured":"Lim Y, Kang U (2015) MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. In: SIGKDD, pp 685\u2013694","DOI":"10.1145\/2783258.2783285"},{"key":"1178_CR30","first-page":"1","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz L (1993) Random walks on graphs: a survey. Combinatorics 2:1\u201346","journal-title":"Combinatorics"},{"key":"1178_CR31","doi-asserted-by":"crossref","unstructured":"Malandrino F et al (2012) Proactive seeding for information cascades in cellular networks. In: INFOCOM, pp 2886\u20132890","DOI":"10.1109\/INFCOM.2012.6195543"},{"issue":"6","key":"1178_CR32","first-page":"1087","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis N et al (1953) Equations of state calculations by fast computing machines. JSAC 21(6):1087\u20131092","journal-title":"JSAC"},{"key":"1178_CR33","doi-asserted-by":"crossref","unstructured":"Mislove A et al (2007) Measurement and analysis of online social networks. In: IMC, pp 29\u201342","DOI":"10.1145\/1298306.1298311"},{"key":"1178_CR34","doi-asserted-by":"crossref","unstructured":"Mohaisen A et al (2010) Measuring the mixing time of social graphs. In: IMC, pp 390\u2013403","DOI":"10.1145\/1879141.1879191"},{"issue":"6","key":"1178_CR35","first-page":"1017","volume":"31","author":"F Murai","year":"2012","unstructured":"Murai F et al (2012) On set size distribution estimation and the characterization of large networks via sampling. JSAC 31(6):1017\u20131025","journal-title":"JSAC"},{"issue":"5","key":"1178_CR36","first-page":"385","volume":"84","author":"S Omidi","year":"2009","unstructured":"Omidi S et al (2009) Moda: an efficient algorithm for network Motif discovery in biological networks. GGS 84(5):385\u2013395","journal-title":"GGS"},{"key":"1178_CR37","doi-asserted-by":"crossref","unstructured":"Pavany A et al (2013) Counting and sampling triangles from a graph stream. In: PVLDB, pp 1870\u20131881","DOI":"10.14778\/2556549.2556569"},{"key":"1178_CR38","doi-asserted-by":"crossref","unstructured":"Rasti AH et al (2009) Respondent-driven sampling for characterizing unstructured overlays. In: INFOCOM mini-conference, pp 2701\u20132705","DOI":"10.1109\/INFCOM.2009.5062215"},{"key":"1178_CR39","doi-asserted-by":"crossref","unstructured":"Ribeiro B et al (2010) On MySpace account spans and double Pareto-like distribution of friends. In: NetSciCom, pp 1\u20136","DOI":"10.1109\/INFCOMW.2010.5466698"},{"key":"1178_CR40","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Towsley D (2010) Estimating and sampling graphs with multidimensional random walks. In: IMC, pp 390\u2013403","DOI":"10.1145\/1879141.1879192"},{"key":"1178_CR41","doi-asserted-by":"crossref","unstructured":"Ribeiro B et al (2012) Sampling directed graphs with random walks. In: INFOCOM, pp 1692\u20131700","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"1178_CR42","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1111\/j.0081-1750.2004.00152.x","volume":"34","author":"MJ Salganik","year":"2004","unstructured":"Salganik MJ, Heckathorn DD (2004) Sampling and estimation in hidden populations using respondent-driven sampling. Sociol Methodol 34:193\u2013239","journal-title":"Sociol Methodol"},{"issue":"4","key":"1178_CR43","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1002\/sam.11224","volume":"7","author":"C Seshadhri","year":"2014","unstructured":"Seshadhri C et al (2014) Wedge sampling for computing clustering coefficients and triangle counts on large graphs. Stat Anal Data Min 7(4):294\u2013307","journal-title":"Stat Anal Data Min"},{"key":"1178_CR44","doi-asserted-by":"crossref","unstructured":"Stefani LD et al (2016) Tri\u00e8st: counting local and global triangles in fully-dynamic streams with fixed memory size. In: SIGKDD, pp 825\u2013834","DOI":"10.1145\/2939672.2939771"},{"issue":"2","key":"1178_CR45","first-page":"377","volume":"17","author":"D Stutzbach","year":"2009","unstructured":"Stutzbach D et al (2009) On unbiased sampling for unstructured peer-to-peer networks. TON 17(2):377\u2013390","journal-title":"TON"},{"key":"1178_CR46","doi-asserted-by":"crossref","unstructured":"Suh B et al (2010) Want to be retweeted? large scale analytics on factors impacting retweet in twitter network. In: SocialCom, pp 177\u2013184","DOI":"10.1109\/SocialCom.2010.33"},{"key":"1178_CR47","doi-asserted-by":"crossref","unstructured":"Tsourakakis CE et al (2009) Doulion: counting triangles in massive graphs with a coin. In: KDD, pp 837\u2013846","DOI":"10.1145\/1557019.1557111"},{"issue":"2","key":"1178_CR48","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/2629564","volume":"9","author":"P Wang","year":"2014","unstructured":"Wang P et al (2014) Efficiently estimating motif statistics of large networks. TKDD 9(2):8:1\u20138:27","journal-title":"TKDD"},{"key":"1178_CR49","doi-asserted-by":"crossref","unstructured":"Wang P et al (2016) Minfer: a method of inferring motif statistics from sampled edges. In: ICDE, pp 1050\u20131061","DOI":"10.1109\/ICDE.2016.7498312"},{"issue":"4","key":"1178_CR50","first-page":"347","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke S (2006) Efficient detection of network motifs. TCBB 3(4):347\u2013359","journal-title":"TCBB"},{"issue":"8","key":"1178_CR51","first-page":"2013","volume":"28","author":"B Wu","year":"2016","unstructured":"Wu B et al (2016) Counting triangles in large graphs by random sampling. TKDE 28(8):2013\u20132026","journal-title":"TKDE"},{"key":"1178_CR52","unstructured":"Yang M et al (2004) Deployment of a large-scale peer-to-peer social network. In: WORLDS, pp 1\u20136"},{"issue":"3","key":"1178_CR53","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/2743023","volume":"9","author":"MB Zafar","year":"2015","unstructured":"Zafar MB et al (2015) Sampling content from online social networks: comparing random versus expert sampling of the twitter stream. TWEB 9(3):12:1\u201312:33","journal-title":"TWEB"},{"issue":"3","key":"1178_CR54","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/1151374.1151386","volume":"40","author":"M Zhong","year":"2006","unstructured":"Zhong M, Shen K (2006) Random walk based node sampling in self-organizing networks. SIGOPS Oper Syst Rev 40(3):49\u201355","journal-title":"SIGOPS Oper Syst Rev"},{"issue":"4","key":"1178_CR55","first-page":"26:1","volume":"40","author":"Z Zhou","year":"2013","unstructured":"Zhou Z et al (2013) Faster random walks by rewiring online social networks on-the-fly. TODS 40(4):26:1\u201326:36","journal-title":"TODS"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-018-1178-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-018-1178-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-018-1178-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:59:59Z","timestamp":1719881999000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-018-1178-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,15]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["1178"],"URL":"https:\/\/doi.org\/10.1007\/s10115-018-1178-x","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2018,3,15]]},"assertion":[{"value":"2 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}