Open Problems:98 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Estimating a Graph's Degree Distribution to Open Problems:98 without leaving a redirect

2019-08-26T18:25:06Z

Krzysztof Onak moved page Waiting:Estimating a Graph's Degree Distribution to Open Problems:98 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-26T18:24:50Z

Updating the header

Krzysztof Onak at 02:05, 25 August 2019

2019-08-25T02:05:38Z

Ccanonne at 21:35, 7 August 2019

2019-08-07T21:35:39Z

Ccanonne at 21:30, 7 August 2019

2019-08-07T21:30:53Z

Ccanonne: Created page with "{{Header |title=Estimating a Graph's Degree Distribution |source=wola19 |who=C. Seshadhri }} The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree fr..."

2019-08-07T21:18:01Z

Created page with "{{Header |title=Estimating a Graph's Degree Distribution |source=wola19 |who=C. Seshadhri }} The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree fr..."

New page

{{Header
|title=Estimating a Graph's Degree Distribution
|source=wola19
|who=C. Seshadhri
}}
The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree frequencies: i.e., letting $n(d)$ denote the number of degree-$d$ vertices, the histogram $(n(d))_{d\geq 0}$. Define the (complementary) cumulative distribution function as
\[
N(d) \eqdef \sum_{d'\geq d} n(d'), \qquad d\geq 0\,.
\]
Assume one has access to the graph $G$ via the following (standard) three types of queries:
- sampling a u.a.r. vertex
- querying the degree of a given vertex
- sample a u.a.r. neighbor of a given vertex
and the goal is to obtain the following $(1\pm \varepsilon)$-"bicriteria" approximation $\hat{N}$ of the degree distribution: for all $d$,
\[
(1-\varepsilon)N( (1-\varepsilon)d) \leq \hat{N}(d) \leq (1+\varepsilon) N((1+\varepsilon)d)\,.
\]
Previous work of Eden, Jain, Pinar, Ron, and Seshadhri {{Cite|EdenJPRS-18}} shows an upper bound of
\[
\frac{n}{h} + \frac{m}{\min_d d\cdot N(d)}
\]
queries, where $h$ is the value s.t. $N(h)=h$ (where the complementary cdf intersects the diagonal).

'''Question:''' Can this upper bound be improved? Can one establish matching lower bounds?

And also, slightly less well-defined:

'''Question:''' Can one obtain better upper bounds when relaxing the goal to only learn the ''high-degree'' (tail) part of the distribution? What about testing properties of the degree distribution (e.g., "power-law-ness") in this setting? And what about the first type of queries — can one relax it, or work with a different type of sampling than uniform (for instance, via random walks)?

← Older revision	Revision as of 18:25, 26 August 2019
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=wola19
 |who=C. Seshadhri

@@ Line 10: / Line 10: @@
 Assume one has access to the graph $G$ via the following (standard) three types of queries:
-- sampling a u.a.r. vertex
+* sampling a vertex uniformly at random
-- querying the degree of a given vertex
+* querying the degree of a given vertex
-- sample a u.a.r. neighbor of a given vertex
+* sample a neighbor of a given vertex uniformly at random
-and the goal is to obtain the following $(1\pm \varepsilon)$-"bicriteria" approximation $\hat{N}$ of the degree distribution: for all $d$,
+and the goal is to obtain the following $(1\pm \varepsilon)$-&ldquo;bicriteria&rdquo; approximation $\hat{N}$ of the degree distribution: for all $d$,
 \[
      (1-\varepsilon)N( (1-\varepsilon)d) \leq \hat{N}(d) \leq (1+\varepsilon) N((1+\varepsilon)d)\,.
@@ Line 30: / Line 30: @@
 And also, slightly less well-defined:
-'''Question:''' Can one obtain better upper bounds when relaxing the goal to only learn the ''high-degree'' (tail) part of the distribution? What about testing properties of the degree distribution (e.g., "power-law-ness") in this setting? And what about the first type of queries — can one relax it, or work with a different type of sampling than uniform (for instance, via random walks)?
+'''Question:''' Can one obtain better upper bounds when relaxing the goal to only learn the ''high-degree'' (tail) part of the distribution? What about testing properties of the degree distribution (e.g., &ldquo;power-law-ness&rdquo;) in this setting? And what about the first type of queries — can one relax it, or work with a different type of sampling than uniform (for instance, via random walks)?

@@ Line 6: / Line 6: @@
 The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree frequencies: i.e., letting $n(d)$ denote the number of degree-$d$ vertices, the histogram $(n(d))_{d\geq 0}$. Define the (complementary) cumulative distribution function as
 \[
-     N(d) \eqdef \sum_{d'\geq d} n(d'), \qquad d\geq 0\,.
+     N(d) \stackrel{\rm def}{=} \sum_{d'\geq d} n(d'), \qquad d\geq 0\,.
 \]
 Assume one has access to the graph $G$ via the following (standard) three types of queries: