Towards Unbiased BFS Sampling

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify and correct the degree bias of BFS. First, we...

Full description

Saved in:
Bibliographic Details
Published in:IEEE journal on selected areas in communications 2011-10, Vol.29 (9), p.1799-1809
Main Authors: Kurant, M., Markopoulou, A., Thiran, P.
Format: Article
Language:English
Subjects:
Bias
Breadth-First-Search (BFS)
Equations
estimation
Facebook
Fires
Graphs
Indexes
Internet
Mathematical model
Mathematical models
network topology
Networks
online social networks
Peer to peer computing
Sampling
sampling methods
Scattering
Searching
Studies
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!