Sampling Techniques for Large, Dynamic Graphs

Daniel Stutzbach, Reza Rejaie Nick Duffield, Subhabrata Sen, Walter Willinger
University of Oregon AT&T Labs—Research
{agthorr,reza}@[Link] {duffield,sen,walter}@[Link]

Abstract— Peer-to-peer systems are becoming increasingly significant bias in two ways. The first cause of bias is the
popular, with millions of simultaneous users and a wide range highly dynamic nature of these systems. It is easy to imagine
of applications. Understanding existing systems and devising the overlay as a static graph from which we want to collect a
new peer-to-peer techniques relies on access to representative
models derived from empirical observations. Due to the large set of peers. However, gathering a set of samples takes time,
and dynamic nature of these systems, directly capturing global and during that time the graph will change. In Section II-A,
behavior is often impractical. Sampling is a natural approach for we show how this often leads to bias towards short-lived peers
learning about these systems, and most previous studies rely on and explain how to overcome this difficulty.
it to collect data.
The second significant cause of bias is the graph properties
This paper addresses the common problem of selecting rep-
resentative samples of peer properties such as peer degree, link of the P2P topology. A naive approach will be heavily biased
bandwidth, or the number of files shared. A good sampling tech- towards high-degree peers. As the sampling program explores
nique will select any of the peers present with equal probability. the graph, each link it traverses is much more likely to lead
However, common sampling techniques introduce bias in two to a high-degree peer than a low-degree peer. We describe
ways. First, the dynamic nature of peers can bias results towards
different techniques for traversing the overlay to select peers in
short-lived peers, much as naively sampling flows in a router can
lead to bias towards short-lived flows. Second, the heterogeneous Section II-B and evaluate them in Section III via simulation. In
overlay topology can lead to bias towards high-degree peers. We this preliminary work, we simulate using two types of graphs:
present preliminary evidence suggesting that applying a degree- ordinary random graphs and an actual snapshot of the Gnutella
correction method to random walk-based peer selection leads to graph topology [22]. In our ongoing work, we are adding other
unbiased sampling, at the expense of a loss of efficiency.
types of random graphs, such as certain power-law random
I. I NTRODUCTION graphs and small-world graphs, to explore the robustness of the
considered techniques to different types of graph structures. By
Peer-to-peer (P2P) systems are becoming increasingly pop-
comparing and contrasting the performance of different tech-
ular, with millions of simultaneous users [1] and covering a
niques in different settings, we can gain a better understanding
wide range of applications, from file-sharing programs like
of the most efficient techniques to consistently yield unbiased
LimeWire and eMule to Internet telephony services such as
(or only slightly biased) samples.
Skype. Understanding existing systems and devising new P2P
techniques relies on having access to representative models In summary, bias in sampling from P2P systems can be
derived from empirical observations of existing systems. How- introduced along two axes: (i) temporal (due to differences in
ever, due to the large and dynamic nature of P2P systems, peer lifetimes) and (ii) topological (due to differences in peer
it is often difficult or impossible to directly capture global degree). Our findings show that these factors cause heavy bias
behavior. Sampling is a natural approach for learning about in commonly used techniques such as breadth-first search and
these systems using light-weight data collection, relied on by random walks. We present preliminary evidence suggesting
most previous studies (e.g., [4], [19]). One challenge, however, that applying a degree-correction method to random walk leads
is ensuring that the samples are representative (or unbiased). to unbiased sampling, at the expense of a loss of efficiency.
This paper addresses the common problem of selecting Section IV discusses related work, and Section V concludes
representative samples of peer properties such as peer degree, the paper with a summary of our findings and plans for future
link bandwidth, or the number of files shared [24]. To examine work.
peer properties, any sampling technique needs to locate a set
of peers in the overlay and gather data from them. Initially, II. S AMPLING P EER P ROPERTIES
the sampling program is aware of a handful of peers and
Our goal in this paper is to tackle the common problem of
leveraging them to learn about additional peers. Typically, the
sampling peer properties, which covers a wide range of in-
sampling program queries known peers to learn about their
teresting aspects. Examples include products of user behavior
neighbors, incrementally exploring a fraction of the overlay
(such as the number of files shared and link bandwidth), local
graph.1 A good sampling technique will select any of the peers
graph properties (such as degree and clustering coefficient),
present with equal probability. However, as we will show,
and dynamic properties (such as remaining uptime). Global
commonly used sampling techniques can easily introduce
1 Other sampling programs rely on passive monitoring or querying for
properties, such as the graph diameter, cannot be determined
popular files, but such approaches are fundamentally biased towards peers easily using sampling and tend to rely on heavy-weight
generating more traffic or with those files. We do not consider them further. solutions, such as crawling the entire overlay [21].
 St0 +∆
Collecting a sample of a property is a two-step process. a vertex vi ∈ t=t 0
Vt , but rather to sample the property at
First, the selection process explores part of the P2P overlay vi at a particular instant t. This means we must view vi,t and
and selects a peer. Second, a property-specific measurement vi,t′ as distinct samples even though they come from the same
tool gathers the sample. For example, sampling the clustering peer. The key difference is that it must be possible to sample
coefficient requires gathering the neighbor information for the from the same peer more than once, at different points in time.
selected peer and all of its neighbors. Sampling the remain- We may accomplish this goal by sampling selecting t and vi,t
ing uptime requires monitoring the peer until it departs the uniformly from the sets:
network. This paper is concerned with the first step, selecting t ∈ [t, t0 + ∆], vi,t ∈ Vt
a peer, which is the common aspect for sampling any peer
This sampling technique will not be biased by the dynamics of
property.
peer behavior, because the sample set is decoupled from peer
The goal is to select an unbiased sample, meaning selecting
session lengths. To our knowledge, no prior P2P measurement
the sample uniformly at random. Additionally, the sampling
studies relying on sampling use this approach.
process should also be efficient, meaning that the sampling
Returning to our simple example, this approach will cor-
process should not have to explore a large portion of the graph
rectly select long-lived peers half the time and short-lived
to select an unbiased sample. As we described in Section I,
peers half the time. When the samples are examined, they will
bias can be caused by the dynamic nature of P2P systems
show that half of the peers in the system at any given moment
and by their graph structure. In the following two sections we
have many files while half of the peers have few files, which
introduce mechanisms to cope with these problems.
is exactly correct.
A. Coping with dynamics We can now divide the sampling process into two parts: (i)
selecting times uniformly at random and (ii) selecting peers
We develop a formal and general model of a P2P system as
uniformly at random from all peers available at that time.
follows. If we take an instantaneous snapshot of the system at
Selecting times uniformly at random can be easily achieved
time t, we can view the overlay as a graph G(V, E) with the
by generating times between samples using an exponential
peers as vertices and connections between the peers as edges.
distribution. At each chosen time, we must collect a sample
Extending this notion, we incorporate the dynamic aspect by
from the peers present at that time, which reduces to the
viewing the system as an infinite series of time-indexed graphs,
problem of selecting a vertex uniformly at random from a
Gt = G(Vt , Et ). The most common approach for sampling
graph. We address this problem in the next subsection.
from this series of graphs is to define a measurement window,
[t0 , t0 + ∆], and select peers uniformly at random from the
B. Coping with graph structure
set:
t0[
+∆
In this section, we discuss several techniques for selecting
Vt0 ,t0 +∆ = Vt vertices randomly from a graph. When sampling from a P2P
t=t0
system, we typically begin with knowledge of at least one
This formulation is appropriate if peer session lengths are peer and a method to query known peers for a list of their
exponentially distributed (i.e., memoryless). However, exist- neighbors. The goal is to explore a small fraction of the
ing measurement studies [10], [17], [19], [22] show session graph yet return a peer (vertex) uniformly at random. In
lengths are heavily skewed, with many peers being present Section III, we will evaluate the techniques discussed below
for just a short time (a few minutes) while other peers remain using simulation.
in the system for a very long time (i.e., longer than ∆). As Two classical ways to explore a graph are via breadth-first
a consequence, as ∆ increases, the set Vt0 ,t0 +∆ includes an (BFS) and depth-first search (DFS), often used by sampling
increasingly large fraction of short-lived peers. techniques that crawl a portion of the overlay topology (as
A simple example may be illustrative. Suppose we wish to in [19]). These techniques add newly discovered peers to a
observe the number of files shared by peers. In this example queue and choose new peers to explore by removing them
system, half the peers are up all the time and have many files, from the queue. They differ only in that BFS uses a FIFO
while the other peers remain for around 1 minute and are queue while DFS uses a LIFO queue. Neither of these tech-
immediately replaced by new short-lived peers, who have few niques allows duplicates, automatically causing bias towards
files. The technique used by most studies would observe the short-lived peers as described in the previous subsection. We
system for a long time (∆) and incorrectly conclude that most nevertheless include BFS in our simulations, to demonstrate
of the peers in the system have very few files. Moreover, their that it performs poorly even in a static system.
results will depend on how long they observe the system. The Another family of techniques are based on conducting a
longer they watch, the larger the fraction of observed peers random walk. The simplest approach is to perform a random
with few files. walk of length r, select the ending peer as a sample, then
One fundamental problem of this approach is that it focuses perform another walk of length r to get the next sample.
on sampling peers instead of peer properties. It selects each While this technique offers low bias for some types of graphs,
sampled vertex at most once. However, the property at the its efficiency is somewhat low ( r1 ). Graph theory [8], [15]
vertex may change with time. Our goal should not be to select suggests that a good choice is r ≥ log |V |.
 2500 2500
Histogram (# of peers)

Histogram (# of peers)
Oracle/RWDC/RSDC Oracle/RSDC
2000 RW/RS/BFS 2000 RW/RS
BFS
1500 1500 RWDC
1000 1000
500 500
0 0
600 800 1000 1200 1400 600 800 1000 1200 1400
Number of times sampled Number of times sampled
(a) Random Graph (b) Gnutella
Fig. 1. Bias of different sampling techniques; after collecting k · |V | samples, the figures show how many peers (y-axis) were selected x times
Oracle RWDC RSDC RW RS BFS Oracle RWDC RSDC RW RS BFS
Std. Deviation 32 32 32 206 207 210 Std. Deviation 32 65 32 865 866 806
Skew 0.03 0.03 0.03 0.21 0.21 0.22 Skew 0.03 -4.28 0.03 47 47.92 17
Kurtosis -0.01 -0.01 0.00 0.04 0.03 0.03 Kurtosis -0.01 30 0.00 3084 3087 703
Efficiency 100% 2% 4% 8% 99% 99% Efficiency 100% 2% 4% 8% 99% 99%
(a) Random Graph (b) Gnutella
TABLE I
B IAS OF DIFFERENT SAMPLING TECHNIQUES ; S TATISTICS CORRESPONDING WITH F IGURE 1

A more efficient technique performs a random walk of to explore the performance of these techniques according to
length r, returns that peer as a sample, then continues to three criteria:
walk and return every additional peer along the walk as a • Bias: Selecting some peers over others
sample [8]. However, by not walking r steps between every • Correlation: Selecting related peers
sample, the samples may be correlated due to the inherit • Efficiency: How much work is done to collect samples
relationship between adjacent peers. We call this technique In this preliminary work, we examine the behavior of
a “random stroll”. This technique is similar to DFS, except sampling techniques over two types of graphs: (i) ordinary
it allows duplicates. Since we prefer algorithms that allow random graphs and (ii) a Gnutella ultrapeer topology snapshot
duplicates, we omit DFS from our evaluations. from February 2005, examined in detail in our previous work
One problem with random walk techniques is that they on characterizing the Gnutella topology [22]. To make useful
are biased towards high-degree peers. It is well-known that comparisons, the random graphs have the same number of
they visit peers with frequency proportional to the peer’s vertices (161,680) and edges (1,946,596) as the Gnutella
degree [15]. One way to compensate for this problem is to alter topology. To generate edges for the random graphs, we select
the sample-selection criteria slightly. If a peer is a candidate pairs of nodes at random until we have the desired num-
for sampling, select it with probability d1 where d is the peer’s ber of edges, skipping duplicate edges and self-edges.3 We
degree, otherwise continue the walk and consider the next chose to use these random graphs because they have simple
peer.2 properties and are easy to understand, making them a good
For comparison purposes, we can define an ideal sampling baseline for comparisons. We chose the Gnutella topology to
technique that uses an oracle to select a peer uniformly at examine how the sampling techniques would behave on a real
random from all peers that are currently present. While often system. Compared to a random graph, the Gnutella topology’s
impractical on real P2P networks, we can easily select peers degree distribution is significantly more skewed, and it has
uniformly at random in a simulator. There is no bias because significantly more clustering. In our ongoing work, we are
the selection is not correlated with any other peer properties. exploring the robustness of these sampling techniques over a
In summary, we consider the following techniques: wide variety of common types of graphs.
• Uniformly random (Oracle)
• Breadth-first search (BFS) A. Measuring Bias
• Random walk (RW) Uniformly random sampling (e.g., using an oracle) will
• Random stroll (RS) select each peer with equal probability. A poor sampling
• Random walk with degree correction (RWDC) technique will select some peers with much greater probability
• Random stroll with degree correction (RSDC) than others. In a simulator, we can compare other sampling
techniques to the ideal as follows. For some graph G(V, E),
III. E VALUATION we use each sampling technique4 to select a very large number
3 This process is not guaranteed to generate a connected graph, but will do

In Section II-B we defined several techniques for sampling so with high probability.
4 Since BFS does not allow duplicates, it cannot sample k · |V | peers in
peers from a P2P system. In this section, we use simulation
one execution. To simulate realistic usage, we initially perform one random
2 We would like to thank Christos Gkantsidis of Microsoft Research for walk to reach a random starting point, then perform a BFS to collect 1,000
suggesting this technique. samples. We reinitialize the search and repeat until we have k · |V | samples.
 100 100
Oracle/RWDC/RSDC Oracle/RWDC/RSDC
10 RW 10 RW
RS RS
1 1
CCDF

CCDF
BFS BFS
0.1 0.1
0.01 0.01
0.001 0.001
0 0.5 1 1.5 2 0 1 2 3 4 5
Correlation between random pairs of peers (%) Correlation between random pairs of peers (%)
(a) Random Graph (b) Gnutella
Fig. 2. Correlation of different sampling techniques; after collecting 1000 · |V | samples, the figures show for a pair of peers (A, B) what percentage of the
time (x-axis) did B appear whenever A appeared, as a CCDF over 1 million pairs of (A, B).
of samples, k · |V | (for example, k = 1000). We record topology. In addition to drawing this conclusion based visually
how many times each node is selected. The typical node on the presence or absence, respectively, of the bell-shaped
should be selected k times, with other nodes being selected curve centered around the mean (k = 1000), the data in
close to k times approximately following a normal distribution Table I provides further evidence. For random graphs, the skew
with variance k.5 A good sampling technique must produce a and kurtosis for these techniques is close to zero, suggesting
similar distribution close to selecting uniformly at random. normality. For Gnutella, the skew and kurtosis are quite large.
If the variance is higher, the technique is biased, unfairly The bias in these techniques is caused primarily by selecting
selecting some peers more than others. peers with higher degree, which explains why the results are
If a candidate technique produces a distribution similar to normally distributed for ordinary random graphs (which have
the ideal, this is evidence that the technique is unbiased. an approximately normally degree distribution) but not for the
Although it may be possible to deliberately construct a bad Gnutella topology (which does not).
sampling technique that would pass this test, in practice a Finally, we see that BFS behaves similarly to RW and RS
sampling technique with a systematic bias will have signif- for ordinary random graphs but not for the Gnutella topology.
icantly more variance than the ideal. Some techniques may Again, this is a result of the graphs’ degree distributions. These
not even produce a normal distribution, resulting in high skew techniques respond the same way to normally distributed node
and kurtosis (statistics which are very close to zero for samples degrees, but respond differently to a more skewed distribution.
from a normal distribution). Specifically, the RW and RS techniques are very prone to
The results for each of our candidate techniques are shown repeatedly selecting the few high-degree peers in Gnutella.
in Figure 1 using k = 1000. Additionally, Table I presents the Because BFS maintains a short history and will not select the
standard deviation, skew, and kurtosis. In cases where multiple same high-degree nodes during the same sampling session, it
lines were visually indistinguishable, we have plotted only one is somewhat more balanced, thus leading to a somewhat lower
of the lines for clarity. Specifically, RSDC performs just as skew and kurtosis (as shown in Table I(b)).
well as selecting peers uniformly at random using an oracle. In summary, BFS, RW, and RS exhibit significant bias.
On the other hand, without degree correction both random Degree correction for random walk and random stroll cause
walk (RW) and random stroll (RS) perform poorly, exhibiting these techniques to perform well, with RSDC exhibiting no
significantly higher standard deviation than the ideal. BFS also bias on either graph type.
exhibits significant bias. The bias of these techniques is also
evidenced by large standard deviations, as shown in Table I. B. Measuring Correlation
Comparing the data for ordinary random graphs (Fig. 1(a), A technique that has an equal probability of selecting each
Tab. I(a)) and the Gnutella topology (Fig. 1(b), Tab. I(b)) peer may still tend to select peers in groups. That is, the results
several things become apparent. First, we see that Oracle may be correlated. BFS is an obvious example of a technique
and RSDC perform the same on both types of topologies, with correlation; if a peer is selected, it becomes very likely its
evidence that RSDC is unbiased and not adversely affected by neighbors will also be selected in the same sampling session.
graph structure. Second, RWDC performs the same as Oracle Likewise, random stroll may exhibit correlation since it selects
and RSDC on the random graph but is slightly skewed on neighboring peers.
the Gnutella topology. We are unsure what introduces this One method of measuring correlation is to examine the
bias in RWDC, but not RSDC, and plan to study this in distribution of the percentage of sampling sessions in which
our ongoing work by looking for patterns across the over- node A is selected that also include node B, for all nodes A and
sampled and under-sampled peers from RWDC. Third, we B. We define a sampling sessions as a set of 1,000 consecutive
see that the results for RW, RS, and BFS appear normally samples. A good sampling technique will show a very low
distributed for ordinary random graphs but not for the Gnutella percentage for every possible pair. A sampling technique with
5 Based on the normal approximation of a binomial distribution with p = significant correlation will contain some pairs of peers that
1
|V |
and n = k|V | frequently appear together. If we plot the distribution as a
CCDF, this poor behavior will manifest as a long tail. How- and prove that a particular random algorithm can generate
ever, this method requires O(n2 ) memory, which is somewhat all graphs in the class. Cooper et al. [7] use this approach to
prohibitive for n = 161, 680. To overcome this difficulty, we show their algorithm for overlay construction generates graphs
randomly select a large subset (1 million) of the possible pairs with good properties. Our work is quite different; instead
of nodes and examine the correlation between only those pairs. of sampling a graph from a class of graphs our concern is
The results are shown in Figure 2. As expected, breadth- sampling peers from a particular graph.
first search (BFS) exhibits significantly more correlation (a Others use sampling to extract information from graphs,
longer tail) than any of the other techniques, followed by e.g., sampling a representative subgraph from a large, in-
RS. Interestingly, RSDC appears to perform just as well as tractable graph, while maintaining properties of the origi-
Oracle. The degree correction causes the random stroll to take nal [12], [13], [20]. Others use sampling as a component of
extra steps between selections, greatly decreasing the amount efficient, randomized algorithms [23]. However, these studies
of correlation. RWDC also performs well. rely on having knowledge of the graph in advance. Our prob-
Random walk without degree correction performs well over lem is quite different because we have imperfect information.
the ordinary random graphs but exhibits slight correlation over A closely related problem to ours is sampling Internet
the Gnutella topology. This is again a case where the degree routers by running traceroute from a few hosts to many ad-
distribution affects the performance of the sampling technique. dresses. Using simulation [14] and analysis [2], research shows
Over the Gnutella topology, the sampling process for RW is that traceroute samples can lead to the appearance of a power-
so heavily biased (as shown in the previous subsection) by law degree distribution regardless of the true distribution. Like
the degree distribution that it causes correlations to occur. In our study, they evaluate sampling when there is imperfect
other words, a sampling session often returns a similar set of information. Our study differs in its basic operation for graph-
high-degree peers. In the ordinary random graph, the bias is exploration. In their study, the basic operation is “What is the
not strong enough to cause significant correlation since none path to this address?”. In our study, the basic operation is
of the peers are of exceptional degree. “What are the neighbors of this peer?”.
Another closely related problem is selecting web pages uni-
C. Measuring Efficiency
formly at random from the set of all web pages [3], [9], [18].
Aside from bias, another important metric for evaluating Web pages naturally form a graph, with hyper-links forming
the usefulness of a sampling technique is its efficiency. One edges between pages. Unlike peer-to-peer networks, the graph
reason for sampling is to reduce the amount of work required is directed and only outgoing links are easily discovered. Much
to collect useful data. If the sampling technique is inefficient, of the work on sampling web pages therefore focuses on
it does not achieve that goal as well as an efficient technique. estimating the number of incoming links, to facilitate degree
Initially, any sampling technique begins with knowledge of a correction. Unlike peers in peer-to-peer systems, web pages are
small set of peers in the system. It iteratively queries peers for generally regarded as relatively stable, and temporal causes of
a list of their neighbors and returns a subset of these discovered sampling bias have not been considered in the web context.
peers as the samples. As the basic operation is the neighbors- Several properties of random walks have been extensively
query, we measure the efficiency as follows: studied analytically [15], such as the access time, cover time,
number of samples produced and mixing time. While these properties have many useful
efficiency =
number of peers queried applications,to our knowledge the application of random walks
A technique that is 100% efficient returns a sample set as a method of selecting nodes uniformly at random from
containing every peer that it queried. The efficiency does not an unknown graph has not been well studied. Additionally,
reveal anything about the quality of the samples; it is simply analytical techniques are only useful for examining classes of
a measure of how easily the samples are collected. graphs which can be expressed mathematically, while in our
The efficiencies of the various techniques we examine are work we also examine a graph (the Gnutella topology) that
shown in the bottom row of Table I. BFS and RS are both very was captured empirically.
close to 100% efficient. However, as the previous subsections A number of papers [6], [8], [16] have made use of random
have shown, they are also heavily biased. RW, in addition walks as a basis for searching unstructured P2P networks.
to being biased, is only 8% efficient. RWDC and RSDC are However, searching simply requires locating a certain piece
unbiased but are only 2% and 4% efficient, respectively. Note of data anywhere along the walk, and is not particularly con-
that the efficiency of the degree correction techniques depends cerned if some nodes are preferred over others. Gkantsidis et
on the degree distribution of the graph. They will be more al. additionally use random walks as a component of their
efficient on low-degree graphs and less efficient on high-degree overlay-construction algorithm.
graphs.
IV. R ELATED W ORK V. C ONCLUSIONS AND F UTURE W ORK
Sampling from a class of graphs has been well studied in In this paper we have explored several techniques for
the graph theory literature [5], [11], where they define a class sampling from P2P systems. One of our contributions is to
of graphs sharing some property (e.g., degree distribution) show that unbiased sampling must allow the same peer to
be selected multiple times to avoid bias correlated with peer [17] J. Pouwelse, P. Garbacki, D. Epema, and H. Sips. The Bittorrent P2P
sessions lengths. File-sharing System: Measurements and Analysis. In International
Workshop on Peer-to-Peer Systems (IPTPS), 2005.
We simulated each technique over ordinary random graphs [18] P. Rusmevichientong, D. M. Pennock, S. Lawrence, and C. L. Giles.
as well as a real Gnutella topology and evaluated how much Methods for Sampling Pages Uniformly from the World Wide Web. In
bias and correlation they introduce as well as their efficiency. AAAI Fall Symposium on Using Uncertainty Within Computation,
2001.
We found that the commonly used BFS technique, while effi- [19] S. Saroiu, P. K. Gummadi, and S. D. Gribble. Measuring and
cient, introduces significant sampling bias. Conducting random Analyzing the Characteristics of Napster and Gnutella Hosts.
walks is also significantly biased and additionally is inefficient. Multimedia Systems Journal, 9(2), 2003.
[20] M. P. H. Stumpf, C. Wiuf, and R. M. May. Subnets of scale-free
The random stroll technique corrects the inefficiency, but networks are not scale-free: Sampling properties of networks.
remains significantly biased. Each of these techniques are Proceedings of the National Academy of Sciences, 102(12), 2005.
biased due to the influence of the degree distribution. We [21] D. Stutzbach and R. Rejaie. Capturing Accurate Snapshots of the
Gnutella Network. In Global Internet Symposium, 2005.
describe a “degree correction” modification to the random [22] D. Stutzbach, R. Rejaie, and S. Sen. Characterizing Unstructured
walk and random stroll techniques that corrects the bias, Overlay Topologies in Modern P2P File-Sharing Systems. In Internet
resulting in samples that appear just as accurate as using an Measurement Conference, 2005.
[23] A. A. Tsay, W. S. Lovejoy, and D. R. Karger. Random Sampling in
oracle. However, there is a significant decrease in efficiency Cut, Flow, and Network Design Problems. Mathematics of Operations
when using these techniques. Research, 24(2), 1999.
In our ongoing work, we are extending our study to include [24] S. Zhao, D. Stutzbach, and R. Rejaie. Characterizing Files in the
Modern Gnutella Network: A Measurement Study. In Multimedia
additional types of random graphs, such as power-law random Computing and Networking, 2006.
graphs and small-world graphs. By comparing and contrasting
the performance of different techniques in different settings,
we can gain a better understanding of the most efficient
techniques to yield unbiased samples. Additionally, we are
exploring techniques for estimating global properties, such as
the number of peers in a P2P system or the diameter of an
overlay network by exploring only a fraction of the graph.
R EFERENCES
[1] [Link]. [Link] 2005.
[2] D. Achlioptas, A. Clauset, D. Kempe, and C. Moore. On the Bias of
Traceroute Sampling; or, Power-law Degree Distributions in Regular
Graphs. In Symposium on Theory of Computing, 2005.
[3] Z. Bar-Yossef, A. Berg, S. Chien, J. Fakcharoenphol, and D. Weitz.
Approximating Aggregate Queries about Web Pages via Random
Walks. In International Conference on Very Large Databases, 2000.
[4] R. Bhagwan, S. Savage, and G. Voelker. Understanding Availability.
In International Workshop on Peer-to-Peer Systems, 2003.
[5] B. Bollobás. A probabilistic proof of an asymptotic formula for the
number of labelled regular graphs. European Journal of
Combinatorics, 1, 1980.
[6] Y. Chawathe, S. Ratnasamy, and L. Breslau. Making Gnutella-like P2P
Systems Scalable. In SIGCOMM, 2003.
[7] C. Cooper, M. Dyer, and C. Greenhill. Sampling regular graphs and a
peer-to-peer network. In Symposium on Discrete Algorithms, 2005.
[8] C. Gkantsidis, M. Mihail, and A. Saberi. Random Walks in
Peer-to-Peer Networks. In INFOCOM, 2004.
[9] M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork. On
Near-Uniform URL Sampling. In International World Wide Web
Conference, 2001.
[10] M. Izal, G. Urvoy-Keller, E. W. Biersack, P. A. Felber, A. A. Hamra,
and L. Garces-Erice. Dissecting BitTorrent: Five Months in a Torrent’s
Lifetime. In PAM, 2004.
[11] M. Jerrum and A. Sinclair. Fast uniform generation of regular graphs.
Theoretical Computer Science, 73, 1990.
[12] V. Krishnamurthy, M. Faloutsos, M. Chrobak, L. Lao, J.-H. Cui, and
A. G. Percus. Reducing Large Internet Topologies for Faster
Simulations. In IFIP Networking, 2005.
[13] V. Krishnamurthy, J. Sun, M. Faloutsos, and S. Tauro. Sampling
Internet Topologies: How Small Can We Go? In International
Conference on Internet Computing, 2003.
[14] A. Lakhina, J. W. Byers, M. Crovella, and P. Xie. Sampling Biases in
IP Topology Measurements. In INFOCOM, 2003.
[15] L. Lovász. Random walks on graphs: A survey. Combinatorics: Paul
Erdös is Eighty, 2, 1993.
[16] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and
Replication in Unstructured Peer-to-Peer Networks. In International
Conference on Supercomputing, 2002.