{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:51:32Z","timestamp":1756385492941,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["JP21J10415, JP21H04872"],"award-info":[{"award-number":["JP21J10415, JP21H04872"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>Analysis of social networks with limited data access is challenging for third parties. To address this challenge, a number of studies have developed algorithms that estimate properties of social networks via a simple random walk. However, most existing algorithms do not assume private nodes that do not publish their neighbors\u2019 data when they are queried in empirical social networks. Here we propose a practical framework for estimating properties via random walk-based sampling in social networks involving private nodes. First, we develop a sampling algorithm by extending a simple random walk to the case of social networks involving private nodes. Then, we propose estimators with reduced biases induced by private nodes for the network size, average degree, and density of the node label. Our results show that the proposed estimators reduce biases induced by private nodes in the existing estimators by up to 92.6% on social network datasets involving private nodes.<\/jats:p>","DOI":"10.1145\/3561388","type":"journal-article","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T11:53:05Z","timestamp":1662465185000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Random Walk Sampling in Social Networks Involving Private Nodes"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0632-3930","authenticated-orcid":false,"given":"Kazuki","family":"Nakajima","sequence":"first","affiliation":[{"name":"Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3939-9800","authenticated-orcid":false,"given":"Kazuyuki","family":"Shudo","sequence":"additional","affiliation":[{"name":"Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242685"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1038\/35019019"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403073"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.chb.2015.05.045"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1988688.1988749"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883045"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.4626"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568019"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/PerComW.2012.6197508"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_3_2_14_2","article-title":"Facebook 500 Million Stories","year":"2010","unstructured":"Facebook. 2010. Facebook 500 Million Stories. Retrieved December 2021 from https:\/\/www.facebook.com\/notes\/facebook\/500-million-stories\/409753352130\/.","journal-title":"Retrieved December 2021 from https:\/\/www.facebook.com\/notes\/facebook\/500-million-stories\/409753352130\/"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3149887"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1111\/rssa.12059"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111011"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566997"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1000261107"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488436"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/3096941"},{"key":"e_1_3_2_24_2","first-page":"1","article-title":"Imputation of missing network data: Some simple procedures","volume":"10","author":"Huisman Mark","year":"2009","unstructured":"Mark Huisman. 2009. Imputation of missing network data: Some simple procedures. Journal of Social Structure 10 (2009), 1\u201329.","journal-title":"Journal of Social Structure"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2012.09.001"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000051"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.07.002"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993773"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_3_2_33_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved December 2021 from http:\/\/snap.stanford.edu\/data","journal-title":"Retrieved December 2021 from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113345"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00090"},{"key":"e_1_3_2_37_2","first-page":"353","volume-title":"Proceedings of the Combinatorics, Paul Erd\u0151s is Eighty","author":"Lov\u00e1sz L.","year":"1996","unstructured":"L. Lov\u00e1sz. 1996. Random walks on graphs: A survey. In Proceedings of the Combinatorics, Paul Erd\u0151s is Eighty. 353\u2013398."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-985X.2011.00711.x"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.28.436"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403116"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-82367-1"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735707"},{"key":"e_1_3_2_44_2","volume-title":"Networks(2nd. ed.).","author":"Newman M. E. J.","year":"2018","unstructured":"M. E. J. Newman. 2018. Networks(2nd. ed.).Oxford University Press."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000024"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.05.001"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1111\/rssa.12180"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.0081-1750.2004.00152.x"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2013.09.003"},{"key":"e_1_3_2_52_2","volume-title":"Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1214\/11-EJS630"},{"key":"e_1_3_2_54_2","article-title":"Twitter API GET followers\/ids","year":"2021","unstructured":"Twitter. 2021. Twitter API GET followers\/ids. Retrieved from https:\/\/developer.twitter.com\/en\/docs\/accounts-and-users\/follow-search-get-users\/api-reference\/get-followers-ids.html. Accessed on December 2021.","journal-title":"Retrieved from https:\/\/developer.twitter.com\/en\/docs\/accounts-and-users\/follow-search-get-users\/api-reference\/get-followers-ids.html"},{"key":"e_1_3_2_55_2","article-title":"Twitter API GET friends\/ids","year":"2021","unstructured":"Twitter. 2021. Twitter API GET friends\/ids. Retrieved from https:\/\/developer.twitter.com\/en\/docs\/accounts-and-users\/follow-search-get-users\/api-reference\/get-friends-ids.html. Accessed on December 2021.","journal-title":"Retrieved from https:\/\/developer.twitter.com\/en\/docs\/accounts-and-users\/follow-search-get-users\/api-reference\/get-friends-ids.html"},{"key":"e_1_3_2_56_2","first-page":"79","article-title":"Probability based estimation theory for respondent driven sampling","volume":"24","author":"Volz Erik","year":"2008","unstructured":"Erik Volz and Douglas D. Heckathorn. 2008. Probability based estimation theory for respondent driven sampling. Journal of Official Statistics 24 (2008), 79\u201397.","journal-title":"Journal of Official Statistics"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1604138113"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00083"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/2847526"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561388","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:35Z","timestamp":1750186835000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561388"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3561388"],"URL":"https:\/\/doi.org\/10.1145\/3561388","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"2021-12-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}