PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Unbiased BFS Sampling

Maciej Kurant, Athina Markopoulou, Patrick Thiran

arXiv:1102.4599v1cs.SIcs.NIstat.ME

TL;DR

Incomplete BFS sampling overrepresents high-degree nodes, complicating topology and node-statistic estimates despite BFS’s advantage of producing plausible sampled graphs. The paper derives this bias in RG(p_k), proposes a practical correction, and finds it more effective than high-variance arbitrary-topology alternatives.

  • Problem

    Incomplete BFS is biased toward high-degree nodes, threatening measurements even though BFS samples can support topological analysis as plausible graphs.

  • Method

    The paper derives q_k as a function of coverage fraction f in RG(p_k), then uses the analysis to correct node statistics from BFS samples.

  • Results

    The RG(p_k)-based correction performs well across Internet topologies and Facebook and Orkut BFS samples, while arbitrary-topology estimators have large variance.

  • Takeaways & Limitations

    For incomplete BFS, the RG(p_k)-based procedure provides a practical way to quantify and correct degree bias in node statistics.

Abstract

from arXiv · show

Breadth First Search (BFS) is a widely used approach for sampling large unknown Internet topologies. Its main advantage over random walks and other exploration techniques is that a BFS sample is a plausible graph on its own, and therefore we can study its topological characteristics. However, it has been empirically observed that incomplete BFS is biased toward high-degree nodes, which may strongly affect the measurements. In this paper, we first analytically quantify the degree bias of BFS sampling. In particular, we calculate the node degree distribution expected to be observed by BFS as a function of the fraction f of covered nodes, in a random graph RG(pk) with an arbitrary degree distribution pk. We also show that, for RG(pk), all commonly used graph traversal techniques (BFS, DFS, Forest Fire, Snowball Sampling, RDS) suffer from exactly the same bias. Next, based on our theoretical analysis, we propose a practical BFS-bias correction procedure. It takes as input a collected BFS sample together with its fraction f. Even though RG(pk) does not capture many graph properties common in real-life graphs (such as assortativity), our RG(pk)-based correction technique performs well on a broad range of Internet topologies and on two large BFS samples of Facebook and Orkut networks. Finally, we consider and evaluate a family of alternative correction procedures, and demonstrate that, although they are unbiased for an arbitrary topology, their large variance makes them far less effective than the RG(pk)-based technique.

I. INTRODUCTION

The paper analyzes why incomplete BFS samples overrepresent high-degree nodes and develops correction methods grounded in a random-graph model. It evaluates those methods against real Internet and social-network topologies while stating clear scope boundaries.

  • Motivation: BFS is attractive because its samples remain plausible graphs for studying topological characteristics, unlike random-walk samples.This advantage depends on the sample being representative of the full graph.
  • Problem: Incomplete BFS can strongly overestimate node degree, as Facebook sampling found an average degree of 324 versus a real value of 94.The paper reports this as an overestimate of about 250%.
  • Contributions: The paper precisely derives BFS’s observed degree distribution q_k as a function of coverage fraction f for arbitrary degree distributions in RG(p_k).The authors describe this as the first analytical result characterizing BFS sampling bias.
  • Contributions: A practical correction procedure estimates node statistics from a BFS sample and its covered fraction f, performing well across Internet topologies and Facebook and Orkut samples.A ready-to-use Python implementation is publicly available.
  • Contributions: Alternative corrections that are unbiased for arbitrary topologies have large variance and are less effective than the RG(p_k)-based technique.The comparison favors the model-based method in practical effectiveness.
  • Scope: The theoretical results hold strictly for RG(p_k), while dynamically varying and interaction graphs are outside the paper’s scope.The authors report that the results nevertheless apply relatively well to a broad range of real-life topologies.

III. GRAPH EXPLORATION TECHNIQUES

The paper distinguishes random walks from graph traversals and explains how their transition rules determine revisitation, exploration order, and sampling behavior. MHRW modifies random-walk transitions to remove degree bias, while traversals terminate after partial coverage in typical sampling.

  • Exploration categories: Random walks may revisit nodes, whereas graph traversals visit each node at most once and eventually cover all nodes in a connected graph.Sampling with traversals usually stops at a fraction f < 1 of the graph.
  • Random Walk: Random Walk chooses each next node uniformly among the current node’s neighbors, creating a linear bias toward high-degree nodes.The walk begins from a seed node and repeatedly selects a neighbor.
  • MHRW: MHRW sometimes self-loops instead of moving to a proposed neighbor, with the probability determined by the degrees of the two nodes.This reduces transitions to high-degree nodes and eliminates RW’s degree bias.
  • Graph traversals: BFS selects the earliest discovered but unvisited node, so it discovers nodes closest to the seed first.This is the defining queue discipline for BFS.

1) Breadth First Search (BFS):

The paper places BFS within a family of traversal and sampling methods, then analyzes degree bias in RG(p_k) by studying the observed distribution q_k. The model preserves arbitrary degree distributions while omitting other graph properties.

  • Depth First Search (DFS): DFS selects the latest discovered but unvisited node, exploring nodes farthest from the seed in hop distance first.This contrasts with BFS’s earliest-first exploration order.
  • Forest Fire: Forest Fire randomizes BFS by independently exploring each neighbor with success probability p, and it can die out before covering the graph.The process reduces to BFS when p = 1.
  • Snowball Sampling and RDS: Snowball Sampling selects exactly n neighbors randomly at each node, while RDS applies a correction procedure to Snowball Sampling for hidden populations.RDS is presented as a close relative of BFS-style exploration.
  • Random graph model: The degree distribution p_k is the fraction of nodes with degree k, and RG(p_k) models graphs with an arbitrary such distribution.The model is generated by assigning stubs according to node degrees and randomly matching them.
  • BFS bias: The analysis studies the observed distribution q_k, which generally differs from p_k and has a higher average degree in incomplete samples.The paper derives q_k as a function of p_k and sampling coverage.

2) Metropolis Hastings Random Walk (MHRW):

MHRW provides an unbiased reference by using a uniform stationary distribution, while the paper analyzes traversal sampling through a stub-level process that avoids revisits and supports multiple scheduling disciplines.

  • MHRW: MHRW has a uniform stationary distribution and therefore estimates the true mean.This makes it a reference method for comparison with biased random walks and traversals.
  • Analytical setup: Unlike random walks, traversals create dependencies across iterations because they cannot revisit nodes.These dependencies make their analysis substantially more difficult than Markov-chain analysis of walks.
  • Graph traversals: The paper analyzes graph traversals with a stub-level algorithm that collects nodes without replacement using a queue of discovered, unprocessed stubs.Each newly discovered node contributes its remaining stubs to the queue.
  • Traversal variants: FIFO, LIFO, and randomized-loss scheduling of the queue implement BFS, DFS, and Forest Fire, respectively.The algorithm removes reverse-traversal stubs to prevent edge tracebacks.

2) Discovery on-the-fly:

The paper replaces explicit random stub matching with an equivalent on-the-fly construction, making BFS dependencies analytically tractable. This yields equations describing BFS degree bias under RG(pk).

  • Discovery on-the-fly:: On-the-fly stub selection is equivalent to constructing the configuration-model graph by deferred decisions.At each step, an unmatched stub is selected uniformly without first generating the entire graph.
  • Discovery on-the-fly:: Each stub receives an independent uniform index in [0, 1], determining when it is processed during exploration.The resulting ordering supports the BFS execution illustrated in Fig. 2.
  • Discovery on-the-fly:: A degree-k vertex is discovered before time t with probability 1−(1−t)^k.This follows because all k stub indices must exceed t for the vertex to remain undiscovered.
  • Discovery on-the-fly:: The parameter t is converted numerically into the covered-node fraction f, yielding the expected sampled degree distribution as a function of f.The mapping is well defined because the expected uncovered fraction decreases continuously with t.
  • Discovery on-the-fly:: Equations (11) and (12) describe BFS sampling bias under RG(pk), while the sampled node sequence is independent of queue-management order.Therefore, the same bias applies to common traversal techniques under this random-graph model.

5) Equivalence of traversal techniques under RW(pk):

Under RG(pk), traversal samples behave like degree-weighted sampling without replacement. Their average sampled degree declines as coverage grows, and short traversals are especially biased.

  • Equivalence of traversal techniques under RW(pk):: At every step, an undiscovered vertex is selected with probability proportional to its degree.This establishes equivalence between traversal sampling and degree-weighted sampling without replacement.
  • Equivalence of traversal techniques under RW(pk):: For f→0, every traversal technique is equivalent to random-walk sampling.The approximation follows from 1−(1−t)^k ≃ kt at the beginning of exploration.
  • Equivalence of traversal techniques under RW(pk):: The expected sampled average degree ⟨qBFS_k⟩ decreases monotonically with the covered fraction f.Later selections are less concentrated on high-degree nodes than earlier selections.
  • Equivalence of traversal techniques under RW(pk):: Many short traversals are more biased than one long traversal with the same total number of samples.This follows from the decreasing sampled average degree over successive selections.
  • Equivalence of traversal techniques under RW(pk):: If RG(pk) is disconnected, exploration remains confined to the component containing its starting node.The process stops when that component is covered.

A. Random walks (baseline)

The paper contrasts traversal correction with established random-walk estimators and extends correction to arbitrary node properties. Its BFS estimator uses inclusion probabilities and requires the covered fraction.

  • A. Random walks (baseline): Random-walk sampling uses the Hansen–Hurwitz estimator because node-selection probability is proportional to degree.The estimator is unbiased under sampling with replacement.
  • A. Random walks (baseline): For BFS and other traversals, the paper applies the Horvitz–Thompson estimator to inclusion probabilities under sampling without replacement.The inclusion probability is derived from the BFS degree-bias equations.
  • A. Random walks (baseline): The iterative procedure requires the real covered fraction f_real, or equivalently the graph size |V|, to resolve the dependence on the unknown degree distribution.It repeatedly updates the estimated distribution until the inferred fraction approaches f_real.
  • A. Random walks (baseline): The correction estimates the mean of an arbitrary node function x(v), with the original degree distribution as a special case.It also yields estimates of the mean degree and degree distribution.
  • A. Random walks (baseline): The practical estimator requires only the sample, node values and degrees within that sample, and the fraction of sampled nodes.A ready-to-use Python implementation is publicly available.

C. Alternative approach

The evaluation compares analytical predictions with simulations on random graphs and examines how assortativity changes traversal bias. It also contrasts the RG(pk)-based correction with arbitrary-topology alternatives.

  • C. Alternative approach: Alternative correction procedures are unbiased for arbitrary topologies but have large variance, making them less effective than the RG(pk)-based technique.This is the principal trade-off motivating the paper’s preferred correction approach.
  • C. Alternative approach: Theory and simulation show an almost perfect match, and the correction nearly removes the sampled degree-distribution bias.All traversal techniques follow the same curve, which decreases with coverage fraction.
  • C. Alternative approach: Fig. 3 compares sampled average degree across coverage fractions and compares real, expected, and corrected degree distributions.The experiments average results over 1000 configuration-model graphs with 10000 nodes and a fixed heavy-tailed degree distribution.
  • C. Alternative approach: Fig. 4 varies assortativity by degree-preserving edge rewiring and focuses on f∈[0,0.1].The left and right panels represent positive and negative assortativity, respectively.
  • C. Alternative approach: Positive assortativity strengthens early traversal bias, whereas negative assortativity has the opposite effect.Forest Fire is reported as especially affected under positive assortativity.

B. Real-life fully known topologies

The RG(pk)-based correction performs well on fully known real-life Internet topologies despite omitting properties such as assortativity. Its BFS estimator generally corrects the sampled average degree, while the RW estimator underestimates it at larger coverage fractions.

  • RG(pk) omits real-life properties such as assortativity, yet its correction technique performs well across many Internet topologies.
  • The BFS estimator corrects the sampled average node degree surprisingly well on the evaluated topologies.
  • Differences from the real-life graphs appear mainly as f approaches 0 and for specific topologies.
  • The RW estimator coincides with the BFS estimator as f approaches 0 but significantly underestimates average degree for larger f.
  • The Facebook evaluation used BFS samples with 28 random seeds and with one seed, alongside random-walk and other measurements.
  • Because both Facebook BFS samples covered less than 1% of the network, their sampled average degree showed almost no decline and BFS and RW estimates were nearly identical.

2) Orkut:

The Orkut BFS sample covered 11.3% of the network, and its sampled average degree did not decline monotonically. Despite this, the BFS estimator approximated the average degree relatively well, while arbitrary-topology estimators traded unbiasedness for high variance.

  • 2) Orkut:: The sampled Orkut average degree did not decrease monotonically with f, possibly because the run began in a sparsely connected region.
  • 2) Orkut:: The BFS estimator approximated Orkut’s average node degree relatively well despite the absence of a definitive ground-truth value.
  • 2) Orkut:: The RG(pk)-based correction is unbiased for RG(pk) graphs but can retain limited bias on arbitrary real-life graphs.
  • 2) Orkut:: Arbitrary-topology estimators are unbiased on arbitrary graphs but have very large variance, making them less effective in practice than RG(pk)-based estimators.

C. Practical requirements

Arbitrary-topology estimators are unbiased, but practical use requires that their needed node values be observable from the BFS sample and that their variance remain small.

  • The estimator is unbiased for any choice of Q(w), regardless of the sampling method.
  • Feasibility requires that the values needed by the estimator be available from the sampled nodes, with Q(U) ⊂ S(U) as a necessary condition.
  • A practical estimator should also have small variance.
  • The paper analyzes i-stage BFS samples defined as the vertices within i hops of the starting node.
  • Using only the first sampled node is feasible but produces huge variance.
  • The half-radius estimator uses only nodes from the first i/2 BFS stages and is feasible.

4) Half-radius extended:

The arbitrary-topology estimators are unbiased but have high variance, whereas the RG(pk)-based estimator is more concentrated and performs better in the reported comparisons. The paper therefore favors RG(pk)-based correction for local node statistics, while noting limits for non-local properties and model scope.

  • Evaluation: Unbiased arbitrary-topology estimators have much larger RMSE than RG(pk)-based estimators.The simulations average results over 1000 BFS samples, with RMSE capturing both estimator bias and variance.
  • Evaluation: Large variance arises because most sampled-node values are unusable and feasible query-set sizes differ substantially across nodes.These effects create differences among individual total estimates.
  • Evaluation: The arbitrary-topology estimator is unbiased but imprecise, whereas the potentially slightly biased RG(pk)-based estimator is more concentrated.The comparison is framed as an accuracy-versus-precision trade-off.
  • Practical implications: Random Walk is recommended for node properties because it is simple, unbiased for arbitrary topologies with correction, and typically more efficient than MHRW.This recommendation concerns local node-property sampling rather than non-local graph properties.
  • Practical implications: BFS remains attractive for non-local properties because it provides a plausible graph view, but its results require careful interpretation unless a community is fully covered.The paper notes that fully exhausting a sufficiently small community can make the BFS sample representative of that community.
Loading 1102.4599v1…