Analysis of Sampling Algorithms for Twitter

Deepan Subrahmanian Palguna, Vikas Joshi, Venkatesan T. Chakaravarthy, Ravi Kothari, L. Venkata SubramaniamIJCAI 2015

Abstract

This paper establishes a theoretical framework for determining the minimum sample size required to represent the Twitter "universe." By deriving mathematical bounds based on tweet length and desired precision, the authors demonstrate that representative sampling is independent of total tweet volume. The study focuses on frequent noun mining and sentiment restoration, providing actionable insights for efficient large-scale social media analysis.

Introduction

Twitter generates approximately 500 million tweets daily, creating a "firehose" of data that is computationally expensive to process in its entirety. While Twitter provides a 1% random sample via its API, the statistical representativeness of such samples has largely remained an empirical question. This research provides a theoretical foundation to determine "how much data is enough" for tasks like frequent noun mining and sentiment analysis.

Methodology

The authors model Twitter data using uniform random sampling with replacement, treating tweets as "bags of words" with associated sentiment labels (positive, negative, or neutral). To calculate the required sample size ($K$), the framework utilizes:

  • $\theta$-frequent Nouns: Defining a threshold where a noun is "frequent" if it appears in a specific percentage of the dataset.
  • Chernoff Bounds: Used to bound the probability that a sample's characteristics deviate significantly from the true population.
  • Multinomial Distributions: Applied to model the three-way sentiment classification.
Figure 1: Theoretical bounds on sample size for frequent noun mining as a function of failure probability and noun frequency ($\theta$).

Key Insights

Independence from Universe Size

A primary finding is that the required sample size $K$ is independent of the total number of tweets ($N$) in the universe. Whether sampling from millions or billions of tweets, the sample size needed for a specific confidence level depends only on the maximum tweet length ($L$) and the target noun frequency ($\theta$).

The "Dominance" Shortcut vs. Restoration

The research distinguishes between two goals: restoring the full sentiment distribution and preserving the dominant sentiment.

  • Restoration ensures that the proportions of all sentiments in the sample match the universe.
  • Preservation simply ensures the "winning" sentiment in the sample is the same as in the universe.

As shown in Figure 3, when a clear dominant sentiment exists (e.g., 90% positive), preserving the dominant sentiment requires far fewer samples than full restoration. However, if sentiments are nearly tied, the "preserve" strategy becomes more demanding because the margin for error is much smaller.

Figure 3: Comparison of sample size bounds for "Restoring" vs. "Preserving" sentiment distributions across different sentiment profiles.

Experimental Validation

The theory was validated using the PE-2014 dataset, comprising 200,000 political tweets per day.

  • Noun Mining: For a noun frequency of $\theta = 0.1$, a sample of 8,000 to 10,000 tweets was sufficient to eliminate frequent noun errors in simulations.
  • Sentiment Accuracy: A sample of 10,000 tweets reduced the mean maximum deviation in sentiment frequency to approximately 0.04.

Conclusion

The results suggest that researchers can achieve high-precision results using a mathematically-determined fraction of the Twitter stream. This allows for the use of more sophisticated, computationally intensive NLP tools on smaller, representative samples without sacrificing the accuracy of the "big picture" public opinion. Future work may refine these bounds using VC dimension theory and address the complexities of imperfect classifiers.

Summary updated

BibTeX
@inproceedings{palguna2015analysis,
  author = {Deepan Subrahmanian Palguna and Vikas Joshi and Venkatesan T. Chakaravarthy and Ravi Kothari and L. Venkata Subramaniam},
  title = {{Analysis of Sampling Algorithms for Twitter}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure