USDSG: Breaking the Bias in Directed Social Graph Sampling

TL;DR

Measuring massive directed networks like Twitter is notoriously difficult because standard crawling methods disproportionately favor "celebrity" nodes. This paper proposes USDSG, the first unbiased sampling method for directed graphs. By treating directed edges as bidirectional during traversal and applying a corrected Metropolis-Hastings Random Walk (MHRW), the authors achieve a near-perfect uniform sample with less than 10% error compared to ground truth.

The "Dead End" Problem in Directed Networks

In undirected networks like Facebook (friendship), links are reciprocal. However, in directed networks like Twitter (following), the topology is often "broken." Prior works used MHRW to successfully sample undirected graphs, but directed graphs introduce a fatal flaw: Sink Nodes.

If a random walker enters a node with an out-degree of 0, the walk terminates, making it impossible to explore the graph further or reach a steady-state distribution. Furthermore, simply following out-links causes the sample to converge toward high-degree "hubs," skewing any statistical analysis of the network's true properties.

Methodology: USDSG

The core insight of USDSG is a two-step transformation:

1. Topology Relaxation: Treat all unidirectional edges as bidirectional. This ensures the graph is strongly connected, allowing the walker to reach any node from an initial seed and avoiding the "sink node" trap.
2. Corrective Proposal Function: In an undirected graph, MHRW uses node degree $k_v$ to rebalance the walk. USDSG adapts this by using the total number of connected neighbors (regardless of original direction) as the proposal function $Q(v)$.

The Algorithm Logic

During the walk, a transition from node $v$ to $w$ is accepted with a probability $\alpha$: $\alpha =\min \left(1,\frac{Q(v)}{Q(w)}\right)$ This specific ratio cancels out the natural bias that favors high-degree nodes, effectively "slowing down" the walker when it hits dense clusters and forcing it to spend more time in sparse areas of the graph.

Note: The sampling framework leverages MCMC to achieve convergence to a uniform distribution.

Experimental Results

The authors validated USDSG using three large-scale datasets from the Stanford Large Network Dataset Collection (SNAP): soc-Epinions1, soc-Slashdot0811, and soc-Slashdot0922.

Key Findings:

• Near-Zero Bias: The average in-degree and out-degree of the USDSG samples were compared against a theoretical Uniform (UNI) sample. The error rates were remarkably low, particularly on the Slashdot0902 dataset (0.67% error for in-degree).
• Distribution Accuracy: Beyond just averages, the Cumulative Distribution Functions (CDFs) of the sampled degrees perfectly overlapped with the UNI ground truth.

Table 1: Comparison of Average Degree showing USDSG's performance against UNI.

Critical Insight & Conclusion

The brilliance of USDSG lies in its simplicity. By recognizing that edge direction is a constraint on traversal but not a requirement for mathematical convergence, the authors successfully ported MCMC techniques to a more complex graph domain.

Limitations: The method assumes you can discover in-coming edges (who follows a user) as easily as out-going edges. In many restricted APIs, finding "followers" is significantly harder than finding "following," which might limit the practical application of the bidirectional traversal in certain proprietary environments.

Future Outlook: As social networks grow into the billions, uniform sampling remains the only way to perform cost-effective measurement. USDSG provides the theoretical foundation for building more representative datasets for sociology and network science.