Sublinear time estimation of degree distribution moments: the arboricity connection

DOI10.1137/17M1159014MaRDI QIDQ4972298zbMATH OpenFDO

Authors Talya Eden, Dana Ron, C. Seshadhri

Publication date 25 November 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.03661

zbMATH Keywords

approximation algorithmsarboricitydegeneracydegree distributiondegree momentssublinear time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph $G=(V,E)$ with $n$ vertices, and define (for $s>0$) $m{u}_s=frac1ncdotsu{m}_{vinV}{d}_v^s$. Our aim is to estimate $m{u}_s$ within a multiplicative error of $(1+epsilon)$ (for a given approximation parameter $epsilon>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), $widetildeO(sqrtn)$ queries suffice for any constant $epsilon$ (Feige, SICOMP 06 and Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) extended this result to all integral $s>0$, by designing an algorithms that performs $widetildeO(n^{1-1/(s+1)})$ queries. We design a new, significantly simpler algorithm for this problem. In the worst-case, it exactly matches the bounds of Gonen-Ron-Shavitt, and has a much simpler proof. More importantly, the running time of this algorithm is connected to the degeneracy of $G$. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with degeneracy at most $alpha$, it has a query complexity of $widetildeOleft(frac{n}^{1-1/s}m{u}_s^{1/s}Big(alph{a}^{1/s}+minalpha,m{u}_s^{1/s}Big)ight)=widetildeO(n^{1-1/s}alpha/m{u}_s^{1/s})$. Thus, for the class of bounded degeneracy graphs (which includes all minor closed families and preferential attachment graphs), we can estimate the average degree in $widetildeO(1)$ queries, and can estimate the variance of the degree distribution in $widetildeO(sqrtn)$ queries. This is a major improvement over the previous worst-case bounds. Our key insight is in designing an estimator for $m{u}_s$ that has low variance when $G$ does not have large dense subgraphs.

Recommendations

• scientific article; zbMATH DE number 7204459
• Counting stars and other small subgraphs in sublinear time
• Counting stars and other small subgraphs in sublinear-time
• Approximately counting triangles in sublinear time
• Approximating Average Parameters of Graphs

Cites work

• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Algorithmic complexity of power law networks
• An improved constant-time approximation algorithm for maximum~matchings
• Approximately counting triangles in sublinear time
• Approximating average parameters of graphs
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Arboricity and Subgraph Listing Algorithms
• Counting stars and other small subgraphs in sublinear-time
• Decomposition of Finite Graphs Into Forests
• Edge-Disjoint Spanning Trees of Finite Graphs
• Emergence of Scaling in Random Networks
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Graph theory
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• Local Graph Partitions for Approximation and Testing
• Lower bounds for approximating graph parameters via communication complexity
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• plfit
• Power-law distributions in empirical data
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Smallest-last ordering and clustering and graph coloring algorithms
• Structural sparsity
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• The method of moments and degree distributions for network models
• The space complexity of approximating the frequency moments
• Why do simple algorithms for triangle enumeration work in the real world?
• Winners don't take all: Characterizing the competition for links on the web

Cited in

(9)

• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
• Sublinear time estimation of degree distribution moments: the arboricity connection
• The arboricity captures the complexity of sampling edges
• scientific article; zbMATH DE number 7204459 (Why is no real title available?)
• Efficient estimation algorithms for neighborhood variance and other moments
• Testing C_k-freeness in bounded-arboricity graphs
• Improved sublinear-time moment estimation using weighted sampling
• Testing triangle freeness in the general model in graphs with arboricity \(O(\sqrt{n})\)
• Tolerant testers for subgraph-freeness

Describes a project that uses

Uses Software

• plfit

This page was built for publication: Sublinear time estimation of degree distribution moments: the arboricity connection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972298)