Benefits of Bias: Towards Better Characterization of Network Sampling

Motivation

• Sampling addresses networks that are too large, decentralized, or inaccessible to analyze in full by using subsets of nodes and links.The paper describes sampling as inference from small network subsets.Source: §1 · p. 1

Contribution

• The study connects specific sampling biases to structural representativeness so those biases can be leveraged in practical applications.The authors frame their work as a comprehensive examination of bias as a potentially useful asset, contrasting with literature focused on avoiding bias.Source: §1 · p. 1

Summary of Findings

• Expansion bias pushes sampling toward new, undiscovered clusters and wider portions of a network, while BFS performs poorly at discovery and hub accumulation.The authors also report that selecting highly connected nodes from the sampled set can approximate direct high-degree sampling and find such nodes faster than most other methods.Source: §1 · p. 2

Applications

• The paper identifies disease outbreak detection and market research as applications for exploiting sampling biases.It also notes earlier work using structurally representative samples to infer network protocol performance.Source: §1 · pp. 1–2

Representative Subgraph Sampling

• Representative subgraph sampling often seeks a universal sample, whereas this work studies biases in specific strategies because no single strategy may suit every application.Classical network sampling instead focuses largely on unbiased estimates of node attributes, while this work targets properties of the network itself.Source: §2 · p. 2

Studies on Sampling Bias

• Earlier studies documented negative effects of sampling bias, while this work examines advantages of certain biases and their use in network analysis.Examples include random sampling failing to preserve scale-free structure and traceroute sampling exhibiting the converse.Source: §2 · p. 2

Unbiased Sampling

• Modified random-walk methods for inaccessible nodes have supported frequency estimation, but preliminary tests found them less effective for structural and functional inference.The paper therefore focuses on other strategies, including representative-subgraph approaches.Source: §2 · p. 2

Property Testing and Other Areas

• The paper relates network sampling to graph property testing, decentralized search, and Web crawling, which also make decisions from partial network views.It notes that some studied strategies are graph-search algorithms, connecting findings to those areas.Source: §2 · p. 2

3.1 Notations and Definitions

• A network is G = (V, E), a graph with vertex set V and edge set E; a sample S is a subset of V.The neighborhood N(S) contains nodes outside S that connect to at least one node in S, and G_S is the induced subgraph on S.Source: §3.1 · p. 2

3.2 Datasets

• The study covers 12 undirected, unweighted networks from domains including power grids, voting, trust, citations, email, coauthorship, P2P, social media, and product co-purchasing.The authors chose diverse domains to assess strategies across varying network topologies.Source: §3.2 · p. 3

Link-Trace Sampling

• Link-trace sampling starts from a seed and repeatedly adds a node from the current neighborhood until the sample reaches its target size.It can operate without complete access to the network, provided neighbors of visited nodes can be obtained.Source: §4 · p. 3

Sampling Strategies

• BFS, DFS, random walk, and forest fire differ in how they traverse available neighbors, with forest fire probabilistically exploring neighbors in a BFS-like process.Forest fire uses p = 0.7 in this study; at p = 1 it is identical to BFS.Source: §4 · p. 3
• Degree sampling selects the highest-degree available node, while SEC uses its links to the current sample as an approximation of its full degree.Degree sampling requires knowledge of candidate nodes' neighbors; SEC avoids that requirement by counting links from the sample.Source: §4 · p. 3
• Expansion sampling greedily seeks a sample with high expansion, and like degree sampling it uses knowledge of the neighborhoods of candidate nodes.The paper investigates how this expansion bias affects properties of constructed samples.Source: §4 · pp. 3–4

• The study evaluates representativeness across Degree, Clustering, and Reach, choosing measures viewed as potentially useful for real applications.Source: §5 · p. 4
• Each strategy is tested with 100 randomly seeded samples, and the measures are averaged as sample size grows.Source: §5 · p. 4
• Because of space limits and the number of networks, only two illustrative datasets are shown per measure; full results are in supplementary material.Source: §5 · p. 4

5.1 Degree

• Degree, or the number of neighbors a node has, is treated as a fundamental network property with potential relevance to applications.Source: §5.1 · p. 4

5.1.1 Measures

• DistSim measures degree-distribution agreement using one minus the K-S distance, while Hubs tracks the proportion of top-K nodes accumulated as the sample grows.The tests use K = 100.Source: §5.1.1 · p. 4

5.1.2 Results

• DS and SEC find most top-100 hubs below 1% sample size in some cases, while BFS and FFS need over 10%; no strategy leads both metrics.Source: Figure 1 · p. 4, §5.1.2 · p. 4

5.2 Clustering

• Many real-world networks, including social networks, exhibit more clustering than expected at random.Source: §5.2 · p. 4

5.2.1 Measures

• The local coefficient captures links among a node’s neighbors, while the global coefficient is the number of closed triplets divided by connected triples.Source: §5.2.1 · p. 5

5.2.2 Results

• Clustering estimates are less consistent overall; DFS and RW fare relatively better, while many strategies initially overestimate clustering before estimates decline.The authors relate the early overestimate to clustered nodes being encountered earlier than peripheral nodes.Source: §5.2.2 · p. 5

5.3 Network Reach

• Network reach is proposed as a measure of how far a sample spreads across the network.Source: §5.3 · p. 5

5.3.1 Measures

• Community reach is the fraction of detected communities represented in the sample; DQ is the share of nodes in the sample or its one-hop neighborhood.Source: §5.3.1 · pp. 5–6
• The usual 1−1/e greedy coverage guarantee does not hold for link-trace sampling because choices are restricted to the current neighborhood.Source: §5.3.1 · p. 6

5.3.2 Results

• XS performs best on all three network-reach measures; BFS performs poorly on all three, while SEC is among the least effective at reaching different communities.Source: §5.3.2 · p. 6
• XS’s expansion bias is linked to reaching new communities, while DS can miss network coverage when high-degree nodes’ neighborhoods overlap.XS can discover more of the network in the same number of steps, sometimes by sampling comparatively lower-degree nodes.Source: §5.3.2 · p. 6

5.4 A Note on Seed Sensitivity

• Across measures and datasets, XS, SEC, and DS show the least seed sensitivity and variability as sample size grows.The authors describe these methods as having the most explicit biases.Source: §5.4 · p. 6
• BFS, DFS, FFS, and RW exhibit the greatest seed sensitivity and variability.Source: §5.4 · p. 6
• The contrast between explicitly biased and remaining methods holds across all measures and datasets.Source: §5.4 · p. 6

6. ANALYZING SAMPLING BIASES

• XS outperforms on all three network-reach criteria, while the preceding results identify its strength in accumulating nodes from diverse communities.The figure caption reports similar results for the remaining networks.Source: Figure 4 · p. 6, §6 · p. 6

6.1 Existing Analytical Results

• Random walks favor high-degree nodes in the limit, while prior analysis of degree-based walks helps explain DS performance on hub inclusion and discovery quotient.The authors caution that random-walk results appear to hold only in the limit and fail to predict actual sampling performance; other analytical work largely reports negative results.Source: §6.1 · pp. 6–7

6.2 Analyzing XS Bias

• When community conductance is sufficiently low and eout < |V|(ein)^2/[n(|V|+ein|S|)], adding a node from a new community has higher expected expansion than adding one from a represented community.The analysis provides a theoretical basis for the observed link between expansion bias and community reach.Source: §6.2 · p. 7

6.3 Analyzing SEC Bias

• SEC preserves the expected-degree ordering among sampled-neighbor candidates; this helps explain its hub inclusion, with performance relative to DS partly depending on degree-distribution tails.Longer and denser tails allow more slack when real-world link patterns deviate from random-network expectations.Source: §6.3 · pp. 7–8

7.1 Practical Outbreak Detection

• SEC locates top well-connected individuals much faster than ACQ and does not require uniformly random node selection, which ACQ assumes.This makes SEC applicable in realistic scenarios where ACQ is unworkable.Source: §7.1 · p. 8, Figure 6 · p. 8

7.2 Marketing

• XS can sample members of diverse groups without prior demographic attributes, social variables, or knowledge of the network's community structure, supporting potential marketing uses.The passage connects diverse-community sampling to stratified surveys and word-of-mouth marketing.Source: §7.2 · p. 8

7.3 Landmarks and Graph Exploration

• XS is a promising landmark-selection strategy because it covers the network well; BFS ranks low on network-reach measures, prompting scrutiny of its use in exploration and crawling.Landmark methods use distances from sampled nodes to approximate distances between pairs of nodes.Source: §7.3 · p. 8

8. CONCLUSION

• BFS ranks among the worst performers for discovering the network and accumulating critical, well-connected hubs.The conclusion describes BFS as a widely used method for network sampling and crawling.Source: §8 · pp. 8–9
• High-expansion sampling tends to collect nodes in newer, different network portions not already encountered by the sampling process.These nodes are uniquely different from nodes that are simply well-connected or traversed during BFS.Source: §8 · p. 9
• Sampling nodes connected to already sampled nodes reasonably approximates sampling high-degree nodes.Source: §8 · p. 9
• The authors demonstrate applications of these findings in disease outbreak detection and marketing.Source: §8 · p. 9
• Future work will investigate enhancing top-performing strategies, including by alternating or combining sampling biases.Source: §8 · p. 9