Sampling Content Distributed Over Graphs

Pinghui Wang, Junzhou Zhao, John C. S. Lui, Don Towsley, Xiaohong GuanarXiv 2013 · OpenReview

Abstract

Despite recent efforts to estimate topology characteristics of large graphs such as online social networks and peer-to-peer networks, little attention has been given to developing a formal methodology to characterize the vast amount of content distributed over these networks. Due to the large-scale nature of these networks, exhaustive enumeration of this content is computationally prohibitive. This paper demonstrates how to obtain content properties by sampling only a small fraction of vertices. We show that naive sampling produces significant bias in content statistics, such as the average number of content duplications. To address this, we propose two efficient estimators: the Special Copy Estimator (SCE) and the Weighted Copy Estimator (WCE). Experimental results show that these estimators are cost-effective and asymptotically unbiased, providing a new tool for efficiently querying content in large-scale networks.

The Challenge of Content Duplication

While researchers have perfected methods for estimating the topology of large graphs (e.g., degree distributions), the content living on those graphs presents a different set of challenges. Measuring content properties—such as the distribution of retweets in a social network or file replicas in a P2P network—is difficult because content is often duplicated across many nodes.

Conceptual model of content distributed across a graph, where files (F_i) are duplicated across multiple user nodes.

If nodes are sampled at random to see what content they hold, a massive duplication bias occurs: popular content with thousands of copies is much more likely to be sampled than unique content. A naive "Distinct Content Estimator" (DCE) will wildly overestimate the average popularity of items. While Maximum Likelihood Estimation (MLE) can theoretically correct this, it requires sampling nearly the entire graph to achieve accuracy, which defeats the purpose of sampling.

Proposed Estimators: SCE and WCE

The authors propose moving beyond simple node-counting by utilizing the "meta-information" often found in modern network protocols and social media APIs.

  1. Special Copy Estimator (SCE): This method assumes we can identify a "source" or "original" version of a piece of content (e.g., an original tweet vs. a retweet). By only counting these "special copies" during sampling, the estimator mathematically removes the duplication bias.
  2. Weighted Copy Estimator (WCE): This approach is more powerful for networks where "original" labels aren't available but "copy counts" are (e.g., a P2P file listing its total seeds, or a tweet displaying its retweet count). WCE assigns a weight to each sampled copy that is inversely proportional to the total number of copies in the network, effectively "normalizing" the influence of popular items.

WCE can also be extended to estimate graph structure by sampling a user and looking at the "summary" of their neighbors—a feature common in platforms like Sina Microblog.

Key Results and Performance

The effectiveness of these estimators was tested using real-world datasets from Xiami (a music social network), YouTube, Flickr, and Sina Microblog, alongside synthetic content distribution schemes.

Comparison of estimators (SCE, WCE, DCE, MLE) against real values for different content distributions (W=20 and W=100).

The experimental results confirmed several key findings:

  • Bias Removal: Naive sampling (DCE) was shown to be highly biased, while both SCE and WCE proved to be asymptotically unbiased.
  • Accuracy: WCE consistently outperformed SCE. In experiments on the Xiami dataset, WCE was one to two orders of magnitude more accurate than SCE for content with a high number of copies (long-tail distribution).
  • MLE Failure: Experiments confirmed that MLE is impractical for large graphs; it requires sampling a huge fraction of the network to converge, whereas WCE works with a tiny fraction (e.g., 1%).
  • Real-world Application: On Sina Microblog, a naive count suggested an average of 423 retweets per tweet, but the unbiased WCE estimator revealed the true average was closer to 1.6.

Conclusion

Content sampling is a different mathematical beast than vertex sampling. Because content can exist in multiple places at once, the probability of "hitting" a piece of content is proportional to its popularity, creating a non-linear bias. By using the network's own metadata (retweet counts, source labels) as a shortcut, SCE and WCE provide accurate, unbiased results with significantly lower sampling costs than traditional methods. Future work will explore how these estimators handle dynamic networks where content is constantly being created or deleted in real-time.

Summary updated

Abstract

Despite recent effort to estimate topology characteristics of large graphs (i.e., online social networks and peer-to-peer networks), little attention has been given to develop a formal methodology to characterize the vast amount of content distributed over these networks. Due to the large scale nature of these networks, exhaustive enumeration of this content is computationally prohibitive. In this paper, we show how one can obtain content properties by sampling only a small fraction of vertices. We first show that when sampling is naively applied, this can produce a huge bias in content statistics (i.e., average number of content duplications). To remove this bias, one may use maximum likelihood estimation to estimate content characteristics. However our experimental results show that one needs to sample most vertices in the graph to obtain accurate statistics using such a method. To address this challenge, we propose two efficient estimators: special copy estimator (SCE) and weighted copy estimator (WCE) to measure content characteristics using available information in sampled contents. SCE uses the special content copy indicator to compute the estimate, while WCE derives the estimate based on meta-information in sampled vertices. We perform experiments to show WCE and SCE are cost effective and also ``{\em asymptotically unbiased}''. Our methodology provides a new tool for researchers to efficiently query content distributed in large scale networks.
BibTeX
@misc{wang2013sampling,
  author = {Pinghui Wang and Junzhou Zhao and John C. S. Lui and Don Towsley and Xiaohong Guan},
  title = {{Sampling Content Distributed Over Graphs}},
  year = {2013},
  eprint = {1311.3882},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1311.3882},
}

Loading related content...

Figure