A Comparison of Techniques for Sampling Web Pages

Eda Baykan, Monika Rauch Henzinger, Stefan F. Keller, Sebastian De Castelberg, Markus Kinzler

TL;DR

This paper directly compares three prominent web page sampling algorithms (A, B, and C) based on random walks, addressing the challenge of obtaining unbiased web samples for understanding its properties. The study reveals that Algorithm C, while biased towards high PageRank and outdegree pages, offers a more uniform distribution of nodes per host, whereas Algorithms A and B suffer from a significant "getting stuck" problem on highly connected hosts.

What Problem Does This Paper Address?

The World Wide Web is a vast and dynamic information source, yet understanding its fundamental characteristics – like the proportion of pages in a specific language, topic, or domain – is incredibly difficult. Exhaustively crawling the entire web is infeasible due to its sheer size and constant evolution. Therefore, researchers rely on sampling techniques to gather representative data. While several random walk-based algorithms exist for web sampling, they have typically been evaluated in isolation. This paper aims to bridge that gap by directly comparing three such algorithms (A, B, and C) under identical conditions to understand their strengths, weaknesses, and biases.

Methods

The paper focuses on three random walk-based sampling algorithms:

  • Algorithm A: Based on a random walk on an undirected, aperiodic, and irreducible graph. It aims for a stationary distribution proportional to node degree. To correct for this bias, it uses subsampling inversely proportional to node degree.
  • Algorithm B: Similar to Algorithm A but designed for a regular graph (achieved by adding self-loops). It theoretically converges to a uniform distribution. Subsampling is also done inversely proportional to node degree.
  • Algorithm C: Mimics the PageRank random walk, aiming for a stationary distribution proportional to PageRank values. It incorporates random resets to avoid getting stuck. Subsampling is done inversely proportional to PageRank values.

The authors implemented the "walk phase" of these algorithms and then experimented with different "subsampling phases" (sampling states vs. steps, and from the last half vs. last quarter of the walk). They performed extensive experiments on the live web, collecting data and analyzing various metrics.

Datasets

The experiments were conducted on the live World Wide Web. The authors did not create or use a specific benchmark dataset but rather performed their crawls under controlled conditions.

Key Insights and Ideas

  • "Getting Stuck" is a Major Issue: Algorithms A and B suffer from a significant problem where the random walk gets "stuck" on highly interconnected hosts with few outgoing links. This leads to a highly unbalanced distribution of nodes per host in the samples.
  • Algorithm C's Trade-offs: While Algorithm C effectively avoids the "getting stuck" problem through random resets, it exhibits a clear bias towards high PageRank and high outdegree web pages.
  • Subsampling States vs. Steps: Subsampling states (individual web pages visited) generally leads to less biased samples, particularly concerning the distribution of nodes per host, compared to subsampling steps (transitions between pages).
  • Subsampling Window (Last Half vs. Last Quarter): The choice of subsampling from the last half or last quarter of the walk steps did not significantly impact the results, suggesting that the starting node bias is relatively small after a sufficiently long walk.
  • PageRank as a Proxy: Using "visit ratio" (the frequency of visiting a node) as a substitute for PageRank in subsampling for Algorithm C yielded results similar to using actual PageRank values, suggesting its viability.

Key Results

  • Nodes per Host: C Samples showed a relatively uniform distribution of hosts, with about 9,500 unique hosts for 10,000 nodes. In contrast, A and B Samples had significantly fewer unique hosts, with over 30% of nodes belonging to just three hosts in some cases.
  • PageRank Bias: Walk C successfully visited high PageRank nodes more frequently, as evidenced by the high PageRank values of the most visited nodes. Walk AB showed no such bias.
  • Outdegree Distribution: All samples showed some bias towards high outdegree nodes, deviating from the expected power-law exponent of 2.72. C Samples had a particularly high average outdegree.
  • Top Level Domain (TLD) Distribution: A Samples, B Samples, and C Samples generally agreed on the dominance of ".com" domains (44-65%), with ".net" and ".org" following (4-9%).
  • Document Content Length: B Samples (subsampling states) and C Samples showed similar monotonically decreasing distributions of content length. Spikes in A and B Samples (subsampling steps) were attributed to uneven host distributions.

Limitations and Future Work

  • Algorithm C's Bias: The paper acknowledges that Algorithm C's bias towards high PageRank and outdegree pages is difficult to correct.
  • "Getting Stuck" Correction: While the authors attempted to mitigate the "getting stuck" problem by stopping walks that couldn't leave a host, they suggest that a more robust solution might involve periodic random resets, similar to Algorithm C, or as proposed in other works on topic distribution.
  • Further Investigation Needed: The paper notes that further investigation is required to understand the differing behavior of state vs. step subsampling for TLD distribution.
  • Comparison with Previous Work: The paper highlights differences in host distributions compared to a 1999 study, attributing this to the significant changes in the web over time.

Summary updated

Abstract

As the World Wide Web is growing rapidly, it is getting increasingly challenging to gather representative information about it. Instead of crawling the web exhaustively one has to resort to other techniques like sampling to determine the properties of the web. A uniform random sample of the web would be useful to determine the percentage of web pages in a specific language, on a topic or in a top level domain. Unfortunately, no approach has been shown to sample the web pages in an unbiased way. Three promising web sampling algorithms are based on random walks. They each have been evaluated individually, but making a comparison on different data sets is not possible. We directly compare these algorithms in this paper. We performed three random walks on the web under the same conditions and analyzed their outcomes in detail. We discuss the strengths and the weaknesses of each algorithm and propose improvements based on experimental results.
BibTeX
@inproceedings{baykan2009comparison,
  author = {Eda Baykan and Monika Rauch Henzinger and Stefan F. Keller and Sebastian De Castelberg and Markus Kinzler},
  title = {{A Comparison of Techniques for Sampling Web Pages}},
  booktitle = {STACS},
  year = {2009},
  url = {https://openreview.net/forum?id=neeYNOJa16},
}

Loading related content...

Figure