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.
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.
- 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.
- 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.
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