{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:53:15Z","timestamp":1760233995174,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T00:00:00Z","timestamp":1615248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"institute of information and communications technology planning and evaluation (IITP)","award":["2020-0-01826"],"award-info":[{"award-number":["2020-0-01826"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Recently, researchers have paid attention to many types of huge networks such as the Internet of Things, sensor networks, social networks, and traffic networks because of their untapped potential for theoretical and practical outcomes. A major obstacle in studying large-scale networks is that their size tends to increase exponentially. In addition, access to large network databases is limited for security or physical connection reasons. In this paper, we propose a novel sampling method that works effectively for large-scale networks. The proposed approach makes multiple heterogeneous Markov chains by adjusting random-walk traits on the given network to explore the target space efficiently. This approach provides better unbiased sampling results with reduced asymptotic variance within reasonable execution time than previous random-walk-based sampling approaches. We perform various experiments on large networks databases obtained from synthesis to real\u2013world applications. The results demonstrate that the proposed method outperforms existing network sampling methods.<\/jats:p>","DOI":"10.3390\/s21051905","type":"journal-article","created":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T06:22:32Z","timestamp":1615270952000},"page":"1905","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Advanced Network Sampling with Heterogeneous Multiple Chains"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5947-5487","authenticated-orcid":false,"given":"Jaekoo","family":"Lee","sequence":"first","affiliation":[{"name":"College of Computer Science, Kookmin University, Seoul 02707, Korea"}]},{"given":"MyungKeun","family":"Yoon","sequence":"additional","affiliation":[{"name":"College of Computer Science, Kookmin University, Seoul 02707, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0106-7106","authenticated-orcid":false,"given":"Song","family":"Noh","sequence":"additional","affiliation":[{"name":"Department of Information and Telecommunication Engineering, Incheon National University, Incheon 22012, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,9]]},"reference":[{"key":"ref_1","unstructured":"(2020, July 30). Facebook Reports Second Quarter 2020 Results. Available online: https:\/\/investor.fb.com\/investor-news\/press-release-details\/2020\/Facebook-Reports-Second-Quarter-2020-Results\/default.aspx."},{"key":"ref_2","unstructured":"(2020, July 30). How Big Is the Internet of Things?. How Big Will It Get?, Available online: https:\/\/paxtechnica.org\/?page_id=738."},{"key":"ref_3","unstructured":"Krishnamachari, B., Estrin, D., and Wicker, S. (2002, January 2\u20135). The impact of data aggregation in wireless sensor networks. Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, Vienna, Austria."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1038\/35036627","article-title":"The large-scale organization of metabolic networks","volume":"407","author":"Jeong","year":"2000","journal-title":"Nature"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, V., Faloutsos, M., Chrobak, M., Lao, L., Cui, J.H., and Percus, A.G. (2005). Reducing large internet topologies for faster simulations. Networking 2005. Networking Technologies, Services, and Protocols, Springer.","DOI":"10.1007\/11422778_27"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1089\/cmb.2005.12.835","article-title":"Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data","volume":"12","author":"Sharan","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Leskovec, J., McGlohon, M., Faloutsos, C., Glance, N.S., and Hurst, M. (2007, January 26\u201328). Patterns of Cascading behavior in large blog graphs. Proceedings of the 2007 SIAM International Conference on Data Mining, Minneapolis, MN, USA.","DOI":"10.1137\/1.9781611972771.60"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1952982.1952995","article-title":"False data injection attacks against state estimation in electric power grids","volume":"14","author":"Liu","year":"2011","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Agmon, N., Shabtai, A., and Puzis, R. (2019, January 15\u201317). Deployment optimization of IoT devices through attack graph analysis. Proceedings of the 12th Conference on Security and Privacy in Wireless and Mobile Networks, New York, NY, USA.","DOI":"10.1145\/3317549.3323411"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"016128","DOI":"10.1103\/PhysRevE.66.016128","article-title":"Spread of epidemic disease on networks","volume":"66","author":"Newman","year":"2002","journal-title":"Phys. Rev. E"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_12","unstructured":"Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web, Stanford InfoLab."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"e177","DOI":"10.1093\/bioinformatics\/btl301","article-title":"Biological network comparison using graphlet degree distribution","volume":"23","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. (2010, January 6\u201310). Pregel: A system for large-scale graph processing. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807184"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"716","DOI":"10.14778\/2212351.2212354","article-title":"Distributed GraphLab: A framework for machine learning and data mining in the cloud","volume":"5","author":"Low","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Xin, R.S., Gonzalez, J.E., Franklin, M.J., and Stoica, I. (2013, January 24). Graphx: A resilient distributed graph system on spark. Proceedings of the First International Workshop on Graph Data Management Experiences and Systems, New York, NY, USA.","DOI":"10.1145\/2484425.2484427"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0370-2693(87)91197-X","article-title":"Hybrid monte carlo","volume":"195","author":"Duane","year":"1987","journal-title":"Phys. Lett. B"},{"key":"ref_18","unstructured":"Bishop, C.M. (2006). Pattern Recognition and Machine Learning, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Neal, R.M. (2011). MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, CRC press.","DOI":"10.1201\/b10905-6"},{"key":"ref_20","unstructured":"Hu, P., and Lau, W.C. (2013). A survey and taxonomy of graph sampling. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Leskovec, J., and Faloutsos, C. (2006, January 20\u201323). Sampling from large graphs. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150479"},{"key":"ref_22","unstructured":"Cormen, T.H. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1214\/aoms\/1177705148","article-title":"Snowball sampling","volume":"32","author":"Goodman","year":"1961","journal-title":"Ann. Math. Stat."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Rasti, A.H., Torkjazi, M., Rejaie, R., Duffield, N., Willinger, W., and Stutzbach, D. (2009, January 19\u201325). Respondent-driven sampling for characterizing unstructured overlays. Proceedings of the IEEE INFOCOM 2009, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5062215"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Gjoka, M., Kurant, M., Butts, C.T., and Markopoulou, A. (2010, January 14\u201319). Walking in Facebook: A case study of unbiased sampling of OSNs. Proceedings of the 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA.","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"ref_26","first-page":"231","article-title":"On Metropolis-Hastings algorithms with delayed rejection","volume":"59","author":"Mira","year":"2001","journal-title":"Metron"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Lee, C.H., Xu, X., and Eun, D.Y. (2012, January 11\u201315). Beyond random walk and metropolis-hastings samplers: Why you should not backtrack for unbiased graph sampling. Proceedings of the ACM SIGMETRICS Performance Evaluation Review, London, UK.","DOI":"10.1145\/2254756.2254795"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Avrachenkov, K., Ribeiro, B., and Towsley, D. (2010). Improving random walk estimation accuracy with uniform restarts. Algorithms and Models for the Web-Graph, Springer.","DOI":"10.1007\/978-3-642-18009-5_10"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Cheng, K. (2014, January 10\u201312). Sampling from Large Graphs with a Reservoir. Proceedings of the 2014 17th International Conference on NBiS, Salerno, Italy.","DOI":"10.1109\/NBiS.2014.25"},{"key":"ref_30","unstructured":"Aldous, D., and Fill, J. (2014). Reversible Markov Chains and Random Walks on Graphs, University of California."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1142\/S0219199707002551","article-title":"Non-backtracking random walks mix faster","volume":"9","author":"Alon","year":"2007","journal-title":"Commun. Contemp. Math."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert","year":"2002","journal-title":"Rev. Mod. Phys."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"7332","DOI":"10.1073\/pnas.0610245104","article-title":"Structure and tie strengths in mobile communication networks","volume":"104","author":"Onnela","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1007\/s10955-013-0749-1","article-title":"Scale-free graph with preferential attachment and evolving internal vertex structure","volume":"151","author":"Matuszak","year":"2013","journal-title":"J. Stat. Phys."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Mira, A., and Geyer, C.J. (2000). On non-reversible Markov chains. Monte Carlo Methods, Fields Institute\/AMS.","DOI":"10.1090\/fic\/026\/07"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1214\/154957804100000024","article-title":"General state space Markov chains and MCMC algorithms","volume":"1","author":"Roberts","year":"2004","journal-title":"Probab. Surv."},{"key":"ref_37","unstructured":"Leskovec, J., and Krevl, A. (2020, October 03). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). Konect: The koblenz network collection. Proceedings of the 22nd International Conference on World Wide Web Companion, Rio de Janeiro, Brazil.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Ahmed, N.K., Duffield, N., Neville, J., and Kompella, R. (2014, January 24\u201327). Graph sample and hold: A framework for big-graph analytics. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2623330.2623757"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Ribeiro, B., and Towsley, D. (2010, January 1\u20133). Estimating and sampling graphs with multidimensional random walks. Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, Melbourne, Australia.","DOI":"10.1145\/1879141.1879192"},{"key":"ref_41","first-page":"24","article-title":"Random sampling from a search engine\u2019s index","volume":"55","author":"Gurevich","year":"2008","journal-title":"J. ACM"},{"key":"ref_42","unstructured":"Daniel, W.W. (1990). Applied Nonparametric Statistics, PWS-Kent."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/5\/1905\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:35:18Z","timestamp":1760160918000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/5\/1905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,9]]},"references-count":42,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["s21051905"],"URL":"https:\/\/doi.org\/10.3390\/s21051905","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2021,3,9]]}}}