Provable and practical approximations for the degree
distribution using sublinear graph samples∗
Talya Eden

School of Computer Science, Tel Aviv
University
Tel Aviv, Israel
talyaa01@gmail.com

Shweta Jain

University of California, Santa Cruz
Santa Cruz, CA, USA
sjain12@ucsc.edu

arXiv:1710.08607v2 [cs.SI] 19 Jan 2018

Dana Ron

School of Computer Science, Tel Aviv
University
Tel Aviv, Israel
danaron@tau.ac.il

Ali Pinar

Sandia National Laboratories
Livermore, CA
apinar@sandia.gov

C. Seshadhri

University of California, Santa Cruz
Santa Cruz, CA
sesh@ucsc.edu

ABSTRACT

1

The degree distribution is one of the most fundamental properties
used in the analysis of massive graphs. There is a large literature on
graph sampling, where the goal is to estimate properties (especially
the degree distribution) of a large graph through a small, random
sample. The degree distribution estimation poses a significant
challenge, due to its heavy-tailed nature and the large variance
in degrees.
We design a new algorithm, SADDLES, for this problem,
using recent mathematical techniques from the field of sublinear
algorithms. The SADDLES algorithm gives provably accurate
outputs for all values of the degree distribution. For the analysis,
we define two fatness measures of the degree distribution, called
the h-index and the z-index. We prove that SADDLES is sublinear
in the graph size when these indices are large. A corollary of this
result is a provably sublinear algorithm for any degree distribution
bounded below by a power law.
We deploy our new algorithm on a variety of real datasets and
demonstrate its excellent empirical behavior. In all instances, we
get extremely accurate approximations for all values in the degree
distribution by observing at most 1% of the vertices. This is a major
improvement over the state-of-the-art sampling algorithms, which
typically sample more than 10% of the vertices to give comparable
results. We also observe that the h and z-indices of real graphs are
large, validating our theoretical analysis.

In domains as diverse as social sciences, biology, physics,
cybersecurity, graphs are used to represent entities and the
relationships between them. This has led to the explosive growth
of network science as a discipline over the past decade. One of
the hallmarks of network science is the occurrence of specific
graph properties that are common to varying domains, such as
heavy tailed degree distributions, large clustering coefficients,
and small-world behavior. Arguably, the most significant among
these properties is the degree distribution, whose study led to the
foundation of network science [7, 8, 20].
Given an undirected graph G, the degree distribution (or
technically, histogram) is the sequence of numbers n(1), n(2), . . .,
where n(d) is the number of vertices of degree d. In almost all
real-world scenarios, the average degree is small, but the variance
(and higher moments) is large. Even for relatively large d, n(d)
is still non-zero, and n(d) typically has a smooth non-increasing
behavior. In Fig. 1, we see the typical degree distribution behavior.
The average degree in a Google web network is less than 10, but
the maximum degree is more than 5000. There are also numerous
vertices with all intermediate degrees. This is referred to as a “heavy
tailed” distribution. The degree distribution, especially the tail, is
of significant relevance to modeling networks, determining their
resilience, spread of information, and for algorithmics [6, 9, 13, 16,
33–36, 42].
With full access to G, the degree distribution can be computed
in linear time, by simply determining the degree of each vertex.
Yet in many scenarios, we only have partial access to the graph,
provided through some graph samples. A naive extrapolation of
the degree distribution can result in biased results. The seminal
research paper of Faloutsos et al. claimed a power law in the degree
distribution on the Internet [20]. This degree distribution was
deduced by measuring a power law distribution in the graph sample
generated by a collection of traceroute queries on a set of routers.
Unfortunately, it was mathematically and empirically proven that
traceroute responses can have a power law even if the true network
does not [1, 11, 27, 37]. In general, a direct extrapolation of the
degree distribution from a graph subsample is not valid for the

ACM Reference format:
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. 2016.
Provable and practical approximations for the degree distribution using
sublinear graph samples. In Proceedings of , , , 12 pages.
DOI:
∗ Both

Talya Eden and Shweta Jain contributed equally to this work, and are joint first
authors of this work.
Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
,
© 2016 Copyright held by the owner/author(s). .
DOI:

INTRODUCTION

The Hidden Degrees Model (HDM) Vertex and neighbor
queries allowed, not degree queries: This is a substantially weaker
model. In numerous cybersecurity and network monitoring
settings, an algorithm cannot query for degrees, and has to infer
them indirectly. Observe that this model is significantly harder
than the standard model. It takes O((m + n) log n) to determine
all the degrees, since one has to at least visit all the edges to find
degrees exactly. In this model, we express the number of queries as
a fraction of m.
We stress that other query models are possible. Recent work of
Dasgupta, Kumar, and Sarlos argues that vertex queries are too
powerful, especially in social network contexts [14]. In their query
model, a small set of random seeds are provided, but only neighbor
and degree queries are subsequently allowed.

underlying graph. This leads to the primary question behind our
work.
How can we provably and practically estimate the degree
distribution without seeing the entire graph?
There is a rich literature in statistics, data mining, and physics
on estimating graph properties (especially the degree distribution)
using a small subsample [2, 3, 5, 17, 28, 30, 31, 39, 46, 47].
Nonetheless, there is no provable algorithm for the entire degree
distribution, with a formal analysis on when it is sublinear in the
number of vertices. Furthermore, most empirical studies typically
sample 10-30% of the vertices for reasonable estimates.

1.1

Problem description

We focus on the complementary cumulative degree histogram (often
called the cumulative degree distribution) or ccdh of G. This is
Í
the sequence {N (d)}, where N (d) = r ≥d n(r ). The ccdh is
typically used for fitting distributions, since it averages out noise
and is monotonic [12]. Our aim is to get an accurate bicriteria
approximation to the ccdh of G, at all values of d.

1.2

Our contributions

Our main theoretical result is a new sampling algorithm, the
Sublinear Approximations for Degree Distributions Leveraging
Edge Samples, or SADDLES. This algorithm provably provides
(ε, δ )-approximations for the ccdh. We show how to design
SADDLES under both the Standard Model and the Hidden Degrees
Model. We apply SADDLES on a variety of real datasets and
demonstrate its ability to accurately approximate the ccdh with a
tiny sample of the graph.
• Sampling algorithm for estimating ccdh: Our algorithm
combines a number of techniques in random sampling to get
(ε, δ )-estimates for the ccdh. A crucial component is an application
of an edge simulation technique, first devised by Eden et al. in the
context of triangle counting [18, 19]. This (theoretical) technique
shows how to get a collection of weakly correlated uniform random
edges from independent uniform vertices. SADDLES employs a
weighting scheme on top of this method to estimate the ccdh.
• Heavy tails leads to sublinear algorithms: The challenge
in analyzing SADDLES is in finding parameters of the ccdh that
allow for sublinear query complexity. To that end, we discuss two
parameters that measure “heaviness” of the distribution tail: the
classic h-index and a newly defined z-index. We prove that the
running time of SADDLES is sublinear (for both models) whenever
these indices are large. This yields a provably sublinear time
algorithm to get accurate (ε, δ )-estimates for the ccdh.
• Excellent empirical behavior:
We deploy an
implementation of SADDLES on a collection of large real-world
graphs. In all instances, we achieve extremely accurate estimates
for the entire ccdh by sampling at most 1% of the vertices of the
graph. Refer to Fig. 1. Observe how SADDLES tracks various
jumps in the ccdh, for both graphs in Fig. 1.
• Comparison with existing sampling methods: A number
of graph sampling methods have been proposed in practice, such as
vertex sampling, snowball sampling, forest-fire sampling, induced
graph sampling, random walk, edge sampling [5, 17, 28, 30, 38,
39, 47]. A recent work of Zhang et al. explicitly addresses biases
in these sampling methods, and fixes them using optimization
techniques [47]. We run head-to-head comparisons with all
these sampling methods, and demonstrate the SADDLES gives
significantly better practical performance. Fig. 1 shows the output
of all these sampling methods with a total sample size of 1% of

e(d)} is an (ε, δ )-estimate of the
Definition 1.1. The sequence {N
e(d) ≤ (1 + δ )N ((1 − ε)d).
ccdh if ∀d, (1 − δ )N ((1 + ε)d) ≤ N
Computing an (ε, δ )-estimate is significantly harder than
approximating the ccdh using standard distribution measures.
Statistical measures, such as the KS-distance, χ 2 , `p -norms, etc.
tend to ignore the tail, since (in terms of probability mass) it is
a negligible portion of the distribution. From a network science
standpoint, the few vertices that are of extremely high degree are
essential for graph analysis. An (ε, δ )-estimate is accurate for all d.
The query model: A formal approach requires specifying a
query model for accessing G. We look to the subfields of property
testing and sublinear algorithms within theoretical computer
science for such models [22, 23]. Consider the following three
kinds of queries.
• Vertex queries: acquire a uniform random vertex v ∈ V .
• Neighbor queries: given v ∈ V , acquire a uniform random
neighbor u of V .
• Degree queries: given v ∈ V , acquire the degree dv .
An algorithm is only allowed to make these queries to process the
input. It has to make some number of queries, and finally produce
an output. We discuss two query models, and give results for both.
The Standard Model (SM) All queries allowed: This is the
standard model in numerous sublinear algorithms results [18, 19, 22–
24]. Furthermore, most papers on graph sampling implicitly use this
model for generating subsamples. Indeed, any method involving
crawling from a random set of vertices and collecting degrees is
in the Standard Model. This model is the primary setting for our
work, and allows for comparison with rich body of graph sampling
algorithms. It is worth noting that in the Standard Model, one can
determine the entire degree distribution in O(n log n) queries (the
extra log n factor comes from the coupon collector bound of finding
all the vertices through uniform sampling). Thus, it makes sense to
express the number of queries made by an algorithm as a fraction
of n. Alternately, the number of queries is basically the number of
vertices encountered by the algorithm. Thus, a sublinear algorithm
makes o(n) queries.
2

(a) amazon0601 copurchase network

(b) web-Google web network

(c) cit-Patents citation network

(d) com-orkut social network

Figure 1: The output of SADDLES on a collection of networks: amazon0601 (403K vertices, 4.9M edges), web-Google (870K vertices,
4.3M edges), cit-Patents (3.8M vertices, 16M edges), com-orkut social network (3M vertices, 117M edges). SADDLES samples 1%
of the vertices and gives accurate results for the entire (cumulative) degree distribution. For comparison, we show the output
of a number of sampling algorithms from past work, each run with the same number of samples. (Because of the size of
com-Orkut, methods involving optimization [47] fail to produce an estimate in reasonable time.)
the vertices. Observe how across the board, the methods make
erroneous estimates for most of the degree distribution. The errors
are also very large, for all the methods. This is consistent with
previous work, where methods sample more than 10% of the number
of vertices.

1.3

Our main result is more nuanced, and holds for all degree
distributions. If the ccdh has a heavy tail, we expect N (d) to
be reasonably large even for large values of d. We describe two
formalisms of this notion, through fatness indices.
Definition 1.4. The h-index of the degree distribution is the
largest d such that there are at least d vertices of degree at least d.

Theoretical results in detail

This is the exact analogy of the bibliometric h-index [26]. As we
show in the §2.1, h can be approximated by mind (d + N (d))/2. A
more stringent index is obtained by replacing the arithmetic mean
by the (smaller) geometric mean.

Our main theoretical result is a new sampling algorithm, the
Sublinear Approximations for Degree Distributions Leveraging
Edge Samples, or SADDLES.
We first demonstrate our results for power law degree
distributions [7, 8, 20]. Statistical fitting procedures suggest they
occur to some extent in the real-world, albeit with much noise [12].
The classic power law degree distribution sets n(d) ∝ 1/d γ , where
γ is typically in [2, 3]. We build on this to define a power law lower
bound.

Definition p1.5. The z-index of the degree distribution is z =
mind :N (d )>0 d · N (d).
Our main theorem asserts that large h and z indices lead to a
sublinear algorithm for degree distribution estimation. Theorem 1.3
is a direct corollary obtained by plugging in values of the indices
for power laws.

Definition 1.2. Fix γ > 2. A degree distribution is bounded
below by a power law with exponent γ , if the ccdh satisfies the
following property. There exists a constant τ > 0 such that for all
d, N (d) ≥ bτn/d γ −1 c.

Theorem 1.6. For any ε > 0, the SADDLES algorithm outputs
(with high probability) an (ε, ε)-approximation to the ccdh, and makes
the following number of queries.
e
• SM: O(n/h
+ m/z 2 )
e
• HDM: O(m/z)

The following is a corollary of our main result. For convenience,
we will suppress query complexity dependencies on ε and log n
e
factors, using O(·).

1.4

Theorem 1.3. Suppose the degree distribution of G is bounded
below by a power law with exponent γ . Let the average degree be
denoted by d. For any ε > 0, the SADDLES algorithm outputs (with
high probability) an (ε, ε)-approximation to the ccdh and makes the
following number of queries.
1
1
e 1− γ + n1− γ −1 d)
• SM: O(n

Challenges

The heavy-tailed behavior of the real degree distribution poses
the primary challenge to computing (ε, δ )-estimates to the ccdh.
As d increases, there are fewer and fewer vertices of that degree.
Sampling uniform random vertices is inefficient when N (d) is small.
A natural idea to find high degree vertices to pick a random neighbor
of a random vertex. Such a sample is more likely to be a high degree
vertex. This is the idea behind methods like snowball sampling,
forest fire sampling, random walk sampling, graph sample-and-hold,
etc. [5, 17, 28, 30, 38, 39, 47]. But these lead to biased samples,
since vertices with the same degree may be picked with differing
probabilities.

1

e 1− 2(γ −1) d)
• HDM: O(n

In most real-world instances, the average degree d is typically
constant. Thus, the complexities above are strongly sublinear. For
e 1/2 ) for both models. When γ = 3,
example, when γ = 2, we get O(n
e 2/3 ) and O(n
e 3/4 ).
we get O(n
3

A direct extrapolation/scaling of the degrees in the observed
graph does not provide an accurate estimate. Our experiments show
that existing methods always miss the head or the tail. A more
principled approach was proposed recently by Zhang et al. [47],
by casting the estimation of the unseen portion of the distribution
as an optimization problem. From a mathematical standpoint, the
vast majority of existing results tend to analyze the KS-statistic, or
some `p -norm. As we mentioned earlier, this does not work well
for measuring the quality of the estimate at all scales. As shown by
our experiments, none of these methods give accurate estimate for
the entire ccdh with less than 5% of the vertices.
The main innovation in SADDLES comes through the use of
a recent theoretical technique to simulate edge samples through
vertex samples [18, 19]. The sampling of edges occurs through
two stages. In the first stage, the algorithm samples a set of r
vertices and sets up a distribution over the sampled vertices such
that any edge adjacent to a sampled vertex may be sampled with
uniform probability. In the second stage, it samples q edges from
this distribution. While a single edge is uniform random, the set of
edges are correlated.
For a given d, we define a weight function on the edges, such
that the total weight is exactly N (d). SADDLES estimates the total
weight by scaling up the average weight on a random sample of
edges, generated as discussed above. The difficulty in the analysis
is the correlation between the edges. Our main insight is that if the
degree distribution has a fat tail, this correlation can be contained
even for sublinear r and q. Formally, this is achieved by relating
the concentration behavior of the average weight of the sample to
the h and z-indices. The final algorithm combines this area with
vertex sampling to get accurate estimates for all d.
The hidden degrees model is dealt with using birthday paradox
techniques formalized by Ron and
√ Tsur [41]. It is possible to
estimate the degree dv using O( dv ) queries neighbor queries.
But this adds overhead to the algorithm, especially for estimating
the ccdh at the tail. As discussed earlier, we need methods that bias
towards higher degrees, but this significantly adds to the query cost
of actually estimating the degrees.

1.5

Zhang et al. observe that the degree distribution of numerous
sampling methods is a random linear projection of the true
distribution [47]. They attempt to invert this (ill-conditioned) linear
problem, to correct the biases. This leads to improvement in the
estimate, but the empirical studies typically sample more than 10%
of the vertices for good estimates.
A recent line of work by Soundarajan et al. on active probing
also has flavors of graph sampling [44, 45]. In this setting, we start
with a small, arbitrary subgraph and try to grow this subgraph
to achieve some coverage objective (like discover the maximum
new vertices, find new edges, etc.). The probing schemes devised
in these papers outperform uniform random sampling methods for
coverage objectives.
All these results aim to capture numerous properties of the graph,
using a single graph sample. Nonetheless, the degree distribution is
typically considered as the most important, and empirical analyses
always focus on estimating it accurately. Ribiero and Towsley [39]
and Stumpf and Wiuf [46] specifically study degree distributions.
Ribiero and Towsley [39] do detailed analysis on degree distribution
estimates (they also look at the ccdh) for a variety of these sampling
methods. Their empirical results show significant errors either at
the head or the tail. We note that almost all these results end up
sampling up to 20% of the graph to estimate the degree distribution.
Some methods try to match the shape/family of the distribution,
rather than estimate it as a whole [46]. Thus, statistical methods
can be used to estimate parameters of the distribution. But it is
reasonably well-established that real-world degree distributions
are rarely pure power laws in most instances [12]. Indeed, fitting
a power law is rather challenging and naive regression fits on
log-log plots are erroneous, as results of Clauset-Shalizi-Newman
showed [12].
The subfield of property testing and sublinear algorithms for sparse
graphs within theoretical computer science can be thought of as
a formalization of graph sampling to estimate properties. Indeed,
our description of the main problem follows this language. There
is a very rich body of mathematical work in this area (refer to
Ron’s survey [40]). Practical applications of graph property testing
are quite rare, and we are only aware of one previous work on
applications for finding dense cores in router networks [25]. The
specific problem of estimating the average degree (or the total
number of edges) was studied by Feige [21] and Goldreich-Ron [23].
Gonen et al. and Eden et al. focus on the problem of estimating
higher moments of the degree distribution [19, 24]. One of the main
techniques we use of simulating edge queries was developed in
sublinear algorithms results of Eden et al. [18, 19] in the context of
triangle counting and degree moment estimation. We stress that
all these results are purely theoretical, and their practicality is by
no means obvious.
On the practical side, Dasgupta, Kumar, and Sarlos study
average degree estimation in real graphs, and develop alternate
algorithms [14]. They require the graph to have low mixing time and
demonstrate that the algorithm has excellent behavior in practice
(compared to implementations of Feige’s and the Goldreich-Ron
algorithm [21, 23]). Dasgupta et al. note that sampling uniform
random vertices is not possible in many settings, and thus they
consider a significantly weaker setting than Model 1. Chierichetti

Related Work

There is a rich body of literature on generating a graph sample
that reveals graph properties of the larger “true” graph. We
do not attempt to fully survey this literature, and only refer to
results directly related to our work. The works of Leskovec &
Faloutsos [30], Maiya & Berger-Wolf [31], and Ahmed, Neville, &
Kompella [2, 5] provide excellent surveys of multiple sampling
methods.
There are a number of sampling methods based on random
crawls: forest-fire [30], snowball sampling [31], and expansion
sampling [30]. As has been detailed in previous work, these
methods tend to bias certain parts of the network, which can be
exploited for more accurate estimates of various properties [30, 31,
39]. A series of papers by Ahmed, Neville, and Kompella [2–5] have
proposed alternate sampling methods that combine random vertices
and edges to get better representative samples. Notably, this yields
one of the best streaming algorithms for triangle counting [4].
4

Proof. Let s = mind max(d, N (d)) and let the minimum be
attained at d ∗ . If there are multiple minima, let d ∗ be the largest
among them. We consider two cases. (Note that N (d) is a
monotonically non-increasing sequence.)
Case 1: N (d ∗ ) ≥ d ∗ . So s = N (d ∗ ). Since d ∗ is the largest
minimum, for any d > d ∗ , d > N (d ∗ ). (If not, then the minimum is
also attained at d > d ∗ .) Thus, d > N (d ∗ ) ≥ N (d). For any d < d ∗ ,
N (d) ≥ N (d ∗ ) ≥ d ∗ > d. We conclude that d ∗ is largest d such that
N (d) ≥ d. Thus, h = d ∗ .
If s , h, then d ∗ < N (d ∗ ). Then, N (d ∗ + 1) < N (d ∗ ), otherwise
the minimum would be attained at d ∗ + 1. Furthermore, max(d ∗ +
1, N (d ∗ + 1)) > N (d ∗ ), implying d ∗ + 1 > N (d ∗ ). This proves that
h + 1 > s.
Case 2: d ∗ > N (d ∗ ). So s = d ∗ . For d > d ∗ , N (d) ≤ N (d ∗ ) <
∗
d < d. For d < d ∗ , N (d) ≥ d ∗ > d (if N (d) < d ∗ , then d ∗ would not
be the minimizer). Thus, d ∗ − 1 is the largest d such that N (d) ≥ d,
and h = d ∗ − 1 = s − 1.


et al. focus on sampling uniform random vertices, using only a
small set of seed vertices and neighbor queries [10].
We note that there is a large body of work on sampling graphs
from a stream [32]. This is quite different from our setting, since
a streaming algorithm observes every edge at least once. The
specific problem of estimating the degree distribution at all scales
was considered by Simpson et al. [43]. They observe many of the
challenges we mentioned earlier: the difficulty of estimating the
tail accurately, finding vertices at all degree scales, and combining
estimates from the head and the tail.

2

PRELIMINARIES

We set some notation. The input graph G has n vertices and m
edges. For any vertex v, let Γ(v) be the neighborhood of v, and dv
be the degree. As mentioned earlier, n(d) is the number of vertices
Í
of degree d and N (d) = r ≥d n(r ) is the ccdh at d. We use “u.a.r.”
as a shorthand for “uniform at random”.
We stress that the all mention of probability and error is with
respect to the randomness of the sampling algorithm. There is no
stochastic assumption on the input graph G.
We use the shorthand A ∈ (1 ± α)B for A ∈ [(1 − α)B, (1 + α)B].
We will apply the following (rescaled) Chernoff bound.

The h-index does not measure d vs N (d) at different scales, and
a large h-index only ensures that there are ”enough” high-degree
vertices. For instance, the h-index does not distinguish between
N 1 and N 2 when N 1 (100) = 100 and N 1 (d) = 0 for d > 100 and
N 2 (100, 000) = 100 and N 2 (d) = 0 for all other values of d ≥ 100.
The h and z-indices are related to each other.
√
Claim 2.4. h ≤ z ≤ h.

Theorem 2.1. [Theorem 1 in [15]] Let X 1 , X 2 , . . . , X k be a
sequence of iid random variables with expectation µ. Furthermore,
X i ∈ [0, B].
Í
• For ε < 1, Pr[| ki=1 X i − µk | ≥ εµk] ≤ 2 exp(−ε 2 µk/3B).
Í
• For t ≥ 2eµ, Pr[ ki=1 X i ≥ tk] ≤ 2−t k/B .

Proof. Since Np(d) is integral, if N (d) > 0, then N (d) ≥ 1. Thus,
for all N (d) > 0, max(d, N (d)) ≤ d · N (d) ≤ max(d, N (d)). We
take the minimum over all d to complete the proof.


We will require the following “boosting through medians” lemma,
which is a routine application of the Chernoff bound.

To give some intuition about these indices, we compute the h and
z index for power laws. The classic power law degree distribution
sets n(d) ∝ 1/d γ , where γ is typically in [2, 3].

Theorem 2.2. Consider two quantities A < B. Suppose there exists
a randomized algorithm (that does not know A or B) of expected
running time T that outputs a value in [A, B] with probability at least
2/3. Then, for any 0 < δ < 1/3, there exists a randomized algorithm
with expected running time O(T log(1/δ )) that outputs a value in
(1 ± ε)A with probability at least 1 − δ .

Claim 2.5. If a degree distribution is bounded below by a power
1

Proof. Consider d ≤ τn 1/γ , where τ is defined according to
Definition 1.2. Then, N (d) ≥ bτn/(τ 1/γ n (γ −1)/γ )c = Ω(n 1/γ ). This
proves the h-index bound.

Proof. We simply run k = 200 log(1/δ ) independent
invocations of the algorithm and output the median output. Let X i
be the indicator random variable for the ith invocation outputting
a number in [A, B]. Observe that µ = E[X i ] ≥ 2/3. By
Í
Theorem 2.1, Pr[| ki=1 X i − µk | ≥ µk/5] ≤ 2 exp(−µk/75) ≤
2 exp(−(2/3)(200/75) log(1/δ )) ≤ δ . Thus, with probability at least
1 − δ , at least (4/5)(2/3)k > k/2 outputs lie in [A, B]. This implies
that the median also lies in [A, B].


1
Set d ∗ = (τn) γ −1 . For d ≤ d ∗ , N (d) ≥ 1 and d · N (d) ≥
1

(τ /2)n/d γ −2 = Ω(n γ −1 ). If there exists no d > d ∗ such that
1

2(γ −1) ). If there does exist some such d,
N (d) > 0, then
√ z = Ω(n
then z = Ω( d ∗ ) which yields the same value.

√
Plugging in values, for γ = 2, both h and z are Ω( n). For γ = 3,
h = Θ(n1/3 ) and z = Θ(n1/4 ).

It will be convenient to fix the approximation parameter ε > 0 at
the very outset. So we will not pass ε as a parameter to our various
subroutines.

2.1

1

law with exponent γ , then h = Ω(n γ ) and z = Ω(n 2(γ −1) ).

2.2

Simulating degree queries for HDM

The Hidden Degrees Model does not allow for querying the degree
dv of a vertex v. Nonetheless, it is possible to get accurate estimates
of dv by sampling u.a.r. neighbors (with replacement) of v. This
can be done by using the birthday paradox argument, as formalized
by Ron and Tsur [41]. Roughly speaking, one repeatedly samples
neighbors until the same vertex is seen twice. If this happens after t
samples, t 2 is a constant factor approximation for dv . This argument
√
can be refined to get accurate approximations for dv using O( dv )
random edge queries.

More on Fatness indices

The following characterization of the h-index will be useful for
analysis. Since (d + N (d))/2 ≤ max(d, N (d)) ≤ d + N (d), this
proves that mind (d + N (d))/2 is a 2-factor approximation to the
h-index.
Lemma 2.3. mind max(d, N (d)) ∈ {h, h + 1}
5

• HDM: O((m/z)(ε −3 log(n/εδ ))).

Theorem 2.6. [Theorem 3.1 of [41], restated] Fix any α > 0. There
is an algorithm that outputs a value
√ in (1 ± α)dv with probability
> 2/3, and makes an expected O( dv /α 2 ) u.a.r. neighbor samples.

Observe how a larger h and z-index lead to smaller running times.
Ignoring constant factors and assuming m = O(n), asymptotically
increasing h and z-indices lead to sublinear algorithms. Suppose
the degree distribution was a power law with exponent γ > 1.
The average degree is constant, so m = O(n). Using the index
calculations in §2.1, for SM, the running time is O(n 1−1/γ ). For
√
HDM, it is O(n1−1/2(γ −1) ). For γ = 2, the running times are O( n)
for both models. For γ = 3, the running times are O(n2/3 ) and
O(n3/4 ) respectively.
We now describe the algorithm itself. The main innovation in
SADDLES comes through the use of a recent theoretical technique
to simulate edge samples through vertex samples [18, 19]. The
sampling of edges occurs through two stages. In the first stage,
the algorithm samples a set of r vertices and sets up a distribution
over the sampled vertices such that any edge adjacent to a sampled
vertex may be sampled with uniform probability. In the second
stage, it samples q edges from this distribution.
For each edge, we compute a weight based on the degrees of its
vertices and generate our final ccdh estimate by averaging these
weights. Additionally, we use vertex sampling to estimate the head
of the distribution. Straightforward Chernoff bound arguments can
be used to determine when to use the vertex sampling over the
edge sampling method.
In the following description, we use c to denote a sufficiently
large constant. The same algorithmic structure is used for the
Standard Model and the Hidden Degrees Model. The only difference
is the use the algorithm of Corollary 2.7 to estimate degrees in
the HDM, while the degrees are directly available in the Standard
Model.
We abuse notation somewhat, and use SADDLES to denote the
core sampling procedure. As described, this works for a single
choice of d to estimate N (d). The final algorithm simply invokes
this procedure for various degrees.

For the sake of the theoretical analysis, we will simply assume
this theorem. In the actual implementation of SADDLES, we will
discuss the specific parameters used. It will be helpful to abstract
out the estimation of degrees through the following corollary. The
procedure DEG(v) will be repeatedly invoked by SADDLES. This is
a direct consequence of setting α − ε/10 and applying Theorem 2.2
with δ = 1/n3 .
Corollary 2.7. There is an algorithm DEG that takes as input a
vertex v, and has the following properties:
• For all v: with probability > 1 − 1/n 3 , the output DEG(v) is in
(1 ± ε/10)dv .
√
• The expected running time of DEG(v) is O(ε −2 dv log n).
We will assume that invocations to DEG with the same
arguments use the same sequence of random bits. Alternately,
imagine that a call to DEG(v, ε) stores the output, so subsequent
calls output the same value.
Definition 2.8. The output DEG(v) is denoted by dˆv . The random
bits used in all calls to DEG is collectively denoted Λ. (Thus, Λ
completely specifies all the values {dˆv }.) We say Λ is good if ∀v ∈ V ,
dˆv ∈ (1 ± ε/10)dv .
The following is a consequence of conditional probabilities.
Claim 2.9. Consider any event A, such that for any good Λ,
Pr[A|Λ] ≥ p. Then Pr[A] ≥ p − 1/n 2 .
Proof. The probability that Λ is not good is at most the
probability that for some v, DEG(v) < (1 ± ε/10). By the union
bound and Corollary 2.7, the probability is at most 1/n 2 .
Note that
Í
Pr[A] ≥ Λgood Pr[Λ] Pr[A|Λ] ≥ p Pr[Λ is good]. Since Λ is good
with probability at least 1−1/n2 , Pr[A] ≥ (1−1/n2 )p ≥ p−1/n 2 . 
cΛ (d) to be |{v |dˆv ≥ d}|. We will
For any fixed Λ, we set N
cΛ -values.
perform the analysis of SADDLES with respect to the N

4

cΛ (v) ∈ [N ((1 +
Claim 2.10. Suppose Λ is good. For all v, N
ε/9)d), N ((1 − ε/9)d)].

Claim 4.1. The following holds with probability > 9/10. If
e(d) ∈ (1 ±
SADDLES(d, r , q) outputs an estimate in Step 6, then N
cΛ (d). If it does not output in Step 6, then N
cΛ (d) < (2c/ε 2 )(n/r ).
ε/10)N

Proof. Since Λ is good, ∀u, dˆu ∈ (1 ± ε/10)du , Furthermore, if
du ≥ (1 + ε/9)d, then dˆu ≥ (1 − ε/10)(1 + ε/9)d ≥ d. Analogously,
if du ≤ (1 − ε/9)d, then dˆu ≤ (1 + ε/10)(1 − ε/9)d ≤ d. Thus,
{u|du ≥ d(1 + ε/9)} ⊆ {u|dˆu ≥ d} ⊆ {u|du ≥ d(1 − ε/9)}.


3

ANALYSIS OF SADDLES

The estimate of Step 6 can be analyzed with a direct Chernoff bound.

Proof. Each X i is an iid Bernoulli random variable, with success
cΛ (d)/n. We split into two cases.
probability precisely N
c
Case 1: N Λ (d) ≥ (c/10ε 2 )(n/r ). By the Chernoff bound of
Í
cΛ (d)/n| ≥ (ε/10)(r N
cΛ (d)/n)] ≤
Theorem 2.1, Pr[| i ≤r X i − r N
2
c
2 exp(−(ε /100)(r N Λ (d)/n) ≤ 1/100.
cΛ (d) ≤ (c/10ε 2 )(n/r ). Note that E[Íi ≤r X i ] ≤ c/10ε 2
Case 2: N
Í
2
≤ (c/ε )/2e. By the upper tail bound of Theorem 2.1, Pr[ i ≤r X i ≥
2
c/ε ] < 1/100.
Thus, with probability at least 99/100, if an estimate is output
cΛ (d) > (c/10ε 2 )(n/r ). By the first case, with probability
in Step 6, N
e(d) is a (1 + ε/10)-estimate for N
cΛ (d). A union
at least 99/100, N
bound completes the first part.

THE MAIN RESULT AND SADDLES

We begin by stating the main result, and explaining how heavy
tails lead to sublinear algorithms.
Theorem 3.1. There exists an algorithm SADDLES with the
following properties. For any ε > 0, β > 0, it outputs an
(ε, ε)-approximation of the ccdh with probability > 1 − β. The total
representation size is O((log n)/ε). The expected running time depends
on the model.
• SM: O((n/h + m/z 2 )(ε −3 log(n/εδ ))).
6

Lemma 4.4. Fix any good Λ and d. Suppose r ≥ cε −2n/d. With
probability at least 9/10,
Õ
cΛ (d)
wtΛ,d (v) ∈ (1 ± ε/8)(r /n)N

Algorithm 1: SADDLES(d, r , q)
Inputs:
d: degree for which N(d) is to be computed
r: budget for vertex samples
q: budget for edge samples
Output:
e(d): estimated N (d)
N
1
2
3

4
5
6
7

8
9
10
11
12
13

.

Í
Proof. Let wt(R) denote v ∈R wtΛ,d (v). By linearity of
Í
cΛ (d). To
expectation, E[wt(R)] = (r /n)· v ∈V wtΛ,d (v) ≥ (r /2n)N
apply the Chernoff bound, we need to bound the maximum weight
of a vertex. For good Λ, the weight wtΛ,d of any ordered pair is at
most 1/(1 − ε/10)d ≤ 2/d. The number of neighbors of v such that
cΛ (d). Thus, wtΛ,d (v) ≤ 2N
cΛ (d)/d.
dˆu ≥ d is at most N
By the Chernoff bound of Theorem 2.1 and setting r ≥ cε −2n/d,

Repeat for i = 1, . . . , r ;
Select u.a.r. vertex v and add it to multiset R ;
In HDM, call DEG(v) to get estimate dˆv . In SM, set dˆv to dv .
;
If dˆ ≥ d, set X i = 1. Else, X i = 0. ;
Í v
If i ≤r X i ≥ c/ε 2 ;
e(d) = n Íi ≤k X i ;
Return N
r
Í
Let dˆR = v ∈R dˆv and D denote the distribution over R
where v ∈ R is selected with probability dˆv /dˆR ;
Repeat for i = 1, . . . , q ;
Sample v ∼ D ;
Pick u.a.r. neighbor u of v ;
Call DEG(u) to get dˆu ;
If dˆu ≥ d, set Yi = 1/dˆu . Else, set Yi = 0 ;
q
e(d) = n · dˆR Í Yi .
Return N
r
q

Pr [|wt(R) − E[wt(R)]| > (ε/20)E[wt(R)]]
!
cΛ (d)/2n)
ε 2 · (cε −2n/d) · (N
< 2 exp −
≤ 1/10
cΛ (d)/d
3 · 202 · 2N
With probability at least 9/10, wt(R) ∈ (1 ± ε/20)E[wt(R)]. By
cΛ (d). We
the arguments given above, E[wt(R)] ∈ (1 ± ε/9)(r /n)N
combine to complete the proof.

Now, we determine the number of edge samples required to
estimate the weight wtΛ,d (R).
e(d) be as defined in Step 13 of SADDLES. Assume
Lemma 4.5. Let N
cΛ (d)). Then, with
Λ is good, r ≥ cε −2n/d, and q ≥ cε −2m/(d N
e(d) ∈ (1 ± ε/4)N
cΛ (d).
probability > 7/8, N

i=1

cΛ (d) ≥ (2c/ε 2 )(n/r ), then with probability at
Furthermore, if N
Í
cΛ (d)/n ≥ c/ε 2 . A union boun
least 99/100, i ≤r X i ≥ (1 − ε/10)r N
proves (the contrapositive of) the second part.


Proof. We define the random set R selected in Step 2 to be
Í
sound if the following hold. (1) wt(R) = v ∈R wtΛ,d (v) ∈ (1 ±
Í
cΛ (d) and (2) v ∈R dv ≤ 100r (2m/n). By Lemma 4.4, the
ε/8)(r /n)N
Í
first holds with probability > 9/10. Observe that E[ v ∈R dv ] =
r (2m/n), since 2m/n is the average degree. By the Markov bound,
the second holds with probability > 99/100. By the union bound, R
is sound with probability at least 1 − (1/10 + 1/100) > 8/9.
Fix a sound R. Recall Yi from Step 12. The expectation of Yi |R
Í
Í
is v ∈R Pr[v is selected]· u ∈Γ(v) Pr[u is selected]wtΛ,d (hv, ui).
We plug in the probability values, and observe that for good Λ,
for all v, dˆv /dv ∈ (1 ± ε/10).
Õ
Õ
(1/dv )wtΛ,d (hv, ui)
E[Yi |R] =
(dˆv /dˆR )

We define weights of ordered edges. The weight only depends on
the second member in the pair, but allows for a more convenient
analysis. The weight of hv, ui is the random variable Yi of Step 12.
Definition 4.2. The d-weight of an ordered edge hv, ui for a
given Λ (the randomness of DEG) is defined as follows. We set
wtΛ,d (hv, ui) to be 1/dˆu if dˆu ≥ d, and zero otherwise.
Í
For vertex v, wtΛ,d (v) = u ∈Γ(v) wtΛ,d (hv, ui).
The utility of the weight definition is captured by the following
e(d), and thus, we
claim. The total weight is an approximation of N
can analyze how well SADDLES approximates the total weight.
Í
cΛ (d).
Claim 4.3. If Λ is good, v ∈V wtΛ,d (v) ∈ (1 ± ε/9)N
Proof.
Õ

wtΛ,d (v)

=

v ∈V

Õ Õ
v ∈V u ∈Γ(v)

=

Õ

v ∈R

=

u:dˆu ≥d v ∈Γ(u)

1/dˆu =

(1/dˆR )

u ∈Γ(v)

Õ

(dˆv /dv )

v ∈R

∈

1dˆu ≥d /dˆu

Õ

v ∈R

(1 ± ε/10)(1/dˆR )

Õ

wtΛ,d (hv, ui)

u ∈Γ(v)

Õ Õ

wtΛ,d (hv, ui)

v ∈R u ∈Γ(v)

Õ

du /dˆu

(1 ± ε/10)(wt(R)/dˆR )

(2)
Í
ˆ
e
N (d)
=
(n/r )(d R /q) i ≤q Yi
Note
that
and
Í
(n/r )(dˆR /q)E[ i ≤q Yi |R] ∈ (1 ± ε/10)(n/r )wt(R). Since R is
cΛ (d). Also, note that
sound, the latter is in (1 ± ε/4)N
∈

(1)

u:dˆu ≥d

Since Λ is good, ∀u, dˆu ∈ (1 ± ε/10)du , and du /dˆu ∈ (1 ± ε/9).
Í
cΛ (d).
Applying in (1), v ∈V wtΛ,d (v) ∈ (1 ± ε/9)N


cΛ (d)
c (d)
qwt(R)
(r /n)N
N
≥
= Λ
(3)
ˆ
4(100r (2m/n)
800m
2d R
Í
By linearity of expectation, E[ i ≤q Yi |R] = qE[X 1 |R]. Observe
that Yi ≤ 1/d. We can apply the Chernoff bound of Theorem 2.1 to
E[Yi |R] = E[X 1 |R] ≥

We come to an important lemma, that shows that the weight
of the random subset R (chosen in Step 2) is well-concentrated.
This is proven using a Chernoff bound, but we need to bound the
maximum possible weight to get a good bound on r = |R|.
7

Proof. (of Theorem 3.1) The overall algorithm is the same for
both models, involving multiple invocations to SADDLES. The
only difference is in DEG, which is trivial when degree queries are
allowed. We first argue about correctness.
Consider the set D = {b(1 + ε/10)i c|0 ≤ i ≤ 10ε −1 log n}. We
will run a boosted version of SADDLES for each degree in D. The
e(d 0 ), where d 0 is the largest
output for an arbitrary d will be N
power of (1 + ε/10) smaller than d (rounding down). The boosting
is done through Theorem 2.2, which ensures we can get the desired
estimate for each d with probability > 1 − εβ/100n. A union bound
over all d ∈ D yields a total error probability of at most β.
Observe that the query complexity and running time of
SADDLES are within constant factors of each other. Hence, we
only focus on the number of queries made. For the Standard Model,
the bound for a single invocation of SADDLES is simply O(r + q)
= O(ε −2 (n/h + m/z 2 )).
For the Hidden Degrees Model, we have to account for
the overhead of using Ron-Tsur birthday paradox algorithm of
Corollary 2.7 for each degree estimated.
The number of queries
√
for a single call to DEG(d) is O(ε −2
d
log
n). The total overhead
v
√
Í
of all calls in Step 3 is E[ v ∈R d√v (ε −2 log n)]. By linearity of
expectation, this is O((ε −2 log n)r E[ dv ], where the√expectation is
over a uniform random vertex. We can bound r E[ dv ] ≤ r E[dv ]
= O(ε −2n(m/n)/h) = O(ε −2n/h).
The total overhead of all calls in Step 11 requires more care.
Note that when DEG(v) is called multiple times for a fixed v, the
subsequent calls require no further queries. (This is because the
output of the first call can be stored.) We partition the vertices
into two sets S 0 = {v |dv ≤ z 2 } and S 1 = {v |dv > z 2 }. The total
query cost of queries to S 0 is at most O(q f ) = O((ε −2 log n)m/z).
For the total cost
we directly√bound by (ignoring the ε −2 log n
√ to S 1 ,Í
Í
Í
factor) v ∈S 1 dv = v ∈S 1 dv / dv ≤ z −1 v dv = O(m/z). All
−4
in all, the total query complexity is O((ε log2 )(n/h + m/z)). Since
m ≥ n and z ≤ h, we can simplify to O((ε −4 log2 n)(m/z)).


the iid random variables (Yi |R).
Õ
Õ
Õ
Pr[|
Yi − E[ Yi ]| > (ε/100)E[ Yi ]|R]
i



i



· d · qE[X 1 |R]
(4)
3 · 1002
We use (3) to bound the (positive) term in the exponent is at least
≤

2 exp −

i

ε2

c (d)
cε −2m N
ε2
·
· Λ
≥ 10.
2
cΛ (d) 800m
3 · 100 N
Thus, if R is sound, the following bound holds with probability at
least 0.99. We also apply (2).
cΛ (d)
N

=

(n/r )(dˆR /q)

q
Õ

Yi

i=1

∈

(1 ± ε/100)(n/r )(dˆR /q)qE[Yi |R]

∈

e(d)
(1 ± ε/100)(1 ± ε/10)(n/r )wt(R) ∈ (1 ± ε/4)N

The probability that R is sound is at least 8/9. A union bound
completes the proof.

The bounds on r and q in Lemma 4.5 depend on the degree d. We
now bring in the h and z-indices to derive bounds that hold for all
d. We also remove the conditioning over a good Λ.
Theorem 4.6. Let c be a sufficiently large constant. Suppose r ≥
cε −2n/h and q ≥ cε −2m/z 2 . Then, for all d, with probability ≥ 5/6,
e(d) ∈ [(1 − ε/2)N ((1 + ε/2)d), (1 + ε/2)N ((1 − ε/2)d].
N
Proof. We will first assume that Λ is good. By Claim 2.10,
cΛ (d) ∈ [N ((1 + ε/9)d, N ((1 − ε/9)d)].
N
cΛ (d) = 0, so there are no vertices with dˆv ≥ d. By the
Suppose N
bound above, N ((1 + ε/9)d) = 0, implying that N ((1 + ε/2)d) = 0.
e(d) = 0, since the random variables X i and Yi in
Furthermore N
e(d) = N ((1 + ε/2)d),
SADDLES can never be non-zero. Thus, N
completing the proof.
cΛ (d) > 0. We split into two cases,
We now assume that N
depending on whether Step 6 outputs or not. By Claim 4.1, with
e(d) ∈ (1 ± ε/9)N
cΛ (d).
probability > 9/10, if Step 6 outputs, then N
e(d) holds with
By combining these bounds, the desired bound on N
probability > 9/10, conditioned on a good Λ.
Henceforth, we focus on the case that Step 6 does not output. By
cΛ (d) < 2cε −2 (n/r ). By the choice of r and Claim 2.10,
Claim 4.1, N
cΛ ((1 + ε/9)d) < h. By the characterization of h of Lemma 2.3,
N
cΛ ((1 + ε/9)d), (1 + ε/9)d) = (1 + ε/9)d.
z 2 ≤ max(N
cε −2n/d.

5

EXPERIMENTAL RESULTS

We implemented our algorithm in C++ and performed our
experiments on a MacBook Pro laptop with 2.7 GHz Intel Core
i5 with 8 GB RAM. We performed our experiments on a collection
of graphs from SNAP [29], including social networks, web networks,
and infrastructure networks. The graphs typically have millions of
edges, with the largest with more than 100M edges. Basic properties
of these graphs are presented in Table 1. We ignore direction and
treat all edges as undirected edges.

(5)
z2

This implies that r ≥
By the definition of z,
≤
N (min(dmax , (1 +ε/9)d)) · min(dmax , (1 +ε/9)d). By the Claim 2.10
cΛ (d) ≥ N ((1+ε/9)d). Since N
cΛ (d) >
bound in the first paragraph, N
2
c
c
c
0, N Λ (d) ≥ N Λ (dmax ). Plugging into (5), z ≤ N Λ (d) · (1 + ε/9)d.
cΛ (d)). The parameters satisfy the conditions
Thus, m ≤ cε −2m/(d N
e(d) ∈ (1 ± ε/4)N
cΛ (d), and
in Lemma 4.5. With probability > 7/8, N
e(d) has the desired accuracy.
by Claim 2.10, N
e(d)
All in all, assuming Λ is good, with probability at least 7/8, N
has the desired accuracy. The conditioning on a good Λ is removed
by Claim 2.9 to complete the proof.


5.1

Implementation Details

For the Hidden Degrees Model, we explicitly describe the procedure
DEG, which estimates the degree of a given vertex. In the algorithm
Algorithm 2: DEG(v)
1
2

3

We finally prove Theorem 3.1.
8

Initialize S = ∅ ;
Repeatedly add u.a.r. vertex to S, until the number of pair-wise
collisions is at least k = 50 ;

Output |S | /k as estimate dˆv
2

size of n/h + m/z 2 (as given by Theorem 3.1, ignoring constants)
is significantly sublinear. This is consistent with our choice of
r + q = n/100 leading to accurate estimates for the ccdh.

DEG, a “pair-wise collision” refers to a pair of neighbor samples
that yield the same vertex. If S has size t, the expected number
of pair-wise collisions is t2 /dv . We simply reverse engineer that
inequality to get the estimate dˆv . Ron√and Tsur essentially prove
that with high probability, |S | = Θ( dv ) and furthermore, this
suffices to bound the variance of the estimate [41].
Our implementation of SADDLES is identical to the pseudo-code
given in Alg. 1. The only constant to be set is c/ε 2 in Step 5, which
our implementation fixes at 25. There are two parameters r and
q that are chosen to be typically around 0.005n. To get the entire
degree distribution, we run SADDLES on all degrees d = b1.1i c.

5.2

5.3

Comparison with previous work

There are several graph sampling algorithms that have been
discussed in [2, 17, 28, 30, 38, 39, 47]. We describe these methods
below in more detail, and discuss our implementation of the method.
• Vertex Sampling (VS, also called egocentric sampling) [5, 17,
28, 30, 38, 39]: In this algorithm, we sample vertices u.a.r. and scale
the ccdh obtained appropriately, to get an estimate for the ccdh of
the entire graph.
• Edge Sampling (ES) [5, 17, 28, 30, 38, 39]: This algorithm
samples edges u.a.r. and includes one or both end points in the
sampled network. Note that this does not fall into the standard
model. In our implementation we pick a random end point.
• Random walk with jump (RWJ) [5, 17, 30, 38, 39]: We start
a random walk at a vertex selected u.a.r. and collect all vertices
encountered on the path in our sampled network. At any point,
with a constant probability (0.15 in our implementation, based on
previous results) we jump to another u.a.r. vertex.
• One Wave Snowball (OWS) [5, 17, 28]: Snowball sampling
starts with some vertices selected u.a.r. and crawls the network until
a network of the desired size is sampled. In our implementation,
we typically stop at the one level since that accumulates enough
vertices.
• Forest fire (FF) [5, 17, 30]: This method generates random
sub-crawls of the network, and is related to snowball sampling. A
vertex is picked u.a.r. and randomly selects a subset of its neighbors.
In previous work, this is done by choosing x such neighbors, where
x is a geometric random variable with mean 0.2. The process is
repeated from every selected vertex until it ends. It is then repeated
from another u.a.r. vertex.
We run all these algorithms on the amazon0601, web-Google,
cit-Patents, and com-orkut networks. To make fair comparisons,
we run each method until it selects 1% of the vertices. The
comparisons are shown in Fig. 1. Observe how none of the methods
come close to accurately measuring the ccdh. (This is consistent
with previous work, where typically 10-20% of the vertices are
sampled for results.) Naive vertex sampling is accurate at the head
of the distribution, but completely misses the tail. Except for vertex
sampling, all other algorithms are biased towards the tail. Crawls
find high degree vertices with disproportionately higher probability,
and overestimate the tail.

Evaluation of SADDLES

The sample size of SADDLES in the Standard Model is exactly r + q.
We will typically fix this to be 1% of the number of vertices in our
runs, unless otherwise stated.
Accuracy over all graphs. We show results of running
SADDLES with the parameters discussed above for a variety of
graphs. Fig. 1, and Fig. 2 show the results for the Standard Model on
all graphs in Tab. 1. For all these runs, we set r + q to be 1% of the
number of vertices in the graph. For the Hidden Degrees Model, we
show results in Fig. 3. For space reasons, we only show results on
HDM for the graphs in Fig. 2, though results are consistent over all
our experiments. Again, we set r + q to be 1%, though the number
of edges sampled varies quite a bit. The required number of samples
are provided in Tab. 1. Note that the number of edges sampled is
well within 10% of the total, except for the com-youtube graph.
Visually, we can see that the estimates are accurate for all degrees,
in all graphs, for both models. This is despite there being sufficient
irregular behavior in N (d). For example, the web-BerkStan ccdh
(Fig. 1) is quite “bumpy” between degree 102 and 104 , and the
extreme tail has sudden jumps. Note that the shape of the various
ccdhs are different and none of them form an obvious straight line.
Nonetheless, SADDLES captures the distribution almost perfectly
in all cases by observing 1% of the vertices.
Convergence. To demonstrate convergence, we use the
following setup. In the figures, we fix the graph com-orkut, and
run SADDLES only for the degrees 10, 100, and 1000. For each
choice of degree, we vary the total number of samples r + q. (We
set r = q in all runs.) Finally, for each setting of r + q and each
degree, we perform 100 independent runs of SADDLES.
For each such run, we compute an error parameter α. Suppose
the output of a run is M, for degree d. The value of α is the smallest
value of ϵ, such that M ∈ [(1 − ϵ)N ((1 + ϵ)d), (1 + ϵ)N ((1 − ϵ)d)].
(It is the smallest ϵ such that M is an (ϵ, ϵ)-approximation of N (d).)
Fig. 4 shows the spread of α, for the 100 runs, for each choice
of r + q. Observe how the spread decreases as r + q goes to 10%.
In all cases, the values of α decay to less than 0.05. We notice that
convergence is much faster for d = 10. This is because N (10) is
quite large, and SADDLES is using vertex sampling to estimate the
value.

Inverse method of Zhang et al [47]. An important result
of estimating degree distributions is that of Zhang et al [47],
that explicitly points out the bias problems in various sampling
methods. They propose a bias correction method by solving an
ill-conditioned linear system. Essentially, given one of the above
sampled networks, it applies a constrained, penalized weighted
least-squares approach to solving the problem of debiasing the
estimated degree distribution. We apply this method for the
sampling methods demonstrated in their paper, namely vertex
sampling (VS), one-wave snowball (OWS), and induced sampling
(IN) (sample vertices u.a.r. and only retain edges between sampled
vertices). We show results in Fig. 1, again with a sample size of 1% of

Large value of h and z-index on real graphs. The h and
z-index of all graphs is given in Tab. 1. Observe how they are
typically in the hundreds. Note that the average degree is typically
an order of magnitude smaller than these indices. Thus, a sample
9

Table 1: Graph properties: #vertices (n), #edges (m), maximum degree, h-index and z-index. The last column indicates the
median number of samples over 100 runs (as a percentage of m) required by SADDLES under HDM to estimate the ccdh for
r + q = 0.01n. For all graphs except one, the number of samples required is < 0.1m.

graph
loc-gowalla
web-Stanford
com-youtube
web-Google
web-BerkStan
wiki-Talk
as-skitter
cit-Patents
com-lj
soc-LiveJournal1
com-orkut

#vertices
1.97E+05
2.82E+05
1.13E+06
8.76E+05
6.85E+05
2.39E+06
1.70E+06
3.77E+06
4.00E+06
4.85E+06
3.07E+06

#edges
9.50E+05
1.99E+06
2.99E+06
4.32E+06
6.65E+06
9.32E+06
1.11E+07
1.65E+07
3.47E+07
8.57E+07
1.17E+08

max.
degree
14730
38625
28754
6332
84230
100029
35455
793
14815
20333
33313

avg.
degree
4.8
7.0
2.6
4.9
9.7
3.9
6.5
4.3
8.6
17.7
38.1

H-index
275
427
547
419
707
1055
982
237
810
989
1638

Z-index
101
148
121
73
220
180
184
28
114
124
172

Perc. edge
samples for HDM)
7.0
6.4
11.7
6.2
5.5
8.5
6.7
5.6
4.7
2.4
2.0

(a) as-skitter

(b) loc-gowalla

(c) web-Google

(d) wiki-Talk

(e) soc-LiveJournal

(f) com-lj

(g) web-BerkStan

(h) com-youtube

Figure 2: The result of runs of SADDLES on a variety of graphs, for the Standard Model. We set r + q to be 1% of the number of
vertices, for all graphs. Observe the close match at all degrees between the true degree distribution and output of SADDLES.
the vertices. Observe that no method get even close to estimating
the ccdh accurately, even after debiasing. Fundamentally, these
methods require significantly more samples to generate accurate
estimates.
The running time and memory requirements of this method
grow superlinearly with the maximum degree in the graph. The
maximum degree is not known in advance, but the algorithm needs
to know this value , so it uses an upper bound. The largest graph

processed by [47] has a few hundred thousand edges, which is on
the smaller side of graphs in Tab. 1. SADDLES processes a graph
with more than 100M edges in less than a minute, while our attempts
to run the [47] algorithm on this graph did not terminate in hours.

6

ACKNOWLEDGEMENTS

Ali Pinar’s work is supported by the Laboratory Directed Research
and Development program at Sandia National Laboratories. Sandia
10

(a) as-skitter

(b) loc-gowalla

(c) web-Google

(d) wiki-Talk

Figure 3: The result of runs of SADDLES on a variety of graphs, for the Hidden Degrees Model. We set r + q to be 1% of the
number of vertices, for all graphs. The actual number of edges sampled varies, and is given in Tab. 1.

(a) d = 10

(b) d = 100

(c) d = 1000

(d) d = 10000

Figure 4: Convergence of SADDLES: We plot the values of the error parameter α (as defined in §5.2) for 100 runs at increasing
values of r + q. We have a different plot for d = 10, 100, 1000, 10000 to show the convergence at varying portions of the ccdh.
National Laboratories is a multimission laboratory managed and
operated by National Technology and Engineering Solutions
of Sandia, LLC., a wholly owned subsidiary of Honeywell
International, Inc., for the U.S. Department of Energy’s National
Nuclear Security Administration under contract DE-NA-0003525.
Both Shweta Jain and C. Seshadhri are grateful to the support
of the Sandia National Laboratories LDRD program for funding
this research. C. Seshadhri also acknowledges the support of NSF
TRIPODS grant.
This research was partially supported by the Israel Science
Foundation grant No. 671/13 and by a grant from the Blavatnik
fund. Talya Eden is grateful to the Azrieli Foundation for the award
of an Azrieli Fellowship.
Both Talya Eden and C. Seshadhri are grateful to the support
of the Simons Institute, where this work was initiated during the
Algorithms and Uncertainty Semester.

[5] Nesreen K Ahmed, Jennifer Neville, and Ramana Kompella. 2014. Network
sampling: From static to streaming graphs. TKDD 8, 2 (2014), 7.
[6] 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.
[7] Albert-László Barabási and Réka Albert. 1999. Emergence of Scaling in Random
Networks. Science 286 (Oct. 1999), 509–512.
[8] 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
33 (2000), 309–320.
[9] Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph Mining: Laws,
Generators, and Algorithms. Comput. Surveys 38, 1 (2006). DOI:http://dx.doi.
org/10.1145/1132952.1132954
[10] 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).
[11] A. Clauset and C. Moore. 2005. Accuracy and scaling phenomena in internet
mapping. Phys. Rev. Lett. 94 (2005), 018701.
[12] A. Clauset, C. R. Shalizi, and M. E. J. Newman. 2009. Power-Law Distributions in
Empirical Data. SIAM Rev. 51, 4 (2009), 661–703. DOI:http://dx.doi.org/10.1137/
070710111
[13] R. Cohen, K. Erez, D. ben Avraham, and S. Havlin. 2000. Resilience of the Internet
to Random Breakdowns. Phys. Rev. Lett. 85, 4626fi?!8 (2000).
[14] A. Dasgupta, R. Kumar, and T. Sarlos. 2014. On estimating the average degree.
In Conference on the World Wide Web (WWW). 795–806.
[15] D. Dubhashi and A. Panconesi. 2012. Concentration of Measure for the Analysis
of Randomised Algorithms. Cambridge University Press.
[16] 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. DOI:http://dx.doi.org/
10.1109/NSW.2013.6609190
[17] Peter Ebbes, Zan Huang, Arvind Rangaswamy, Hari P Thadakamalla, and ORGB
Unit. 2008. Sampling large-scale social networks: Insights from simulated
networks. In 18th Annual Workshop on Information Technologies and Systems,
Paris, France.

REFERENCES
[1] 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 56, 4
(2009).
[2] N.K. Ahmed, J. Neville, and R. Kompella. 2010. Reconsidering the Foundations
of Network Sampling. In WIN 10.
[3] N. Ahmed, J. Neville, and R. Kompella. 2012. Space-Efficient Sampling from
Social Activity Streams. In SIGKDD BigMine. 1–8.
[4] Nesreen K Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. 2014.
Graph sample and hold: A framework for big-graph analytics. In SIGKDD. ACM,
ACM, 1446–1455.
11

[18] T. Eden, A. Levi, D. Ron, and C. Seshadhri. 2015. Approximately Counting
Triangles in Sublinear Time. In Foundations of Computer Science (FOCS), GRS11
(Ed.). 614–633.
[19] T. Eden, D. Ron, and C. Seshadhri. 2017. Sublinear Time Estimation of Degree
Distribution Moments: The Degeneracy Connection. In International Colloquium
on Automata, Languages, and Programming (ICALP), GRS11 (Ed.). 614–633.
[20] M. Faloutsos, P. Faloutsos, and C. Faloutsos. 1999. On power-law relationships
of the internet topology. In SIGCOMM. 251–262.
[21] U. Feige. 2006. On sums of independent random variables with unbounded
variance and estimating the average degree in a graph. SIAM J. Comput. 35, 4
(2006), 964–984.
[22] O. Goldreich and D. Ron. 2002. Property Testing in Bounded Degree Graphs.
Algorithmica (2002), 302–343.
[23] O. Goldreich and D. Ron. 2008. Approximating average parameters of graphs.
Random Structures and Algorithms 32, 4 (2008), 473–493.
[24] M. Gonen, D. Ron, and Y. Shavitt. 2011. Counting stars and other small subgraphs
in sublinear-time. SIAM Journal on Discrete Math 25, 3 (2011), 1365–1411.
[25] Mira Gonen, Dana Ron, Udi Weinsberg, and Avishai Wool. 2008. Finding a
dense-core in Jellyfish graphs. Computer Networks 52, 15 (2008), 2831–2841. DOI:
http://dx.doi.org/10.1016/j.comnet.2008.06.005
[26] J. E. Hirsch. 2005. An index to quantify an individual’s scientific research output.
Proceedings of the National Academy of Sciences 102, 46 (2005), 16569fi?!16572.
[27] A. Lakhina, J. Byers, M. Crovella, and P. Xie. 2003. Sampling biases in IP topology
measurements. In Proceedings of INFOCOMM, Vol. 1. 332–341.
[28] Sang Hoon Lee, Pan-Jun Kim, and Hawoong Jeong. 2006. Statistical properties
of sampled networks. Physical Review E 73, 1 (2006), 016102.
[29] Jure Leskovec. 2015. SNAP Stanford Network Analysis Project. http://snap.
standord.edu. (2015).
[30] Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In
Knowledge Data and Discovery (KDD). ACM, 631–636.
[31] 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 (2011), 105–113.
[32] Andrew McGregor. 2014. Graph stream algorithms: A survey. SIGMOD 43, 1
(2014), 9–20.
[33] M. Mitzenmacher. 2003. A Brief History of Generative Models for Power Law
and Lognormal Distributions. Internet Mathematics 1, 2 (2003), 226–251.
[34] M. E. J. Newman. 2003. The Structure and Function of Complex Networks. SIAM
Rev. 45, 2 (2003), 167–256. DOI:http://dx.doi.org/10.1137/S003614450342480
[35] M. E. J. Newman, S. Strogatz, and D. Watts. 2001. Random graphs with arbitrary
degree distributions and their applications. Physical Review E 64 (2001), 026118.
[36] 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 99, 8 (2002), 5207–5211. DOI:http://dx.doi.
org/10.1073/pnas.032085699
[37] T. Petermann and P. Rios. 2004. Exploration of scale-free networks. European
Physical Journal B 38 (2004), 201–204.
[38] 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).
[39] Bruno Ribeiro and Don Towsley. 2012. On the estimation accuracy of degree
distributions from graph sampling. In Annual Conference on Decision and Control
(CDC). IEEE, 5240–5247.
[40] Dana Ron. 2010. Algorithmic and Analysis Techniques in Property Testing.
Foundations and Trends in Theoretical Computer Science 5, 2 (2010), 73–205.
[41] 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 8, 4 (2016), 15:1–15:19.
[42] C. Seshadhri, Tamara G. Kolda, and Ali Pinar. 2012. Community structure and
scale-free collections of Erdös-Rényi graphs. Physical Review E 85, 5 (May 2012),
056109. DOI:http://dx.doi.org/10.1103/PhysRevE.85.056109
[43] 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.
[44] Sucheta Soundarajan, Tina Eliassi-Rad, Brian Gallagher, and Ali Pinar. 2016.
MaxReach: Reducing network incompleteness through node probes. 152–157.
DOI:http://dx.doi.org/10.1109/ASONAM.2016.7752227
[45] Sucheta Soundarajan, Tina Eliassi-Rad, Brian Gallagher, and Ali Pinar. 2017. ϵ
- WGX: Adaptive Edge Probing for Enhancing Incomplete Networks. In Web
Science Conference. 161–170.
[46] Michael PH Stumpf and Carsten Wiuf. 2005. Sampling properties of random
graphs: the degree distribution. Physical Review E 72, 3 (2005), 036118.
[47] 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 9, 1 (2015),
166–199.
12

