Multigraph Sampling of Online Social Networks

I. INTRODUCTION

• Single-relation random walks can produce representative samples only when the social graph is fully connected, and their convergence speed depends strongly on graph characteristics such as clustering.A complete sampling frame is also unavailable for most OSNs, making principled sampling especially difficult.Source: §I · p. 1
• The paper exploits multiple crawlable relations, including friendship, group membership, and event participation, to give crawlers more edges to choose from.These relations can reveal users with no direct social ties, whom a friendship-only crawl cannot discover.Source: §I · p. 1
• The paper proposes a cost-efficient multigraph walk that selects a relation and then enumerates neighbors only in that relation.This avoids enumerating neighbors across every relation at each step.Source: §I · p. 2, Figure 1 · p. 2

A. Terminology and Definitions

• The union multigraph preserves multiple edges between the same node pair, whereas the union simple graph merges them into one edge.The paper focuses on the multigraph as a more efficient structure for implementing sampling across relations.Source: A. Terminology and Definitions · p. 2

1) Naive Multiple Graph Sampling:

• When an individual relation graph is disconnected, its walk remains in the starting component and yields an asymptotically biased sample dependent on the initial seeds.The figure illustrates five disconnected graphs whose union is fully connected.Source: 1) Naive Multiple Graph Sampling · pp. 2–3, Figure 2 · p. 3

2) Union Simple Graph Sampling:

• The union graph can be well-connected even when its constituent graphs are disconnected, allowing a random walk to converge quickly.The example shows each of five graphs disconnected while their union is fully connected.Source: 2) Union Simple Graph Sampling · p. 3, Figure 2 · p. 3
• At every step, union-simple-graph sampling may need to enumerate the current node’s neighbors in every relation, which can be costly.The cost depends on neighborhood size, query costs, and the number of relations.Source: 2) Union Simple Graph Sampling · p. 3

C. Union Multigraph Sampling

• The two-stage procedure selects a relation using the node’s relation-specific degree and then chooses a neighbor in that relation, requiring neighborhood enumeration for only one graph.The procedure is equivalent to selecting a uniformly random incident edge in the union multigraph.Source: C. Union Multigraph Sampling · p. 3
• The algorithm returns sampled nodes and their total degrees, where total degree is the sum of a node’s degrees across relation graphs.The total degree is the node degree in the union multigraph.Source: C. Union Multigraph Sampling · p. 3
• For a connected union multigraph containing at least one triangle, Algorithm 1 converges to the equilibrium distribution π(v) = d(v) / Σu∈V d(u).The proof describes the walk as irreducible and positive recurrent on a finite connected multigraph, with the triangle guaranteeing aperiodicity.Source: C. Union Multigraph Sampling · p. 3

D. Practical Issues

• The authors briefly revisit practical implementation issues and direct readers to their parallel work for further guidance.They identify that work as references.Source: D. Practical Issues · p. 3

1) Choice of crawling technique:

• Re-weighted random walk (RWRW) is used throughout; prior work found it more efficient than alternatives such as Metropolis-Hastings random walks.Source: 1) Choice of crawling technique · p. 4

2) Re-Weighted Random Walk:

• Ordinary multigraph walks favor high-degree nodes, so Hansen-Hurwitz reweighting corrects the bias and gives an unbiased, consistent estimate of the node mean.Source: 2) Re-Weighted Random Walk · p. 4

3) Multiple Walks and Convergence Diagnostics:

• Multiple walks and online convergence diagnostics help identify when walks are in approximate equilibrium and when sampling can safely stop.The diagnostics track running means, compare early and late samples within a walk, and compare variance within and across walks.Source: 3) Multiple Walks and Convergence… · p. 4

III. EVALUATION IN SYNTHETIC GRAPHS

• At Q=6, fLCC ≃1; as Q grows, λ2 and community-estimation error fall, and Q ≃8 at 100 steps matches Q=3 at 500.The figure plots connectivity and λ2 against Q, and estimation error against Q and walk length.Source: Figure 3 · p. 4, §III · pp. 4–5
• The gains also persist with clustered relations: unions with random cliques remain efficient, and clustered random graphs reproduce the earlier results.Source: §III · p. 5

• Last.fm is a music-oriented social network with interest communities that include listeners and artists.Source: §IV · p. 5
• Figure 4 presents multigraphs formed by combining various graphs.Source: Figure 4 · p. 5
• Multigraph sampling obtains a fairly representative Last.fm sample, while sampling on any one relation fails.Source: §IV · p. 5

1) Walking on Relations:

• The crawls use mutual friendship, shared group membership, event attendance, and mutual-neighbor relations to connect users.Last.fm’s neighbor relation includes up to 50 similar users, symmetrized by retaining only mutual neighbors.Source: 1) Walking on Relations · pp. 5–6
• The study compares walks on each individual relation with walks on Friends-Events, Friends-Events-Groups, and Friends-Events-Groups-Neighbors union multigraphs.These crawl types provide the basis for comparing separate and combined relations.Source: 1) Walking on Relations · p. 6

2) Uniform Sample of userIDs (UNI):

• Increasing userIDs generally track later registration dates after the first approximately 2 million users, supporting the use of the ID space for reference sampling.The authors report an exception for the first approximately 2 million users and describe the later ordering as nearly sequential.Source: 2) Uniform Sample of userIDs (UNI) · p. 6
• UNI samples users by drawing IDs uniformly from 0–35 million and rejecting IDs that do not correspond to valid accounts.The authors obtained a 500K-user sample this way; the method relies on a sufficiently small, non-sparse ID space and is not a general OSN solution.Source: 2) Uniform Sample of userIDs (UNI) · p. 6

4) Topology Change During Sampling Process:

• The authors assume Last.fm network changes can be ignored during the 27-day crawl, estimating growth at 0.18%–0.63% per crawl type.They estimate average growth of 25K users per day and report nearly identical studied-property distributions in UNI samples collected one week apart.Source: 4) Topology Change During Sampling… · p. 7
• The first sampling stage discovers a user’s relation graphs and degrees, then selects one graph for the walk.Friends, neighbors, and event lists are collected through API calls; groups are collected by scraping, and each individual group or event is treated as a graph.Source: 5) Efficient Multigraph Sampling in… · p. 7
• The two-stage procedure saves bandwidth and time by avoiding enumeration of group or event members until that relation is selected.For a selected group or event, the second stage fetches the page containing a uniformly chosen member rather than enumerating all members.Source: 5) Efficient Multigraph Sampling in… · p. 7

6) Data Collection:

• Each crawl type uses five independent walks from the same five genre-based seed users and collects exactly 50K samples per walk.The seeds were chosen to be overdispersed; a separate UNI sample contains 500K users.Source: 6) Data Collection · p. 7

7) Summary of Collected Datasets:

• The Friends-Events-Groups-Neighbors multigraph crawl reaches more unique users than any single-graph crawl.The random walks show repetitions ranging from 25% for Friends-Events-Groups-Neighbors to 47% for Neighbors.Source: 7) Summary of Collected Datasets · pp. 7–8
• In combined crawls, Events and Groups dominate transition use when included, which the authors attribute to their large relation-specific degrees.Table II summarizes the fraction of Markov chain transitions using each relation.Source: 7) Summary of Collected Datasets · p. 8, Table II · p. 8
• Despite high user overlap between Groups and Friends-Events-Groups-Neighbors, those crawl types yield very different aggregate user samples.The reported overlap between Groups and Friends-Events-Groups-Neighbors is 66K users.Source: 7) Summary of Collected Datasets · p. 8

B. Evaluation Results

• First-order convergence within each walk is achieved after approximately 500 iterations at maximum.Burn-in was assessed with Geweke diagnostics for each chain and Gelman-Rubin diagnostics across five chains.Source: 1) Convergence · p. 8
• Single-relation crawl types reach the Gelman-Rubin target of R below 1.02 and close to 1 within 1,000 iterations per walk.The result is reported for Friends, Events, Groups, and Neighbors.Source: 1) Convergence · p. 9
• 10K, 12.5K, and 10K samples per crawl type are needed for Friends-Events, Friends-Events-Groups, and Friends-Events-Groups-Neighbors to converge, respectively.The multigraph samples include more isolated users and better reflect ground truth, although diagnostics cannot reliably flag a biased equilibrium caused by non-connectivity.Source: 1) Convergence · p. 9, Figure 9 · p. 9
• Visual inspection shows that estimates of four properties stabilize within 2,000–4,000 samples per walk, or 10,000–20,000 across five walks.The authors also assess the remaining samples with convergence diagnostics.Source: 1) Convergence · p. 9

2) Discovering Isolated Components:

• 88% of UNI-sample users are isolates in Friends, 96–99% in Events, and 93.8% in Groups; 59% of users without friends still show activity.These results indicate that many isolates on a relation are active Last.fm users, not necessarily inactive accounts.Source: 2) Discovering Isolated Components · p. 9
• The Friends-Events-Groups-Neighbors multigraph best estimates isolate percentages overall, except that Neighbors better estimates Friends isolates.Neighbors is used only 0.02% of the time in that multigraph crawl, and the authors note that weighting it more heavily or using a less sparse relation could improve the estimate.Source: 2) Discovering Isolated Components · p. 9

3) Comparing Samples to Ground Truth:

• The all-relations multigraph is closest to UNI for the plotted user-property means, while single-graph crawls give poor estimates and Events or Groups alone overestimate averages.The all-relations crawl closely approximates the average number of groups and percentage of paid subscribers.Source: 3) Comparing Samples to Ground Truth · p. 10, Figure 10 · p. 10
• The all-relations multigraph is closest to UNI in distribution shape and vertical distance, though the gap is largest for number of friends.The authors attribute remaining gaps in distributions and running means to imperfect estimates of isolate percentages.Source: 3) Comparing Samples to Ground Truth · p. 10, Figure 11 · p. 11
• Weekly charts provide an approximate validation reference when a known uniform sample is unavailable.The paper compares sampled estimates with Last.fm’s published weekly charts as a different source of ground truth.Source: 3) Comparing Samples to Ground Truth · p. 10
• The all-relations crawl’s estimated artist and track rank curves track Last.fm’s weekly charts, while single-graph crawl estimates are quite far from the charts.The comparison uses charts for the week July 04–July 11, 2010, and the same chart artists and tracks for all crawl types.Source: 3) Comparing Samples to Ground Truth · pp. 10–11, Figure 12 · p. 11

V. RELATED WORK

• Frontier sampling explores multiple dependent random walks in disconnected or loosely connected subgraphs, whereas multigraph sampling explores relations; the approaches are described as orthogonal and potentially combinable.The paper also relates multigraph sampling to methods that seek faster mixing, including Metropolis-coupled MCMC and simulated tempering.Source: §V · p. 11
• The study assumes the network remains static during a crawl, a reasonable approximation for Last.fm based on snapshots one week apart; it does not address dynamics.The paper notes dynamics are essential in other contexts.Source: §V · p. 12
• The paper adopts practical recommendations from its earlier single-graph crawling framework and, while focusing on multigraph sampling and its utility on fragmented networks.The authors state that, to their knowledge, this is the first exploration of OSN sampling over multiple relations.Source: §V · p. 12

VI. CONCLUSION

• Multigraph sampling can improve coverage and convergence time on partitioned or highly clustered networks, and can approximate uniform sampling on Last.fm even when most users are isolates in each relation.The conclusion presents it as a useful addition to methods for sampling OSNs.Source: §VI · p. 12
• The paper’s stated focus is both demonstrating multigraph sampling’s utility against single-graph sampling and designing an efficient two-stage implementation.The conclusion identifies relation selection and weighting as open questions for optimizing performance.Source: §VI · p. 12