{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T04:50:49Z","timestamp":1749271849272,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T00:00:00Z","timestamp":1655942400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T00:00:00Z","timestamp":1655942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["No.61772216","61832020"],"award-info":[{"award-number":["No.61772216","61832020"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61821003"],"award-info":[{"award-number":["61821003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Defense Preliminary Research Project","award":["2017010201010103"],"award-info":[{"award-number":["2017010201010103"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10115-022-01691-8","type":"journal-article","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T14:03:59Z","timestamp":1655993039000},"page":"1909-1935","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Random walk on node cliques for high-quality samples to estimate large graphs with high accuracies and low costs"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4845-9868","authenticated-orcid":false,"given":"Lingling","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Fang","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Hong","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Feng","sequence":"additional","affiliation":[]},{"given":"Yanwen","family":"Xie","sequence":"additional","affiliation":[]},{"given":"Zhiwei","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,23]]},"reference":[{"issue":"11","key":"1691_CR1","first-page":"1430","volume":"10","author":"NK Ahmed","year":"2017","unstructured":"Ahmed NK, Duffield N, Willke TL, Rossi RA (2017) On sampling from massive graph streams. VLDB 10(11):1430\u20131441","journal-title":"VLDB"},{"key":"1691_CR2","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-18009-5_10","volume-title":"Algorithms and models for the Web-Graph","author":"K Avrachenkov","year":"2010","unstructured":"Avrachenkov K, Ribeiro B, Towsley D (2010) Improving random walk estimation accuracy with uniform restarts. In: Avrachenkov K et al (eds) Algorithms and models for the Web-Graph. Springer, Berlin, pp 98\u2013109"},{"key":"1691_CR3","doi-asserted-by":"crossref","unstructured":"Bhuiyan M.\u00a0A, Rahman M, Rahman M, Al\u00a0Hasan M.(2012) Guise: uniform sampling of graphlets for large graph analysis. In: 2012 IEEE 12th international conference on data mining, IEEE, pp 91\u2013100","DOI":"10.1109\/ICDM.2012.87"},{"key":"1691_CR4","doi-asserted-by":"crossref","unstructured":"Chen F, Lov\u00e1sz L, Pak I.(1999) Lifting markov chains to speed up mixing. In: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, pp 275\u2013281","DOI":"10.1145\/301250.301315"},{"key":"1691_CR5","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3083318","author":"J Chen","year":"2021","unstructured":"Chen J, Gong Z, Mo J, Wang W, Wang C, Dong X, Liu W, Wu K (2021) Self-training enhanced: network embedding and overlapping community detection with adversarial learning. IEEE Trans Neural Netw Learn Syst. https:\/\/doi.org\/10.1109\/TNNLS.2021.3083318","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"issue":"3","key":"1691_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.14778\/3021924.3021940","volume":"10","author":"X Chen","year":"2016","unstructured":"Chen X, Li Y, Wang P, Lui J (2016) A general framework for estimating graphlet statistics via random walk. Proc VLDB Endow 10(3):253\u2013264","journal-title":"Proc VLDB Endow"},{"key":"1691_CR7","doi-asserted-by":"crossref","unstructured":"Chiericetti F, Dasgupta A, Kumar R, Lattanzi S, Sarl\u00f3s T (2016) On sampling nodes in a network. In: Proceedings of the 25th international conference on World Wide Web, international World Wide Web conferences steering committee, pp 471\u2013481","DOI":"10.1145\/2872427.2883045"},{"issue":"2\u20133","key":"1691_CR8","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1016\/j.laa.2007.05.021","volume":"428","author":"W-K Ching","year":"2008","unstructured":"Ching W-K, Ng MK, Fung ES (2008) Higher-order multivariate markov chains and their applications. Linear Algebra Appl 428(2\u20133):492\u2013507","journal-title":"Linear Algebra Appl"},{"issue":"434","key":"1691_CR9","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1080\/01621459.1996.10476956","volume":"91","author":"MK Cowles","year":"1996","unstructured":"Cowles MK, Carlin BP (1996) Markov chain Monte Carlo convergence diagnostics: a comparative review. J Am Stat Assoc 91(434):883\u2013904","journal-title":"J Am Stat Assoc"},{"key":"1691_CR10","doi-asserted-by":"publisher","DOI":"10.1145\/3524105","author":"Y Cui","year":"2022","unstructured":"Cui Y, Li X, Li J, Wang H, Chen X (2022) A survey of sampling method for social media embeddedness relationship. ACM Comput Surv. https:\/\/doi.org\/10.1145\/3524105","journal-title":"ACM Comput Surv"},{"key":"1691_CR11","first-page":"825","volume":"11","author":"L De Stefani","year":"2016","unstructured":"De Stefani L, Epasto A, Riondato M, Upfal E (2016) Tri\u00e8st: Counting local and global triangles in fully-dynamic streams with fixed memory size. ACM Trans Knowl Discov Data (TKDD) 11:825\u2013834","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"1691_CR12","doi-asserted-by":"crossref","unstructured":"Gjoka M, Kurant M, Butts C.\u00a0T, Markopoulou A (2010) Walking in facebook: A case study of unbiased sampling of osns. In: 2010 Proceedings IEEE Infocom, IEEE, PP 1\u20139","DOI":"10.1109\/INFCOM.2010.5462078"},{"issue":"9","key":"1691_CR13","doi-asserted-by":"publisher","first-page":"1872","DOI":"10.1109\/JSAC.2011.111011","volume":"29","author":"M Gjoka","year":"2011","unstructured":"Gjoka M, Kurant M, Butts CT, Markopoulou A (2011) Practical recommendations on crawling online social networks. IEEE J Sel Areas Commun 29(9):1872\u20131892","journal-title":"IEEE J Sel Areas Commun"},{"key":"1691_CR14","doi-asserted-by":"crossref","unstructured":"Jha M, Seshadhri C, Pinar A (2013) A space efficient streaming algorithm for triangle counting using the birthday paradox. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 589\u2013597","DOI":"10.1145\/2487575.2487678"},{"key":"1691_CR15","doi-asserted-by":"crossref","unstructured":"Jowhari H, Ghodsi M (2005) New streaming algorithms for counting triangles in graphs. In: International computing and combinatorics conference, Springer, pp 710\u2013716.","DOI":"10.1007\/11533719_72"},{"issue":"5","key":"1691_CR16","first-page":"590","volume":"4","author":"J Konc","year":"2007","unstructured":"Konc J, Janezic D (2007) An improved branch and bound algorithm for the maximum clique problem. Proteins 4(5):590\u2013596","journal-title":"Proteins"},{"key":"1691_CR17","doi-asserted-by":"crossref","unstructured":"Kurant M, Gjoka M, Butts C.\u00a0T, Markopoulou A.(2011) Walking on a graph with a magnifying glass: stratified sampling via weighted random walks. In: Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, ACM, pp 281\u2013292","DOI":"10.1145\/1993744.1993773"},{"issue":"9","key":"1691_CR18","doi-asserted-by":"publisher","first-page":"1799","DOI":"10.1109\/JSAC.2011.111005","volume":"29","author":"M Kurant","year":"2011","unstructured":"Kurant M, Markopoulou A, Thiran P (2011) Towards unbiased bfs sampling. IEEE J Sel Areas Commun 29(9):1799\u20131809","journal-title":"IEEE J Sel Areas Commun"},{"key":"1691_CR19","doi-asserted-by":"crossref","unstructured":"Kutzkov K, Pagh R (2013) On the streaming complexity of computing local clustering coefficients. In: Proceedings of the sixth ACM international conference on Web search and data mining, ACM, pp 677\u2013686","DOI":"10.1145\/2433396.2433480"},{"key":"1691_CR20","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1145\/2318857.2254795","volume":"40","author":"C-H Lee","year":"2012","unstructured":"Lee C-H, Xu X, Eun DY (2012) Beyond random walk and metropolis-hastings samplers: why you should not backtrack for unbiased graph sampling. ACM SIGMETRICS Perform Eval Rev 40:319\u2013330","journal-title":"ACM SIGMETRICS Perform Eval Rev"},{"issue":"1","key":"1691_CR21","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1232722.1232727","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Adamic LA, Huberman BA (2007) The dynamics of viral marketing. ACM Trans Web (TWEB) 1(1):5","journal-title":"ACM Trans Web (TWEB)"},{"issue":"1","key":"1691_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29\u2013123","journal-title":"Internet Math"},{"key":"1691_CR23","doi-asserted-by":"crossref","unstructured":"Li R.-H, Yu J.\u00a0X, Huang X, Cheng H (2014) Random-walk domination in large graphs. In: 2014 IEEE 30th international conference on data engineering, IEEE, pp 736\u2013747.","DOI":"10.1109\/ICDE.2014.6816696"},{"key":"1691_CR24","doi-asserted-by":"crossref","unstructured":"R.-H. Li, J.\u00a0X. Yu, L.\u00a0Qin, R.\u00a0Mao, and T.\u00a0Jin (2015) On random walk based graph sampling. In: 2015 IEEE 31st international conference on data engineering, IEEE, pp 927\u2013938","DOI":"10.1109\/ICDE.2015.7113345"},{"issue":"3","key":"1691_CR25","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1080\/03081087.2013.777436","volume":"62","author":"W Li","year":"2014","unstructured":"Li W, Ng MK (2014) On the limiting probability distribution of a transition probability tensor. Linear Multili Algebra 62(3):362\u2013385","journal-title":"Linear Multili Algebra"},{"issue":"7","key":"1691_CR26","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1002\/asi.20591","volume":"58","author":"D Liben-Nowell","year":"2007","unstructured":"Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Assoc Inf Sci Technol 58(7):1019\u20131031","journal-title":"J Assoc Inf Sci Technol"},{"key":"1691_CR27","doi-asserted-by":"crossref","unstructured":"Lim Y, Kang U (2015) Mascot: memory-efficient and accurate sampling for counting local triangles in graph streams. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, ACM, pp 685\u2013694","DOI":"10.1145\/2783258.2783285"},{"issue":"1","key":"1691_CR28","first-page":"1","volume":"2","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz L (1993) Random walks on graphs: a survey. Combinatorics Paul Erdos Eighty 2(1):1\u201346","journal-title":"Combinatorics Paul Erdos Eighty"},{"key":"1691_CR29","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz L,Winkler P (1995) Efficient stopping rules for markov chains. In: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, ACM, pp 76\u201382","DOI":"10.1145\/225058.225086"},{"key":"1691_CR30","doi-asserted-by":"crossref","unstructured":"Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, ACM, pp 29\u201342","DOI":"10.1145\/1298306.1298311"},{"key":"1691_CR31","doi-asserted-by":"crossref","unstructured":"Mohaisen A, Yun A, Kim Y (2010) Measuring the mixing time of social graphs. In: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, ACM, pp 383\u2013389","DOI":"10.1145\/1879141.1879191"},{"issue":"6","key":"1691_CR32","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1109\/JSAC.2013.130604","volume":"31","author":"F Murai","year":"2013","unstructured":"Murai F, Ribeiro B, Towsley D, Wang P (2013) On set size distribution estimation and the characterization of large networks via sampling. IEEE J Sel Areas Commun 31(6):1017\u20131025","journal-title":"IEEE J Sel Areas Commun"},{"key":"1691_CR33","doi-asserted-by":"crossref","unstructured":"Nakajima K, Shudo K (2021) Social graph restoration via random walk sampling. arXiv preprint arXiv:2111.11966,","DOI":"10.1109\/ICDE53745.2022.00065"},{"key":"1691_CR34","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Towsley D (2010) Estimating and sampling graphs with multidimensional random walks. In: Proceedings of the 10th ACM SIGCOMM conference on Internet measurement, ACM, pp 390\u2013403","DOI":"10.1145\/1879141.1879192"},{"key":"1691_CR35","doi-asserted-by":"crossref","unstructured":"Ribeiro B, Wang P, Murai F, Towsley D (2012) Sampling directed graphs with random walks. In: 2012 Proceedings IEEE INFOCOM, IEEE, pp 1692\u20131700","DOI":"10.1109\/INFCOM.2012.6195540"},{"issue":"2","key":"1691_CR36","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1109\/TNET.2008.2001730","volume":"17","author":"D Stutzbach","year":"2009","unstructured":"Stutzbach D, Rejaie R, Duffield N, Sen S, Willinger W (2009) On unbiased sampling for unstructured peer-to-peer networks. IEEE\/ACM Trans Netw (TON) 17(2):377\u2013390","journal-title":"IEEE\/ACM Trans Netw (TON)"},{"issue":"2","key":"1691_CR37","first-page":"8","volume":"9","author":"P Wang","year":"2014","unstructured":"Wang P, Lui J, Ribeiro B, Towsley D, Zhao J, Guan X (2014) Efficiently estimating motif statistics of large networks. ACM Trans Know Discov Data (TKDD) 9(2):8","journal-title":"ACM Trans Know Discov Data (TKDD)"},{"issue":"2","key":"1691_CR38","first-page":"162","volume":"11","author":"P Wang","year":"2017","unstructured":"Wang P, Qi Y, Sun Y, Zhang X, Tao J, Guan X (2017) Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. VLDB 11(2):162\u2013175","journal-title":"VLDB"},{"key":"1691_CR39","unstructured":"Wang P, Ribeiro B, Zhao J, Lui J, Towsley D, Guan X (2013) Practical characterization of large networks using neighborhood information. arXiv preprint arXiv:1311.3037"},{"key":"1691_CR40","first-page":"1","volume":"59","author":"P Wang","year":"2018","unstructured":"Wang P, Zhao J, Lui JC, Towsley D, Guan X (2018) Fast crawling methods of exploring content distributed over large graphs. Know Inf Syst 59:1\u201326","journal-title":"Know Inf Syst"},{"key":"1691_CR41","doi-asserted-by":"crossref","unstructured":"Xu X, Lee CH et\u00a0al (2017) Challenging the limits: sampling online social networks with cost constraints. In: IEEE INFOCOM 2017-IEEE conference on computer communications","DOI":"10.1109\/INFOCOM.2017.8057169"},{"issue":"1","key":"1691_CR42","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","volume":"42","author":"J Yang","year":"2015","unstructured":"Yang J, Leskovec J (2015) Defining and evaluating network communities based on ground-truth. Know Inf Syst 42(1):181\u2013213","journal-title":"Know Inf Syst"},{"key":"1691_CR43","doi-asserted-by":"crossref","unstructured":"Yi P, Xie H, Li Y, Lui JC (2021) A bootstrapping approach to optimize random walk based statistical estimation over graphs. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), IEEE, pp 900\u2013911","DOI":"10.1109\/ICDE51399.2021.00083"},{"issue":"3","key":"1691_CR44","first-page":"12","volume":"9","author":"MB Zafar","year":"2015","unstructured":"Zafar MB, Bhattacharya P, Ganguly N, Gummadi KP, Ghosh S (2015) Sampling content from online social networks: comparing random versus expert sampling of the twitter stream. ACM Trans Web (TWEB) 9(3):12","journal-title":"ACM Trans Web (TWEB)"},{"key":"1691_CR45","doi-asserted-by":"crossref","unstructured":"Zaykov AL, Vaganov DA, Guleva VY (2020) Diffusion dynamics prediction on networks using sub-graph motif distribution. In: International conference on complex networks and their applications, Springer, pp 482\u2013493","DOI":"10.1007\/978-3-030-65347-7_40"},{"key":"1691_CR46","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.105891","volume":"198","author":"L Zhang","year":"2020","unstructured":"Zhang L, Jiang H, Wang F, Feng D (2020) Draws: a dual random-walk based sampling method to efficiently estimate distributions of degree and clique size over social networks. Know-Based Syst 198:105891","journal-title":"Know-Based Syst"},{"issue":"1","key":"1691_CR47","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s10618-018-0587-5","volume":"33","author":"J Zhao","year":"2019","unstructured":"Zhao J, Wang P, Lui J, Towsley D, Guan X (2019) Sampling online social networks by random walk with indirect jumps. Data Min Know Discov 33(1):24\u201357","journal-title":"Data Min Know Discov"},{"issue":"2","key":"1691_CR48","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1109\/TVCG.2020.3030428","volume":"27","author":"Y Zhao","year":"2020","unstructured":"Zhao Y, Jiang H, Qin Y, Xie H, Wu Y, Liu S, Zhou Z, Xia J, Zhou F et al (2020) Preserving minority structures in graph sampling. IEEE Trans Vis Comput Gr 27(2):1698\u20131708","journal-title":"IEEE Trans Vis Comput Gr"},{"key":"1691_CR49","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2021.3107297","author":"Y Zhao","year":"2021","unstructured":"Zhao Y, Shi J, Liu J, Zhao J, Zhou F, Zhang W, Chen K, Zhao X, Zhu C, Chen W (2021) Evaluating effects of background stories on graph perception. IEEE Trans Vis Comput Gr. https:\/\/doi.org\/10.1109\/TVCG.2021.3107297","journal-title":"IEEE Trans Vis Comput Gr"},{"issue":"3","key":"1691_CR50","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 40(3):49\u201355","journal-title":"SIGOPS"},{"issue":"10","key":"1691_CR51","first-page":"1034","volume":"8","author":"Z Zhou","year":"2015","unstructured":"Zhou Z, Zhang N, Das G (2015) Leveraging history for faster sampling of online social networks. VLDB 8(10):1034\u20131045","journal-title":"VLDB"},{"issue":"4","key":"1691_CR52","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/2847526","volume":"40","author":"Z Zhou","year":"2016","unstructured":"Zhou Z, Zhang N, Gong Z, Das G (2016) Faster random walks by rewiring online social networks on-the-fly. ACM Trans Database Syst (TODS) 40(4):26","journal-title":"ACM Trans Database Syst (TODS)"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01691-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-022-01691-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-022-01691-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,9]],"date-time":"2023-02-09T04:49:35Z","timestamp":1675918175000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-022-01691-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,23]]},"references-count":52,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1691"],"URL":"https:\/\/doi.org\/10.1007\/s10115-022-01691-8","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2022,6,23]]},"assertion":[{"value":"11 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}