{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:56:47Z","timestamp":1760597807777,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":46,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Azrieli Foundation"},{"name":"Laboratory Directed Research and Development program at Sandia National Laboratories","award":["DE-NA-0003525"],"award-info":[{"award-number":["DE-NA-0003525"]}]},{"name":"NSF TRIPODS","award":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}]},{"name":"Blavatnik fund"},{"name":"Simons Institute"},{"name":"Israel Science Foundation","award":["Grant No.~671\/13"],"award-info":[{"award-number":["Grant No.~671\/13"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186111","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"449-458","source":"Crossref","is-referenced-by-count":21,"title":["Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples"],"prefix":"10.1145","author":[{"given":"Talya","family":"Eden","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Shweta","family":"Jain","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA, USA"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}]}],"member":"320","reference":[{"doi-asserted-by":"crossref","unstructured":"D. Achlioptas, A. Clauset, D. Kempe, and C. Moore. 2009. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM Vol. 56, 4 (2009).","key":"key-10.1145\/3178876.3186111-1","DOI":"10.1145\/1538902.1538905"},{"unstructured":"N.K. Ahmed, J. Neville, and R. Kompella. 2010. Reconsidering the Foundations of Network Sampling. In WIN 10.","key":"key-10.1145\/3178876.3186111-2"},{"doi-asserted-by":"crossref","unstructured":"N. Ahmed, J. Neville, and R. Kompella. 2012. Space-Efficient Sampling from Social Activity Streams SIGKDD BigMine. 1--8.","key":"key-10.1145\/3178876.3186111-3","DOI":"10.1145\/2351316.2351324"},{"doi-asserted-by":"crossref","unstructured":"Nesreen K Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. 2014 a. Graph sample and hold: A framework for big-graph analytics SIGKDD. ACM, ACM, 1446--1455.","key":"key-10.1145\/3178876.3186111-4","DOI":"10.1145\/2623330.2623757"},{"unstructured":"Nesreen K Ahmed, Jennifer Neville, and Ramana Kompella. 2014 b. Network sampling: From static to streaming graphs. TKDD Vol. 8, 2 (2014), 7.","key":"key-10.1145\/3178876.3186111-5"},{"doi-asserted-by":"crossref","unstructured":"Sinan G. Aksoy, Tamara G. Kolda, and Ali Pinar. 2017. Measuring and modeling bipartite graphs with community structure. Journal of Complex Networks (2017). to appear.","key":"key-10.1145\/3178876.3186111-6","DOI":"10.1093\/comnet\/cnx001"},{"doi-asserted-by":"crossref","unstructured":"Albert-László Barabási and Réka Albert. 1999. Emergence of Scaling in Random Networks. Science Vol. 286 (Oct. 1999), 509--512.","key":"key-10.1145\/3178876.3186111-7","DOI":"10.1126\/science.286.5439.509"},{"doi-asserted-by":"crossref","unstructured":"A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. 2000. Graph structure in the web. Computer Networks Vol. 33 (2000), 309--320.","key":"key-10.1145\/3178876.3186111-8","DOI":"10.1016\/S1389-1286(00)00083-9"},{"doi-asserted-by":"crossref","unstructured":"Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph Mining: Laws, Generators, and Algorithms. Comput. Surveys Vol. 38, 1 (2006). https:\/\/doi.org\/10.1145\/1132952.1132954","key":"key-10.1145\/3178876.3186111-9","DOI":"10.1145\/1132952.1132954"},{"doi-asserted-by":"crossref","unstructured":"F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlos. 2016. On Sampling Nodes in a Network. In Conference on the World Wide Web (WWW).","key":"key-10.1145\/3178876.3186111-10","DOI":"10.1145\/2872427.2883045"},{"doi-asserted-by":"crossref","unstructured":"A. Clauset and C. Moore. 2005. Accuracy and scaling phenomena in internet mapping. Phys. Rev. Lett. Vol. 94 (2005), 018701.","key":"key-10.1145\/3178876.3186111-11","DOI":"10.1103\/PhysRevLett.94.018701"},{"doi-asserted-by":"crossref","unstructured":"A. Clauset, C. R. Shalizi, and M. E. J. Newman. 2009. Power-Law Distributions in Empirical Data. SIAM Rev. Vol. 51, 4 (2009), 661--703. https:\/\/doi.org\/10.1137\/070710111","key":"key-10.1145\/3178876.3186111-12","DOI":"10.1137\/070710111"},{"doi-asserted-by":"crossref","unstructured":"R. Cohen, K. Erez, D. ben Avraham, and S. Havlin. 2000. Resilience of the Internet to Random Breakdowns. Phys. Rev. Lett. Vol. 85, 4626--8 (2000).","key":"key-10.1145\/3178876.3186111-13","DOI":"10.1103\/PhysRevLett.85.4626"},{"doi-asserted-by":"crossref","unstructured":"A. Dasgupta, R. Kumar, and T. Sarlos. 2014. On estimating the average degree. In Conference on the World Wide Web (WWW). 795--806.","key":"key-10.1145\/3178876.3186111-14","DOI":"10.1145\/2566486.2568019"},{"unstructured":"D. Dubhashi and A. Panconesi. 2012. Concentration of Measure for the Analysis of Randomised Algorithms. Cambridge University Press.","key":"key-10.1145\/3178876.3186111-15"},{"doi-asserted-by":"crossref","unstructured":"N. Durak, T.G. Kolda, A. Pinar, and C. Seshadhri. 2013. A scalable null model for directed graphs matching all degree distributions: In, out, and reciprocal. In Network Science Workshop (NSW), 2013 IEEE 2nd. 23--30. https:\/\/doi.org\/10.1109\/NSW.2013.6609190","key":"key-10.1145\/3178876.3186111-16","DOI":"10.1109\/NSW.2013.6609190"},{"unstructured":"Peter Ebbes, Zan Huang, Arvind Rangaswamy, Hari P Thadakamalla, and ORGB Unit. 2008. Sampling large-scale social networks: Insights from simulated networks 18th Annual Workshop on Information Technologies and Systems, Paris, France.","key":"key-10.1145\/3178876.3186111-17"},{"unstructured":"Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. 2017 a. Provable and practical approximations for the degree distribution using sublinear graph samples. CoRR Vol. abs\/1710.08607 (2017). [arxiv]1710.08607 http:\/\/arxiv.org\/abs\/1710.08607","key":"key-10.1145\/3178876.3186111-18"},{"unstructured":"T. Eden, A. Levi, D. Ron, and C. Seshadhri. 2015. Approximately Counting Triangles in Sublinear Time Foundations of Computer Science (FOCS), GRS11 (Ed.). 614--633.","key":"key-10.1145\/3178876.3186111-19"},{"unstructured":"T. Eden, D. Ron, and C. Seshadhri. 2017 b. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In International Colloquium on Automata, Languages, and Programming (ICALP), GRS11 (Ed.). 614--633.","key":"key-10.1145\/3178876.3186111-20"},{"doi-asserted-by":"crossref","unstructured":"M. Faloutsos, P. Faloutsos, and C. Faloutsos. 1999. On power-law relationships of the internet topology SIGCOMM. 251--262.","key":"key-10.1145\/3178876.3186111-21","DOI":"10.1145\/316194.316229"},{"doi-asserted-by":"crossref","unstructured":"U. Feige. 2006. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. Vol. 35, 4 (2006), 964--984.","key":"key-10.1145\/3178876.3186111-22","DOI":"10.1137\/S0097539704447304"},{"doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. 2002. Property Testing in Bounded Degree Graphs. Algorithmica (2002), 302--343.","key":"key-10.1145\/3178876.3186111-23","DOI":"10.1007\/s00453-001-0078-7"},{"doi-asserted-by":"crossref","unstructured":"O. Goldreich and D. Ron. 2008. Approximating average parameters of graphs. Random Structures and Algorithms Vol. 32, 4 (2008), 473--493.","key":"key-10.1145\/3178876.3186111-24","DOI":"10.1002\/rsa.20203"},{"doi-asserted-by":"crossref","unstructured":"M. Gonen, D. Ron, and Y. Shavitt. 2011. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Math Vol. 25, 3 (2011), 1365--1411.","key":"key-10.1145\/3178876.3186111-25","DOI":"10.1137\/100783066"},{"doi-asserted-by":"crossref","unstructured":"Mira Gonen, Dana Ron, Udi Weinsberg, and Avishai Wool. 2008. Finding a dense-core in Jellyfish graphs. Computer Networks Vol. 52, 15 (2008), 2831--2841. https:\/\/doi.org\/10.1016\/j.comnet.2008.06.005","key":"key-10.1145\/3178876.3186111-26","DOI":"10.1016\/j.comnet.2008.06.005"},{"doi-asserted-by":"crossref","unstructured":"J. E. Hirsch. 2005. An index to quantify an individual's scientific research output. Proceedings of the National Academy of Sciences Vol. 102, 46 (2005), 16569--16572.","key":"key-10.1145\/3178876.3186111-27","DOI":"10.1073\/pnas.0507655102"},{"doi-asserted-by":"crossref","unstructured":"A. Lakhina, J. Byers, M. Crovella, and P. Xie.. 2003. Sampling biases in IP topology measurements. In Proceedings of INFOCOMM, Vol. Vol. 1. 332--341.","key":"key-10.1145\/3178876.3186111-28","DOI":"10.1109\/INFCOM.2003.1208685"},{"doi-asserted-by":"crossref","unstructured":"Sang Hoon Lee, Pan-Jun Kim, and Hawoong Jeong. 2006. Statistical properties of sampled networks. Physical Review E Vol. 73, 1 (2006), 016102.","key":"key-10.1145\/3178876.3186111-29","DOI":"10.1103\/PhysRevE.73.016102"},{"unstructured":"Jure Leskovec. 2015. SNAP Stanford Network Analysis Project. http:\/\/snap.standord.edu. (2015).","key":"key-10.1145\/3178876.3186111-30"},{"unstructured":"Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In Knowledge Data and Discovery (KDD). ACM, 631--636.","key":"key-10.1145\/3178876.3186111-31"},{"doi-asserted-by":"crossref","unstructured":"A. S. Maiya and T. Y. Berger-Wolf. 2011. Benefits of Bias: Towards Better Characterization of Network Sampling, In Knowledge Data and Discovery (KDD). ArXiv e-prints, 105--113. [arxiv]1109.3911","key":"key-10.1145\/3178876.3186111-32","DOI":"10.1145\/2020408.2020431"},{"doi-asserted-by":"crossref","unstructured":"Andrew McGregor. 2014. Graph stream algorithms: A survey. SIGMOD Vol. 43, 1 (2014), 9--20.","key":"key-10.1145\/3178876.3186111-33","DOI":"10.1145\/2627692.2627694"},{"doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher. 2003. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics Vol. 1, 2 (2003), 226--251.","key":"key-10.1145\/3178876.3186111-34","DOI":"10.1080\/15427951.2004.10129088"},{"doi-asserted-by":"crossref","unstructured":"M. E. J. Newman. 2003. The Structure and Function of Complex Networks. SIAM Rev. Vol. 45, 2 (2003), 167--256. https:\/\/doi.org\/10.1137\/S003614450342480","key":"key-10.1145\/3178876.3186111-35","DOI":"10.1137\/S003614450342480"},{"doi-asserted-by":"crossref","unstructured":"M. E. J. Newman, S. Strogatz, and D. Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Physical Review E Vol. 64 (2001), 026118.","key":"key-10.1145\/3178876.3186111-36","DOI":"10.1103\/PhysRevE.64.026118"},{"doi-asserted-by":"crossref","unstructured":"D. Pennock, G. Flake, S. Lawrence, E. Glover, and C. L. Giles. 2002. Winners don't take all: Characterizing the competition for links on the web. Proceedings of the National Academy of Sciences Vol. 99, 8 (2002), 5207--5211. https:\/\/doi.org\/10.1073\/pnas.032085699","key":"key-10.1145\/3178876.3186111-37","DOI":"10.1073\/pnas.032085699"},{"doi-asserted-by":"crossref","unstructured":"T. Petermann and P. Rios. 2004. Exploration of scale-free networks. European Physical Journal B Vol. 38 (2004), 201--204.","key":"key-10.1145\/3178876.3186111-38","DOI":"10.1140\/epjb\/e2004-00021-5"},{"unstructured":"Ali Pinar, Sucheta Soundarajan, Tina Eliassi-Rad, and Brian Gallagher. 2015. MaxOutProbe: An Algorithm for Increasing the Size of Partially Observed Networks. Technical Report. Sandia National Laboratories (SNL-CA), Livermore, CA (United States).","key":"key-10.1145\/3178876.3186111-39"},{"unstructured":"Bruno Ribeiro and Don Towsley. 2012. On the estimation accuracy of degree distributions from graph sampling Annual Conference on Decision and Control (CDC). IEEE, 5240--5247.","key":"key-10.1145\/3178876.3186111-40"},{"doi-asserted-by":"crossref","unstructured":"Dana Ron. 2010. Algorithmic and Analysis Techniques in Property Testing. Foundations and Trends in Theoretical Computer Science Vol. 5, 2 (2010), 73--205.","key":"key-10.1145\/3178876.3186111-41","DOI":"10.1561\/0400000029"},{"doi-asserted-by":"crossref","unstructured":"Dana Ron and Gilad Tsur. 2016. The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling. ACM Transactions on Computation Theory Vol. 8, 4 (2016), 15:1--15:19.","key":"key-10.1145\/3178876.3186111-42","DOI":"10.1145\/2930657"},{"doi-asserted-by":"crossref","unstructured":"C. Seshadhri, Tamara G. Kolda, and Ali Pinar. 2012. Community structure and scale-free collections of Erdös-Rényi graphs. Physical Review E Vol. 85, 5 (May. 2012), 056109. https:\/\/doi.org\/10.1103\/PhysRevE.85.056109","key":"key-10.1145\/3178876.3186111-43","DOI":"10.1103\/PhysRevE.85.056109"},{"unstructured":"Olivia Simpson, C Seshadhri, and Andrew McGregor. 2015. Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution. In International Conference on Data Mining (ICDM). IEEE, 979--984.","key":"key-10.1145\/3178876.3186111-44"},{"doi-asserted-by":"crossref","unstructured":"Michael PH Stumpf and Carsten Wiuf. 2005. Sampling properties of random graphs: the degree distribution. Physical Review E Vol. 72, 3 (2005), 036118.","key":"key-10.1145\/3178876.3186111-45","DOI":"10.1103\/PhysRevE.72.036118"},{"doi-asserted-by":"crossref","unstructured":"Yaonan Zhang, Eric D Kolaczyk, and Bruce D Spencer. 2015. Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks. The Annals of Applied Statistics Vol. 9, 1 (2015), 166--199.","key":"key-10.1145\/3178876.3186111-46","DOI":"10.1214\/14-AOAS800"}],"event":{"number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"acronym":"WWW '18","name":"the 2018 World Wide Web Conference","start":{"date-parts":[[2018,4,23]]},"location":"Lyon, France","end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186111","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186111&ftid=1957518&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186111"}},"subtitle":[],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":46,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186111","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}