{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T04:10:01Z","timestamp":1773115801177,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,9,28]],"date-time":"2015-09-28T00:00:00Z","timestamp":1443398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2015,10,26]]},"abstract":"<jats:p>This work addresses the problem of estimating social network measures. Specifically, the measures at hand are the network average and global clustering coefficients and the number of registered users. The algorithms at hand (1) assume no prior knowledge about the network and (2) access the network using only the publicly available interface. More precisely, this work provides (a) a unified approach for clustering coefficients estimation and (b) a new network size estimator. The unified approach for the clustering coefficients yields the first external access algorithm for estimating the global clustering coefficient. The new network size estimator offers improved accuracy compared to prior art estimators.<\/jats:p>\n          <jats:p>Our approach is to view a social network as an undirected graph and use the public interface to retrieve a random walk. To estimate the clustering coefficient, the connectivity of each node in the random walk sequence is tested in turn. We show that the error drops exponentially in the number of random walk steps. For the network size estimation we offer a generalized view of prior art estimators that in turn yields an improved estimator. All algorithms are validated on several publicly available social network datasets.<\/jats:p>","DOI":"10.1145\/2790304","type":"journal-article","created":{"date-parts":[[2015,9,29]],"date-time":"2015-09-29T19:22:29Z","timestamp":1443554549000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Estimating Clustering Coefficients and Size of Social Networks via Random Walk"],"prefix":"10.1145","volume":"9","author":[{"given":"Liran","family":"Katzir","sequence":"first","affiliation":[{"name":"Microsoft Research, Advanced Technology Labs, Herzliya, Israel"}]},{"given":"Stephen J.","family":"Hardiman","sequence":"additional","affiliation":[{"name":"Research was conducted while the author was unaffiliated, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2015,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Louigi Addario-Berry and Tao Lei. 2012. The mixing time of the Newman--Watts small world. In SODA. 1661--1668.   Louigi Addario-Berry and Tao Lei. 2012. The mixing time of the Newman--Watts small world. In SODA. 1661--1668.","DOI":"10.1137\/1.9781611973099.131"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242685"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_4_1","volume-title":"Large-Scale Data Mining: Theory and Applications (KDD Workshop).","author":"Avron Haim","year":"2010"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411514"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526716"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019643.2019645"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_11_1","unstructured":"Kai-Min Chung Henry Lam Zhenming Liu and Michael Mitzenmacher. 2012. Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. In STACS. 124--135.  Kai-Min Chung Henry Lam Zhenming Liu and Michael Mitzenmacher. 2012. Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. In STACS. 124--135."},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"Characterization of complex networks: A survey of measurements","volume":"56","author":"Costa Luciano","year":"2006","journal-title":"Adv. Phys."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Bradley Efron and Robert J. Tibshirani. 1993. An Introduction to the Bootstrap. Chapman & Hall New York.  Bradley Efron and Robert J. Tibshirani. 1993. An Introduction to the Bootstrap. Chapman & Hall New York.","DOI":"10.1007\/978-1-4899-4541-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833840"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566997"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2009-00292-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1751-5823.2003.tb00485.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Jerome Kunegis. 2012. KONECT\u2014The Koblenz Network Collection. http:\/\/konect.uni-koblenz.de\/.  Jerome Kunegis. 2012. KONECT\u2014The Koblenz Network Collection. http:\/\/konect.uni-koblenz.de\/.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176347265"},{"key":"e_1_2_1_21_1","unstructured":"Maciej Kurant Carter T. Butts and Athina Markopoulou. 2012. Graph size estimation. CoRR abs\/1210.0460.  Maciej Kurant Carter T. Butts and Athina Markopoulou. 2012. Graph size estimation. CoRR abs\/1210.0460."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"David A. Levin Yuval Peres and Elizabeth L. Wilmer. 2008. Markov Chains and Mixing Times. American Mathematical Society.  David A. Levin Yuval Peres and Elizabeth L. Wilmer. 2008. Markov Chains and Mixing Times. American Mathematical Society.","DOI":"10.1090\/mbk\/058"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694954"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Peter Winkler. 1998. Mixing times. Microsurveys in discrete. In DimacsWorkshop.  L\u00e1szl\u00f3 Lov\u00e1sz and Peter Winkler. 1998. Mixing times. Microsurveys in discrete. In DimacsWorkshop.","DOI":"10.1090\/dimacs\/041\/06"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146402"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.7332"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Reuven Y. Rubinstein and Dirk P. Kroese. 2007. Simulation and the Monte Carlo Method (2nd. ed.). Wiley Series in Probability and Statistics.  Reuven Y. Rubinstein and Dirk P. Kroese. 2007. Simulation and the Monte Carlo Method (2nd. ed.). Wiley Series in Probability and Statistics.","DOI":"10.1002\/9780470230381"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00108"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.32"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2790304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2790304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:06Z","timestamp":1750223226000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2790304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,28]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,10,26]]}},"alternative-id":["10.1145\/2790304"],"URL":"https:\/\/doi.org\/10.1145\/2790304","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,28]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}