Variation across Scales: Measurement Fidelity under Twitter Data Sampling

A comprehensive understanding of data quality is the cornerstone of measurement studies in social media research. This paper presents in-depth measurements on the effects of Twitter data sampling across different timescales and different subjects (entities, networks, and cascades). By constructing complete tweet streams, we show that Twitter rate limit message is an accurate indicator for the volume of missing tweets. Sampling also differs significantly across timescales. While the hourly sampling rate is influenced by the diurnal rhythm in different time zones, the millisecond level sampling is heavily affected by the implementation choices. For Twitter entities such as users, we find the Bernoulli process with a uniform rate approximates the empirical distributions well. It also allows us to estimate the true ranking with the observed sample data. For networks on Twitter, their structures are altered significantly and some components are more likely to be preserved. For retweet cascades, we observe changes in distributions of tweet inter-arrival time and user influence, which will affect models that rely on these features. This work calls attention to noises and potential biases in social data, and provides a few tools to measure Twitter sampling effects.


Introduction
"Polls are just a collection of statistics that reflect what people are thinking in 'reality'. And reality has a wellknown liberal bias." -Stephen Colbert 1 Data quality is a timely topic that receives broad attention. The data noises and biases particularly affect data-driven studies in social media (Tufekci 2014;Olteanu et al. 2019). Overrepresented or underrepresented data may mislead researchers to spurious claims (Ruths and Pfeffer 2014). For example, opinion polls wrongly predicted the U.S. presidential election results in 1936 and 1948 because of unrepresentative samples (Mosteller 1949). In the era of machine learning, the data biases can be amplified by the subsequent models. For example, models overly classify agents doing cooking activity as female due to overrepresented correlations (Zhao et al. 2017), or lack the capacity to identify darkskinned women due to underrepresented data (Buolamwini and Gebru 2018). Hence, researchers must be aware and take Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 1 At the 2006 White House Correspondents' Dinner.
account of the hidden biases in their datasets for drawing rigorous scientific conclusions.
Twitter is the most prominent data source in ICWSM -82 (31%) out of 265 full papers in the past 5 years (2015-2019) used Twitter data (listed in Section A of (Appendix 2020)), in part because Twitter has relatively open data policies, and in part because Twitter offers a range of public application programming interfaces (APIs). Researchers have used Twitter data as a lens to understand political elections (Bovet and Makse 2019), social movements (De Choudhury et al. 2016), information diffusion (Zhao et al. 2015), and many other social phenomena. Twitter offers two streaming APIs for free, namely sampled stream and filtered stream. The filtered stream tracks a set of keywords, users, languages, and locations. When the matched tweet volume is above a threshold, Twitter subsamples the stream, which compromises the completeness of the collected data. In this paper, we focus on empirically quantifying the data noises resulted from the sampling in the filtered stream and its impacts on common measurements. This work addresses two open questions related to Twitter data sampling. Firstly, how are the tweets missing in the filtered stream? The sampling mechanism of the sampled stream has been extensively investigated (Kergl, Roedler, and Seeber 2014;Pfeffer, Mayer, and Morstatter 2018), but relatively little is said about the filtered stream. Since the two streaming APIs are designed to be used in different scenarios, it is pivotal for researchers who use the filtered stream to understand what, when, and how much data is missing. Secondly, what are the sampling effects on common measurements? Our work is inspired by Morstatter et al. (2013), who measured the discrepancies of topical, network, and geographic metrics. We extend the measurements to entity frequency, entity ranking, bipartite graph, retweet network, and retweet cascades. The answers to these questions not only help researchers shape appropriate questions, but also help platforms improve their data services.
We address the first question by curating two datasets that track suggested keywords in previous studies. Without leveraging the costly Twitter Firehose service, we construct the complete tweet streams by splitting the keywords and languages into multiple subcrawlers. We study the Twitter rate limit messages. Contradicting observations made by Sampson et al. (2015), our results show that the rate limit mes-sages closely approximate the volume of missing data. We also find that tweets are not missing at random since the sampling rates have distinct temporal variations across different timescales, especially at the level of hour and millisecond.
Addressing the second question, we measure the effects of Twitter data sampling across different subjects, e.g., the entity frequency, entity ranking, user-hashtag bipartite graph, retweet network, and retweet cascades. We find that (1) the Bernoulli process with a uniform rate can approximate the empirical entity distribution well; (2) the ranks of top entities are distorted; (3) the true entity frequency and ranking can be inferred based on sampled observations; (4) the network structures change significantly with some components more likely to be preserved; (5) sampling compromises the quality of diffusion models as the distributions of tweet inter-arrival time and user influence are substantially skewed. We remark that this work only studies the effects of Twitter sampling mechanism, but does not intend to reverse engineer it.
The main contributions of this work include: • We show that Twitter rate limit message is an accurate indicator for the volume of missing tweets.
• A set of measurements on the Twitter data sampling effects across different timescales and different subjects.
• We show how to estimate the entity frequency and ranking of the complete data using only the sample data.
• We release a software package "Twitter-intact-stream" for constructing the complete data streams on Twitter 2 .

Related work
Studies on Twitter APIs. Twitter has different levels of access (Firehose, Gardenhose, Spritzer) and different ways to access (search API, sampled stream, filtered stream). As the complete data service (Firehose) incurs excessive costs and requires severe storage loads, we only discuss the free APIs.
• Twitter search API returns relevant tweets for a given query, but it only fetches results published in the past 7 days (Twitter.com 2020d). The search API also bears the issue of data attrition. Research using this API to construct a "complete" dataset would inevitably miss parts of desired tweets (Wang, Callan, and Zheng 2015) since tweet creation and deletion are highly dynamic (Almuhimedi et al. 2013). To overcome this limitation, researchers can pivot to the streaming APIs.
• Twitter sampled streaming API returns roughly 1% of all public tweets in realtime (Twitter.com 2020c). Pfeffer, Mayer, and Morstatter (2018) detailed its sampling mechanism and identified potential tampering behaviors. González-Bailón et al. (2014) examined the biases in the retweet network from the 1% sample and the search API. While the 1% sample may be treated as a representative sample of overall Twitter activities (Morstatter, Pfeffer, and Liu 2014;Kergl, Roedler, and Seeber 2014), data filtering can only be conducted post data collection. There-fore, it is not suitable to create ad hoc datasets, e.g., tracking all tweets that contain the hashtag #metoo.
• Twitter filtered streaming API collects tweets matching a set of prescribed predicates in realtime (Twitter.com 2020a). Suppose that the streaming rate is below Twitter limit, the pre-filtering makes the filtered stream possible to construct the complete datasets without using the costly Firehose stream, e.g., on social movements (De Choudhury et al. 2016) and on news outlets (Mishra, Rizoiu, and Xie 2016). We focus on the scenes where the data streams are sampled. The most relevant work is done by Morstatter et al. (2013), in which they compared the filtered stream to the Firehose, and measured the discrepancies in various metrics. We extend the scope of measured subjects. Furthermore, we take a step to correct the sampling effects on entity measures.
Twitter sampling is deterministic (Joseph, Landwehr, and Carley 2014), therefore, simply stacking crawlers with the same predicates will not yield more data. However, users can improve the sample coverage by splitting the keyword set into multiple disjoint predicate sets, and monitoring each set with a distinct subcrawler (Sampson et al. 2015). Effects of missing social data. Social data, which records ubiquitous human activities in digital form, plays a fundamental role in social media research. Researchers have pointed out the necessity to interrogate the assumptions and biases in data (Boyd and Crawford 2012;Ruths and Pfeffer 2014). Tufekci (2014) outlined four issues on data representativeness and validity. The hidden data biases may alter some research conclusions and even impact human decision making (Olteanu et al. 2019). Gaffney and Matias (2018) identified gaps where data is unevenly missing in a widely used Reddit corpus. They suggested strong risks in research that concerns user history or network information, and moderate risks in research that uses aggregate counts. In this work, we use these qualitative observations as starting points and present a set of in-depth quantitative measurements. We corroborate the risks in user history study and network analysis. And we show how the complete counting statistics can be estimated. Sampling from graphs and cascades. Leskovec and Faloutsos (2006) studied different graph sampling strategies for drawing representative samples. Wagner et al. (2017) considered how sampling impacts the relative ranking of groups in the attributed graphs. The effects of graph sampling has been extensively discussed by Kossinets (2006). In this work, the missing tweets can cause edge weights to decrease, and some edges to even disappear. On sampling a cascade, De Choudhury et al. (2010) found that combining network topology and contextual attributes distorts less the observed metrics. Sadikov et al. (2011) proposed a k-tree model to uncover some properties from the sampled data. They both sampled the cascades via different techniques (e.g., random, forest fire) and varying ratios. In contrast, the sampling in this work is an artifact of proprietary Twitter sampling mechanisms, and beyond the control of the users.  Figure 1: (a) Collected and missing tweets in an 11-second interval. blue circle: collected tweet; black cross: missing tweet; black vertical line: rate limit message. green number: estimated missing volume from rate limit messages; black number: count of missing tweets compared to the complete set. (b) MAPE of estimating the missing volumes in the rate limit segments.

Datasets and Twitter rate limit messages
We collect two datasets, using two sets of keywords employed in recent large-scale studies that use Twitter. We choose these works because they are high volume and informative for important social science problems (cyberbullying and online content sharing). We use ρ to denote the sampling rate -i.e., the probability that a tweet is present in the collected (sampled) dataset. We use subscripts to differentiate sampling rates that vary over time ρ t , users ρ u , networks ρ n , and cascades ρ c . The datasets are collected using the Twitter filtered streaming API and are summarized in Table 1.
The streaming client is a program that receives streaming data via Twitter API. The client will be rate limited if the number of matching tweets exceeds a preset threshold -50 tweets per second as of 2020-03 (Twitter.com 2020b). When we use only one client to track all keywords, we find that both datasets trigger rate limiting. We refer to the crawling results from a single client as the sample set.
We develop a software package "Twitter-intact-stream" 3 for constructing the complete data streams on Twitter. The package splits the filtering predicates into multiple subsets, and tracks each set with a distinct streaming client. The CYBERBULLYING and YOUTUBE datasets are respectively crawled by 8 and 12 clients based on different combinations of keywords and languages. We remove the duplicate tweets and sort the distinct tweets chronologically. We refer to the crawling results from multiple clients as the complete set.
In very occasional cases, the complete sets also encounter rate limiting. Estimated from the rate limit messages (detailed next), 0.04% and 0.14% tweets in the complete sets are missing, which are negligible comparing to the volumes of missing tweets in the sample sets (47.28% and 8.47%, respectively). For rigorous comparison, we obtain a 30 minutes complete sample from Twitter Firehose and find the difference with our collected data is trivial (detailed in Section 3 https://github.com/avalanchesiqi/twitter-intact-stream  Table 1: Summary of two datasets. N c : #collected tweets; N r : #rate limit messages;N m : #estimated missing tweets; ρ: mean sampling rate. Full specifications for all streaming clients are listed in Section B of (Appendix 2020).
C of (Appendix 2020)). Hence, for the rest of this work, we treat the complete sets as if they contain no missing tweets. Validating Twitter rate limit messages. When the streaming rate exceeds the threshold, Twitter API emits a rate limit message that consists of a timestamp and an integer. The integer is designed to indicate the cumulative number of missing tweets since the connection starts (Twitter.com 2020e). Therefore, the difference between 2 consecutive rate limit messages should estimate the missing volume in between. We empirically validate the rate limit messages. We divide the datasets into a list of segments where (a) they contain no rate limit message in the complete set; (b) they are bounded by 2 rate limit messages in the sample set. This yields 1,871 and 253 segments in the CYBERBULLYING and YOUTUBE datasets, respectively. The lengths of segments range from a few seconds to several hours, and collectively cover 13.5 days out of the 14-day crawling windows. In this way, we assure that the segments in the complete set have no tweet missing since no rate limit message is received. Consequently, for each segment we can compute the volume of missing tweets in the sample set by either computing the difference of the two rate limit messages bordering the segment, or by comparing the collected tweets with the complete set. Figure 1(a) illustrates the collected and missing tweets in an 11-second interval. The estimated missing volumes from rate limit messages closely match the counts of the missing tweets in the complete set. Overall, the median error in estimating the missing volume using rate limit messages is less than 0.0005, measured by mean absolute percentage error (MAPE) and shown in Figure 1(b). We thus conclude that the rate limit message is an accurate indicator for the number of missing tweets. Note that it only approximates the volume of missing tweets, but not the content.
Our observations contradict those from Sampson et al. (2015), who used the same keyword-splitting approach, yet found that the rate limit messages give inaccurate estimations. They consistently retrieved more distinct tweets (up to 2 times) than the estimated total volume, i.e., the number of collected tweets plus the estimated missing tweets. In contrast, our datasets only have a small deviation (0.08% and 0.13%, comparing N c of the complete set to N c +N m of the sample set in Table 1). This discrepancy is due to a different implementation choice back in 2015 -instead of having 1 rate limit message for each second, the rate limit messages were spawned across 4 threads, resulting in up to 4 messages per second. We provide a detailed analysis in Section C of (Appendix 2020).

Are tweets missing at random?
In this section, we study the randomness of Twitter sampling -do all tweets share the same probability of missing? This is relevant because uniform random sampling creates representative samples. When the sampling is not uniform, the sampled set may suffer from systematic biases, e.g., some tweets have a higher chance of being observed. Consequently, some users or hashtags may appear more often than their cohorts. We tackle the uniformity of the sampling when accounting for the tweet timestamp, language, and type. Tweet timestamps. Figure 2(a) plots the hourly sampling rates. CYBERBULLYING dataset has the highest sampling rate (ρ t =78%) at UTC-8. The lowest sampling rate (ρ t =41%) occurs at UTC-15, about half of the highest value. YOUTUBE dataset is almost complete (ρ t =100%) apart from UTC-8 to UTC-17. The lowest sampling rate is 76% at UTC-12. We posit that the hourly variation is related to the overall tweeting dynamics and the rate limit threshold (i.e., 50 tweets per second): higher tweet volumes yield lower sampling rates. Figure 2(b) shows the sampling rate at the millisecond level, which curiously exhibits a periodicity of one second. In CYBERBULLYING dataset, the sampling rate peaks at millisecond 657 (ρ t =100%) and drops monotonically till millisecond 550 (ρ t =6%) before bouncing back. YOUTUBE dataset follows a similar trend with the lowest value (ρ t =76%) at millisecond 615. This artifact leaves the sample set vulnerable to automation tools. Users can deliberately schedule tweet posting time within the high sampling rate period for inflating their representativeness, or within the low sampling rate period for masking their content in the public API. The minutely and secondly sampling rates are included in Section D of (Appendix 2020).   Table 2: The ratios of the 4 tweet types (root tweet, retweet, quote, and reply) in the complete and the sample sets.
Tweet languages. Some languages are mostly used within one particular timezone, e.g., Japanese and Korean 4 . The temporal tweet volumes for these languages are related to the daily activity patterns in the corresponding countries. We break down the hourly tweet volumes of YOUTUBE dataset into Japanese+Korean and other languages. The results are shown in Figure 3. Altogether, Japanese and Korean account for 31.4% tweets mentioning YouTube URLs. The temporal variations are visually different -48.3% of Japanese and Korean tweets are posted in the evening of local time (JST-6pm to 12am), while tweets in other languages disperse more evenly. Because of the high volume of tweets in this period, sampling rates within UTC-9 to UTC-15 are lower (see Fig-ure 2(a)). Consequently, "ja+ko" tweets are less likely to be observed (89.0% in average, 80.9% between JST-6pm and 12am) than others (92.9% in average). Tweet types. Twitter allows the creation of 4 types of tweets. The users create a root tweet when they post new content from their home timelines. The other 3 types are interactions with existing tweets: retweets (when users click on the "Retweet" button); quotes (when users click on the "Retweet with comment" button); replies (when users click on the "Reply" button). The relative ratios of different types of tweets are distinct for the two datasets (see Table 2). CYBERBULLYING has higher ratios of retweets, quotes, and replies than YOUTUBE, implying more interactions among users. However, the ratios of different types are very similar in the sampled versions of both datasets (max deviation=0.41%, retweets in YOUTUBE dataset). We conclude that Twitter data sampling is not biased towards any tweet type.

Impacts on Twitter entities
In this section, we study how the data sampling affects the observed frequency and relative ranking of Twitter entities, e.g., users, hashtags, and URLs. We first use a Bernoulli process to model the Twitter data sampling (Section 5.1). Next, we show how the entity statistics for one set (e.g., the complete) can be estimated using the other set (the sample, Section 5.2). Finally, we measure the distortions introduced in entity ranking by sampling and how to correct them (Section 5.3). The basic statistics of entities are listed in Table 3. The analyses in this section, Section 6, and Section 7, are done with CYBERBULLYING dataset since its sampling effects are more prominent.

Twitter sampling as a Bernoulli process
We examine how well we can use a Bernoulli process to approximate the Twitter sampling process. Assuming that tweets are sampled identically and independently, the Twitter sampling can be be seen as a simple Bernoulli process with the mean sampling rateρ. We empirically validate this assumption by plotting the complementary cumulative density functions (CCDFs) of user posting frequency (the number of times a user posts) and hashtag frequency (the number of times a hashtag appears) in Figure 4. The black and blue solid lines respectively show the CCDFs of the complete and the sample sets, while the black dashed line shows the CCDF in a synthetic dataset constructed from the complete set using a Bernoulli process with rateρ=52.72%. Firstly, we observe that the CCDF of the sample set is shifted left, towards the lower frequency end. Visually, the distributions for the synthetic (black dashed line) and for the observed sample set (blue solid line) overlap each other. Furthermore, following the practices in (Leskovec and Faloutsos 2006), we measure the agreement between these distributions with Kolmogorov-Smirnov D-statistic, which is defined as  where G and G are the cumulative distribution functions (CDFs) of two distributions. With a value between 0 and 1, a smaller D-statistic implies more agreement between two measured distributions. The results show high agreement between entity distributions in the synthetic and the observed sample sets (0.0006 for user posting and 0.002 for hashtag). This suggests that despite the empirical sampling rates not being unique over time, a Bernoulli process of constant rate can model the observed entity frequency distribution well 5 .

Entity frequency
We investigate whether the statistics on one set (complete or sample) can be estimated using only the statistics of the other set and the Bernoulli process model. We use n c to denote the frequency in the complete set, and n s the frequency in the sample set (n c ≥n s ). More precisely, we ask these three questions: What is the distribution of n s given n c =k? What is the distribution of n c given n s =k? How many entities are missing altogether given the distribution of n s ? Modeling sample frequency from the complete set.
For a user who posts n c times in the complete set, their sample frequency under the Bernoulli process follows a binomial distribution B(n c ,ρ). Specifically, the probability of observing the user n s times in the sample set is We compute the empirical distribution and binomial distribution for n c from 1 to 100. This covers more than 99% users in our dataset. Figure 5(a) shows the D-statistic between two distributions as a function of complete frequency n c . The binomial distribution models the empirical data better when n c is smaller. Figure 5 in the sample set, their complete frequencies follows a negative binomial distribution N B(n s ,ρ). The negative binomial distribution models the discrete probability distribution of the number of Bernoulli trials before a predefined number of successes occurs. In our context, given n s tweets (n s ≥1) are successfully sampled, the probability of having n c tweets in the complete set is We compute the empirical distribution and negative binomial distribution for n s from 1 to 100. Figure 6(a) shows the D-statistic as a function of sample frequency n s . Negative binomial distributions models the best when the number of observed tweets is between 9 and 15 (D-statistic<0.02). Figure 6(b) shows both distributions for n s =13, where the minimal D-statistic is reached. The negative binomial distribution closely resembles the empirical distribution. Their estimated mean complete frequencies are very similar (23.60 vs. 23.72, shown as dashed vertical lines). Estimating missing volume from the sample set. In data collection pipelines, the obtained entities from the filtered stream are sometimes used as seeds for the second step crawling, such as constructing user timelines based on user IDs (Wang, Callan, and Zheng 2015), or querying YouTube statistics based on video URLs (Wu, Rizoiu, and Xie 2018). However, some entities may be completely missing due to Twitter sampling. We thus ask: can we estimate the total number of missing entities given the entity frequency distribution of the sample set?
We formulate the problem as solving a matrix equation with constraints. We use the symbol F to denote the entity frequency vector. F[n s ] represents the number of entities that occurs n s times in the sample set. We want to estimate the frequency vectorF of the complete set. For any n s , its sam- We constrainF to be non-negative numbers and decrease monotonically since the frequency distribution is usually heavy-tailed in practice (see Figure 4). We use the frequency vector for n s ∈[1, 100]. The above matrix equation can be solved as a constrained optimization task. For users who post n c times in the complete set, the probability of their tweets completely missing is Pr(n s =0; n c ,ρ)=(1−ρ) nc . Altogether, the estimated missing volume is ∞ nc=1 (1−ρ) ncF [n c ] for the whole dataset. We show the estimated results in the rightmost column of Table 3. The relative errors (MAPE) are smaller than 0.5% for all entities. This suggests that the volume of missing entities can be accurately estimated if the frequency distribution of the sample set is observed. Summary. Although the empirical sample rates have clear temporal variations, we show that we can use the mean sampling rate to estimate some entity statistics, including the frequency distribution and the missing volume. This reduces the concerns on assuming the observed data stream is a result of uniform random sampling (Joseph, Landwehr, and Carley 2014;Morstatter, Pfeffer, and Liu 2014;Pfeffer, Mayer, and Morstatter 2018).

Entity ranking
Entity ranking is important for many social media studies. One of the most common strategies in data filtering is to keep entities that rank within the top x, e.g., most active users or most mentioned hashtags (Morstatter et al. 2013;González-Bailón et al. 2014). We measure how the Twitter data sampling distorts entity ranking for the most active users, and whether the ground-truth ranking in the complete set can be inferred from the sample ranking. Note that in this subsection, we allow the sampling rates to be timedependent ρ t and user-dependent ρ u -as the sampling with a constant rate would preserve the ranking between the complete and the sample sets. For the universal ranking (considering all entities), we use percentile to measure it and find the higher ranked entities have smaller deviations (detailed in Section E of (Appendix 2020)). Detecting rank distortion. Figure 7(a) plots the most active 100 users in the sample set on the x-axis, and their ranks in the complete set on the y-axis. Each circle is colored based on the corresponding user sampling rate ρ u . The diagonal line indicates uniform random sampling, in which the two sets of ranks should be preserved. The users above the diagonal line improve their ranks in the sample set, while the ones below lose their positions. Figure 7(c) highlights a user WeltRadio, who benefits the most from the sampling: it ranks 50th in the complete set, but it is boosted to 15th place in the sample set. Comparing the complete tweet volume, its volume (4,529) is only 67% relative to the user who actually ranks 15th in the complete set (6,728, user thirdbrainfx). We also find that WeltRadio tweets mostly in the very high sampling rate secondly period (millisecond 657 to 1,000), resulting in a high user sampling rate (ρ u =79.1%). On the contrary, Figure 7(d) shows a user bensonbersk with decreased rank in the sample set and low sampling rate (ρ u =36.5%). Examining his posting pattern, this user mainly tweets in the low sampling rate hours (UTC-12 to 19). Estimating true ranking from the sample set. Apart from measuring the rank distortion between the complete and the sample sets, we investigate the possibility of estimating the ground-truth ranks by using the observations from the sample set. From the rate limit messages, we extract the temporal sampling rates that are associated with different timescales (hour, minute, second, and millisecond), i.e., ρ t (h, m, s, ms). Based on the negative binomial distribution, for a user who we observe n s times at timestamp κ=(h, m, s, ms), the expected volume is n s /ρ t (κ).
We compute the estimated tweet volumes for all users and select the most active 100 users. Figure 7(b) shows the estimated ranks on the x-axis and the true ranks on the yaxis. We quantify the degree of agreement using Kendall's τ , which computes the difference of concordant and discordant pairs between two ranked lists. With value between 0 and 1, a larger value implies more agreement. The Kendall's τ is improved from 0.7349 to 0.8485 with our estimated ranks. The rank correction is important since it allows researchers to mitigate the rank distortion without constructing a complete data stream.

Impacts on networks
In this section, we measure the effects of data sampling on two commonly studied networks on Twitter: the userhashtag bipartite graph, and the user-user retweet network.

User-hashtag bipartite graph
The bipartite graph maps the affiliation between two disjoint sets of entities. No two entities within the same set are linked. Bipartite graphs have been used in many social applications, e.g., mining the relation between scholars and published papers (Newman 2001), or between artists and concert venues (Arakelyan et al. 2018   user-hashtag bipartite graphs for both the complete and the sample sets. This graph links users to their used hashtags. Each edge has a weight -the number of tweets between its associated user and hashtag. The basic statistics for the bipartite graphs are summarized in Table 4. Clustering techniques are often used to detect communities in such bipartite graphs. We apply spectral clustering (Stella and Shi 2003) on the user-hashtag bipartite graph, with the number of clusters set at 6. The resulted clusters are summarized in Table 5, together with the most used 5 hashtags and a manually-assigned category. Apart from the cyberbullying keywords, there are significant amount of hashtags related to politics, live streaming, and Korean pop culture, which are considered as some of the most discussed topics on Twitter. We further quantify how the clusters traverse from the complete set to the sample set in Figure 8. Three of the complete clusters (CC1, CC2, and CC3) are maintained in the sample set (mapping to SC1, SC2, and SC3 respectively), since more than half of the entities preserve. The remaining three complete clusters disperse. Investigating the statistics for the complete clusters, the preserved ones have a larger average weighted degree, meaning complete set   Figure 9: Visualization of bow-tie structure in complete set. The black number indicates the relative size of component in the complete set, blue number indicates the relative size in the sample set. more tweets between the users and hashtags in these clusters. Another notable observation is that albeit the entities traverse to the sample clusters differently, all complete clusters have similar missing rates (28% to 34%). It suggests that Twitter data sampling impacts the community structure. Denser structures are more resilient to sampling.

User-user retweet network
Retweet network describes the information sharing between users. We build a user-user retweet network by following the "@RT" relation.. Each node is a user, and each edge is a directed link weighted by the number of retweets between two users. The user-user retweet network has been extensively investigated in literature (Sadikov et al. 2011;Morstatter et al. 2013;González-Bailón et al. 2014).
We choose to characterize the retweet network using the bow-tie structure. Initially proposed to measure the World Wide Web (Broder et al. 2000), the bow-tie structure was also used to measure the QA community (Zhang, Ackerman, and Adamic 2007) Figure 9 visualizes the bow-tie structure of the user-user retweet network, alongside with the relative size for each component in the complete and sample sets. The LSCC and IN components, which make up the majority part of the bow-tie, reduce the most in both absolute size and relative ratio due to sampling. OUT and Tubes are relatively small in both complete and sample sets. Tendrils and disconnected components enlarge 39% and 32% after sampling. Figure 10 shows the node flow of each components from the complete set to the sample set.

Impacts on retweet cascades
Information diffusion is perhaps the most studied social phenomenon on Twitter. A retweet cascade consists of two parts: a root tweet and its subsequent retweets. A number of models have been proposed for modeling and predicting retweet cascades (Zhao et al. 2015;Mishra, Rizoiu, and Xie 2016;Martin et al. 2016). However, these usually make the assumption of observing all the retweets in cascades. In this section, we analyze the impacts of Twitter sampling on retweet cascades and identify risks for existing models. We first construct cascades without missing tweets from the complete set. Next, we measure the sampling effects for some commonly used features in modeling retweet cascades, e.g., inter-arrival time and potential reach. Constructing complete cascades. When using the filtered streaming API, if a root tweet is observed, the API should return all its retweets. This is because the API also tracks the keywords in the retweeted status field of a tweet (i.e., the root tweet), which allows us to construct a set of complete cascades from the complete set. In the sample set, both the root tweet and any of its retweets could be missing. If the root tweet is missing, we miss the entire cascade. If some retweets are missing, we observe a partial cascade. Table 6 lists the obtained cascades in the complete and the sample sets. Notably, there are 3M cascades in the complete set, but only 1.17M in the sample set (38.85%), out of which only 508k (16.88%) cascades are complete and their sizes are relatively small (i.e., they don't miss any retweet, max cascade size: 23, mean size: 1.37). Prior literature (Zhao et al. 2015) often concentrates on retweet cascades with more than 50 retweets. There are 99,952 such cascades in the complete set, but only 29,577 in the sample set, out of which none is complete.
Inter-arrival time. One line of work models the information diffusion as point processes (Zhao et al. 2015;Mishra,    Rizoiu, and Xie 2016). These models use a memory kernel as a function of the time gap ∆t between two consecutive events, which is also known as inter-arrival time. Figure 11(a) plots the CCDFs of inter-arrival times in the complete and the sample sets. The distribution shifts right, towards larger values. This is expected as the missing tweets increase the time gap between two observed tweets. The median inter-arrival time is 22.9 seconds in the complete set (black dashed line), meaning 50% retweets happen within 23 seconds from last retweet. After sampling, the median increases almost 5-fold to 105.7 seconds (blue dashed line). For research that uses tweet inter-arrival time, this presents the risk of miss-calibrating models and of underestimating the virality of the cascades. Potential reach. Online influence is another well-studied phenomenon on Twitter, and one of its proxies is the number of followers of a user. We define potential reach as the total number of all observed retweeters' followers. This approximates the size of the potential audience for the root tweet. We compute the relative potential reach as the ratio of potential reach in the sample cascade against that in the complete cascade, and we plot the CCDFs in Figure 11(b). When observing cascades for as much as 14 days, 50% of the cascades have the relative potential reach below 0.544. This indicates that when using the sampled Twitter data, researchers can severely underestimate the size of the potential audience. Another common setting is to perform early prediction, i.e., after observing 10 minutes or 1 hour of each retweet cascade. Figure 11(b) shows that the relative potential reach is more evenly distribution for shorter time windows -21.0% cascades have relative potential reach below 0.25 and 33.7% cascades above 0.75 within 10 minutes span -comparing to the observation over 14 days (5.1% and 11.3%, respectively).

Conclusion
This work presents a set of in-depth measurements on the effects of Twitter data sampling. We validate that Twitter rate limit messages closely approximate the volume of missing tweets. Across different timescales (hour, minute, second, millisecond), we find that the sampling rates have distinct temporal variations at each scale. We show the effects of sampling across different subjects (entities, networks, cascades), which may in turn distort the results and interpretations of measurement and modeling studies. For counting statistics such as number of tweets per user and per hashtag, we find that the Bernoulli process with a uniform rate is a reasonable approximation for Twitter data sampling. We also show how to estimate ground-truth statistics in the complete data by using only the sample data.
Limitations. These observations in this paper apply to current Twitter APIs (as of 2020-03) and are subject to the changes of Twitter's proprietary sampling mechanisms. We are aware of that Twitter plans to release a new set of APIs in near future. Consistent with the current streaming APIs, the rate limit threshold for the new APIs is also set to 50 tweets per second (Twitter.com 2020b). Therefore, we believe the observations of this paper will hold. Practical implications and future work. This work calls attention to the hidden biases in social media data. We have shown effective methods for estimating ground-truth statistics, which allows researchers to mitigate the risks in their datasets without collecting the complete data. Our research also provides methods and toolkits for collecting sampled and complete data streams on Twitter. Our findings provide foundations to many other research topics using sampled data, such as community detection and information diffusion algorithms that are robust to data subsampling. Future works include measuring a larger set of activity and network measurements under data sampling, generalizing the results of this work to other social media platforms and data formats, and quantifying the robustness of existing network and diffusion models against data sampling.  Kyoto" as the Japanese location information 20 The lifecyle of a Youtube video: Phases, content and popularity filtered tweets containing keyword "youtube" OR ("youtu" AND "be")    To collect the complete streams, we split the same set of keywords into multiple streaming clients. The CYBERBULLYING and YOUTUBE datasets are respectively crawled by 8 and 12 clients based on different combinations of keywords and languages. We carefully choose the split criteria to ensure that each client would not be rate limited by much (ρ>99% for all subcrawlers). Table 12 and Table 13 list the statistics for all streaming clients of the two datasets.
Firstly, SAMPLED '15 receives up to 4 rate limit messages for each second. Figure 12(a) shows the milliseconds in the rate limit messages are not uniformly distributed -89% rate limit messages are emitted between millisecond 700 to 1,000. With a total of 55,420 rate limit messages, Figure 12(b) shows that {0,1,2,3,4} rate limit messages can be received every second. On the contrary, we obtain at most 1 rate limit message per second in the datasets crawled in 2019. Secondly, the integers in the rate limit messages are not increasing monotonically. This contradicts Twitter's official documentation that "Limit notices contain a total count of the number of undelivered Tweets since the connection was opened (Twitter.com 2020e)". Figure 13(a) shows the scatter plot of rate limit messages with the timestamp on the x-axis and the associated integer value on the y-axis. The above observations prompt us to believe that the rate limit messages (and streaming clients) are split into 4 parallel threads rather than 1. When the received messages are less than 4, one explanation could be that particular thread has delivered all tweets within it. We propose Algorithm 1, which maps rate limit messages to 4 monotonically increasing lists for estimating the number of undelivered tweets. We color the mapping results in Figure 13(b). From the 4,500 rate limit messages received between 2015-09-08 06:30 UTC and 2015-09-08 09:30 UTC, we estimate that 85,720 tweets are missing.  Figure 13: (a) Scatter plot of rate limit messages. x-axis: timestamp; y-axis: associated integer value. (b) Coloring rate limit messages into 4 monotonically increasing threads by using Algorithm 1.
To validate the 4-thread counters for rate limit messages, we obtain a complete data sample from a Twitter data reseller discovertext.com 6 . This company provides access to the Firehose service at a cost. We started two streaming clients simultaneously on 2017-01-06, one with the Twitter filtered streaming API, the other with the Firehose. We track the temporal tweet volumes at three level: (1) public filtered stream (blue); (2) filtered stream plus the estimated missing volume from rate limit messages (red); (3) the complete tweet stream from Firehose (grey). The missing volume is estimated by using Algorithm 1, which accounts the integers in rate limit messages onto 4 parallel counters. As shown in Figure 14, the red line and grey line input : rate limit messages output: multiple monotonically increasing lists A that consist of rate limit messages initialize the returned list of list A by the first element of rate limit messages; while not at end of messages do read the next rate limit message N extRate; read the last element from each of the existing lists A into P revRates;  If one uses the 1-thread counter to compute the missing volume, the total volume will be undercounted as the estimated missing volume now reduces to about 25%. This in turn makes the complete data stream appears to be much larger than the estimated total volume, which was what the researchers found in (Sampson et al. 2015). Based on the above observations, we believe that the discrepancies between our work and (Sampson et al. 2015) are a result of different implementation choices of the rate limit messages in 2015 and 2019.

D Minutely and secondly sampling rates
The temporal variations are much less prominent at the minutely and secondly levels, as shown in Figure

E Universal rank percentiles change
Concerning all users in our dataset (not just the most active 100 users), Figure 16 shows the true rank percentiles on the x-axis and the observed rank percentiles on the y-axis. The smaller the value is, the higher rank the user posits among the cohort. For an user that tweets 5 times in the complete set (displayed as the rightmost vertical line), their tweets appear on average 2.65 times in the sample set. The true rank percentile is 20.37%, and the observed rank percentile is 22.63% ± 11.07%. For an user that tweets 40 times in the complete set, their tweets appear on average 21.09 times in the sample set. The true rank percentile is 2.03%, and the observed rank percentile is 2.14% ± 0.58%. With a decreasing standard deviation, the percentiles of the higher ranked entities are more trustworthy.