{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:13Z","timestamp":1787323513551,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph $G=(V,E)$ with $n$ (nonisolated) vertices, and define (for $s &gt; 0$) $M_s= \\sum_{v \\in V} d^s_v$. Our aim is to estimate $M_s$ within a multiplicative error of $(1+\\varepsilon)$ (for a given approximation parameter $\\varepsilon&gt;0$) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of $s=1$ (the average degree), $O^*(\\sqrt{n})$ queries suffice for any constant $\\varepsilon$ [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the $O^*$ notation to suppress dependencies in $\\log n$ and $1\/\\varepsilon$.) Gonen, Ron, and Shavitt [ SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral $s &gt; 0$ by designing an algorithm that performs $O^*(n^{1-1\/(s+1)})$ queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of $G$. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most $\\alpha$, it has a query complexity of $O^*\\big(\\frac{n \\cdot \\alpha^{1\/s}}{M_s^{1\/s}} + \\min\\big\\{\\frac{m}{M_s^{1\/s}},\\frac{m \\cdot n^{s-1}}{M_s}\\big\\}\\big)$ which is always upper bounded by $O^*\\big(\\frac{n\\alpha}{M_s^{1\/s}}\\big)$. Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in $O^*(1)$ queries, and we can estimate the variance of the degree distribution in $O^*(\\sqrt{n})$ queries. This is a major improvement over the previous worst-case bounds.<\/jats:p>","DOI":"10.1137\/17m1159014","type":"journal-article","created":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T11:11:51Z","timestamp":1574334711000},"page":"2267-2285","source":"Crossref","is-referenced-by-count":3,"title":["Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection"],"prefix":"10.1137","volume":"33","author":[{"given":"Talya","family":"Eden","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,11,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0287-3"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"N. Alon and S. Gutner,\n                      Linear time algorithms for finding a dominating set of fixed size in degenerated graphs\n                      , in Proceedings of the Annual International Conference Computing and Combinatorics (COCOON), 2008, pp. 394-405.","DOI":"10.1007\/978-3-540-73545-8_39"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2015.1037030"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Z. Bi, C. Faloutsos, and F. Korn,\n                      The \u201cDGX\u201d distribution for mining massive, skewed data\n                      , in Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), ACM, 2001, pp. 17-26.","DOI":"10.1145\/502512.502521"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS904"},{"key":"atypb8","first-page":"1306","author":"Brach P.","year":"2016","journal-title":"SIAM"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarl\u00f3s,\n                      On sampling nodes in a network\n                      , in Proceedings of the 25th International Conference on World Wide Web (WWW), 2016, pp. 471-481.","DOI":"10.1145\/2872427.2883045"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435297"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/060672121"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"A. Dasgupta, R. Kumar, and T. Sarlos,\n                      On estimating the average degree\n                      , in Proceedings of the 23rd International Conference on World Wide Web (WWW), 2014, pp. 795-806.","DOI":"10.1145\/2566486.2568019"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Springer, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"atypb18","first-page":"614","author":"Eden T.","year":"2015","journal-title":"IEEE"},{"key":"atypb19","unstructured":"T. Eden, D. Ron, and C. Seshadhri,\n                      Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection\n                      , preprint,https:\/\/arxiv.org\/abs\/1604.03661v1, 2016."},{"key":"atypb20","unstructured":"T. Eden and W. Rosenbaum,\n                      Lower Bounds for Approximating Graph Parameters via Communication Complexity\n                      , preprint,https:\/\/arxiv.org\/abs\/1709.04262, 2017."},{"key":"atypb21","first-page":"403","author":"Eppstein D.","year":"2010","journal-title":"Springer"},{"key":"atypb22","first-page":"251","author":"Faloutsos M.","year":"1999","journal-title":"ACM"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447304"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20203"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/100783066"},{"key":"atypb26","first-page":"22","author":"Hassidim A.","year":"2009","journal-title":"IEEE"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497298"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"atypb29","first-page":"445","volume":"1","author":"St C.","year":"1961","journal-title":"J. London Math. Soc."},{"key":"atypb30","first-page":"12","volume":"1","author":"St C.","year":"1964","journal-title":"J. London Math. Soc."},{"key":"atypb31","unstructured":"J. Ne\u0161etril and P. O. de Mendez,\n                      Sparsity\n                      , Springer, 2010."},{"key":"atypb32","first-page":"327","author":"Nguyen H. N.","year":"2008","journal-title":"IEEE"},{"key":"atypb33","first-page":"1123","author":"Onak K.","year":"2012","journal-title":"SIAM"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032085699"},{"key":"atypb36","first-page":"861","author":"Sala A.","year":"2010","journal-title":"ACM"},{"key":"atypb37","first-page":"979","author":"Simpson O.","year":"2015","journal-title":"IEEE"},{"key":"atypb38","unstructured":"Wikipedia contributors,\n                      Arboricity\n                      , Wikipedia,https:\/\/en.wikipedia.org\/w\/index.php?title=Arboricity&oldid=802150732, 2017 [accessed 26 Nov. 2018]."},{"key":"atypb39","unstructured":"Wikipedia contributors,\n                      Degeneracy (graph theory)\n                      , Wikipedia,https:\/\/en.wikipedia.org\/w\/index.php?title=Degeneracy_(graph_theory)&oldid=860270084, 2018 [accessed 26 Nov. 2018]."},{"key":"atypb40","first-page":"225","author":"Yoshida Y.","year":"2009","journal-title":"ACM"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1159014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:06:46Z","timestamp":1787321206000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1159014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1159014"],"URL":"https:\/\/doi.org\/10.1137\/17m1159014","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}