PaperlayerView exact revision on arXiv

Source-linked AI summary

Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph

David R. Bild, Yue Liu, Robert P. Dick, Z. Morley Mao, Dan S. Wallach

arXiv:1402.2671v1cs.SIphysics.soc-ph

TL;DR

Earlier Twitter research focused on the follower graph or individual cascades, leaving aggregate behavior and the retweet graph less characterized. This paper quantifies user-behavior distributions and retweet-network structure, finding distinct finite-sample activity patterns and a retweet graph whose structure is consistent with closer correspondence to real-world relationships and trust.

  • Problem

    Prior Twitter analysis centered on the social followers graph and individual cascades, while aggregate user behavior and the retweet graph had received little quantitative characterization.

    Source: §I · p. 1

  • Method

    The study characterizes lifetime tweet, tweet-rate, and inter-tweet distributions and analyzes the retweet graph using Twitter datasets.

    Source: §I · p. 1, §II · p. 2, D. 10% Sample (Gardenhose) Dataset · p. 2

  • Results

    Lifetime tweets follow a type-II discrete Weibull, finite-sample tweet and retweet rates have a lognormal cutoff, inter-tweet intervals have an exponential cutoff, and the retweet graph is small-world and scale-free with stronger clustering and less disassortativity than the follower graph.

    Source: §I · p. 2

  • Takeaways & Limitations

    The retweet graph’s structure is consistent with better reflecting real-world relationships and trust, and its scale-free, small-world properties support generating random graphs for empirical spam-detection studies.

    Source: G. Summary · p. 12

    Explaining the causes of the retweet-graph differences and establishing the conjecture that retweets better mirror real-world relationships and trust remain beyond the paper’s scope.

    Source: §VI · p. 8, §IX · p. 15

Abstract

from arXiv · show

Most previous analysis of Twitter user behavior is focused on individual information cascades and the social followers graph. We instead study aggregate user behavior and the retweet graph with a focus on quantitative descriptions. We find that the lifetime tweet distribution is a type-II discrete Weibull stemming from a power law hazard function, the tweet rate distribution, although asymptotically power law, exhibits a lognormal cutoff over finite sample intervals, and the inter-tweet interval distribution is power law with exponential cutoff. The retweet graph is small-world and scale-free, like the social graph, but is less disassortative and has much stronger clustering. These differences are consistent with it better capturing the real-world social relationships of and trust between users. Beyond just understanding and modeling human communication patterns and social networks, applications for alternative, decentralized microblogging systems-both predicting real-word performance and detecting spam-are discussed.

I. INTRODUCTION

The paper fills gaps in quantitative descriptions of aggregate Twitter behavior and examines the retweet graph alongside established follower-graph analyses. It introduces datasets and reports distinct patterns in tweet activity and retweet-network structure.

I. INTRODUCTION

  • Prior work emphasized the follower graph or a small fraction of tweets in individual cascades, leaving basic aggregate behavior distributions underdescribed.The paper focuses on lifetime tweets, tweet rates, and inter-tweet times; it also examines retweet behavior and the retweet graph.Source: §I · p. 1
  • Lifetime tweet counts follow a type-II discrete Weibull, tweet and retweet rates show a finite-sample lognormal cutoff, and inter-tweet durations have a power law with exponential cutoff.The rate distributions are asymptotically power law; high rates are much rarer in finite samples than that asymptote suggests.Source: §I · p. 2
  • The retweet graph is small-world and roughly scale-free like the follower graph, but is less disassortative and more highly clustered.These differences are consistent with the retweet graph better reflecting real-world relationships and trust.Source: §I · p. 2

II. DATASETS

  • The main dataset is a 10% sample of tweets sent from June through September 2012, supplemented with other datasets as needed.The authors note that API limits and terms of service prevent collection and sharing of one complete dataset suitable for all queries.Source: §II · p. 2

A. 2009 Social Graph

  • The follower-graph comparisons use the 2009 snapshot covering 41.7 million users and 1.47 billion relations, while lifetime contributions use account ages, last-tweet dates, and tweet counts for 1,318,683 users.Of those users, 525,779 were classified as inactive after not tweeting in the preceding six months.Source: A. 2009 Social Graph · p. 2, B. Lifetime Contribution Dataset · p. 2

C. SNAP Tweet Dataset

Because tweet sampling misses many infrequent users, the paper estimates population distributions from sampled observations rather than relying on direct scaling. It applies an expectation-maximization procedure and finds that its corrected distribution differs substantially from both the observed and scaled versions.

D. 10% Sample (Gardenhose) Dataset

  • The 10% Gardenhose dataset is a uniform random sample of tweets sent during June–September 2012, with retweets identified from metadata and message syntax.A tweeter sends an original message, a retweeter forwards a previous tweet, and a retweetee is the user whose tweet was forwarded.Source: D. 10% Sample (Gardenhose) Dataset · p. 2
  • The sample is biased toward frequent users, and most users with fewer than ten tweets are absent, motivating quantitative population correction.The paper uses a separate 467-million-tweet 2009 SNAP collection for inter-tweet intervals because that analysis requires consecutive tweets.Source: D. 10% Sample (Gardenhose) Dataset · p. 2, C. SNAP Tweet Dataset · p. 2

E. Estimating Population Distributions from the 10% Sample Dataset

  • The EM procedure estimates the hidden population frequencies by modeling how users with i tweets contribute observed counts j under binomial sampling.The paper describes maximum-likelihood estimation and uses expectation maximization because the likelihood is not analytically tractable.Source: E. Estimating Population Distributions… · p. 3
  • The EM-estimated population distribution differs substantially, especially in the lower decades, from the observed sample and the naive 10×-scaled sample.Figure 1 compares the observed 10% sample, scaling each observed count j to 10j, and the EM population estimate.Source: E. Estimating Population Distributions… · p. 3, Figure 1 · p. 3

III. DISTRIBUTION OF LIFETIME TWEETS

Lifetime tweet counts are heavy-tailed but do not follow a pure power law: the observed distribution is better characterized by a discrete Weibull with a power-law hazard. The section also shows how equal-count binning and related fitting practices can obscure upper-tail cutoffs.

A. Critique of Previously-Reported Power Law Behavior

  • Equal-count binning and regression-based fitting can hide a real upper-tail cutoff, as demonstrated when those methods make Twitter data appear to fit a power law.The authors recommend logarithmic binning, maximum-likelihood fitting, and goodness-of-fit tests against the empirical distribution function instead.Source: A. Critique of Previously-Reported… · pp. 3–4
  • The authors suggest earlier online-community distributions may also contain cutoffs, but unavailable original datasets prevent proving that conclusion.Their Twitter example shows equal-count binning obscuring the known cutoff and the resulting power-law fit appearing acceptable.Source: A. Critique of Previously-Reported… · p. 4

B. Lifetime Tweets Follow a Weibull Distribution

  • The hazard function is power law, giving the discrete Weibull characterization rather than a pure power-law distribution.The hazard is the probability that a user with x contributions quits without making another contribution; Wilkinson called the related pattern participation momentum.Source: B. Lifetime Tweets Follow a Weibull… · p. 4
  • The lifetime-tweet distribution has a type-II discrete Weibull fit with β = 0.17 and α = 1.32, with slight upper-tail deviation attributed to Twitter rate limits.The rate limits shift users who would exceed roughly 200,000 tweets into that tail region.Source: B. Lifetime Tweets Follow a Weibull… · p. 4, Figure 2 · p. 4

C. Interpreting the Hazard Function as Participation Momentum

The power-law hazard is interpreted as participation momentum: each contribution is associated with effort, while the model’s β parameter represents momentum gain. The authors relate this interpretation to feedback and compare contribution effort across platforms.

C. Interpreting the Hazard Function as Participation Momentum

  • Tweeting appears more taxing than voting on Digg stories but less taxing than commenting on Bugzilla reports, based on α.The passage interprets α as a measure of the effort needed to contribute.Source: C. Interpreting the Hazard Function as… · p. 4
  • The hazard’s decreasing trend means users who have tweeted more are more likely to tweet again, consistent with participation momentum.The power-law parameters are calculated from Table III rather than fitted to the plotted data.Source: C. Interpreting the Hazard Function as… · p. 4, Figure 3 · p. 5
  • Tweet rate is essentially uncorrelated with lifetime contributions, while age correlates negatively with tweet rate, arguing against age as the driver of momentum.The reported correlations are τ = −0.0067 for tweet rate versus lifetime contributions and τ = −0.5687 for tweet rate versus age.Source: C. Interpreting the Hazard Function as… · pp. 4–5
  • The authors conjecture that viewer feedback, such as retweets and replies, may accelerate or decelerate momentum gain; refining this interpretation remains future work.They suggest β represents momentum gain per contribution.Source: C. Interpreting the Hazard Function as… · p. 5
  • The power-law hazard leads to a Type-II discrete Weibull distribution for lifetime contributions.The summary attributes α to contribution effort and β to momentum gain.Source: C. Interpreting the Hazard Function as… · p. 5

IV. DISTRIBUTION OF TWEET RATES

The tweet-rate distribution has a heavy-tailed form with a finite-sample cutoff that appears lognormal. The authors use an analytical approximation and reject DPLN as an adequate account of the lower tail.

A. An Analytical Approximation of the Tweet Rate Distribution

  • The empirical distribution has two heavy-tailed regimes meeting near 2,000 tweets, with the crossing point increasing with the square of the sample period.The phase change is attributed to sample-period length.Source: A. An Analytical Approximation of the… · p. 5
  • The analytical approximation fits a lognormal cutoff with β = 1.13, µ = 7.6, σ = 1.06, and c = 0.19.The passage describes the upper tail as heavier than a common exponential cutoff.Source: A. An Analytical Approximation of the… · pp. 5–6

B. The Distribution is Not Double Pareto–Lognormal

  • DPLN fits poorly in the lower tail because the observed slope, −1.13, is steeper than its permitted minimum slope of −1.The call-distribution data shows a similar mismatch.Source: B. The Distribution is Not Double… · p. 6
  • The upper-tail data cannot distinguish a lognormal from a power law, so the authors favor the lognormal form for its simpler parameterization.The passage notes that real-world power laws often exhibit a cutoff.Source: B. The Distribution is Not Double… · p. 6

C. An Urn Process Generating the Tweet Rate Distribution

An urn process models how tweet counts evolve as users enter a sample and existing users receive further tweets. Its simulations reproduce the observed finite-sample phase change, while the asymptotic distribution approaches a Pareto form.

C. An Urn Process Generating the Tweet Rate Distribution

D. Distributions of Retweeter and Retweetee Rates

Twitter’s retweet behavior combines distinct rate patterns with inter-tweet intervals described by a power law with an exponential cutoff. The retweet graph is characterized as small-world and scale-free, and its analysis uses corrections for edge sampling.

D. Distributions of Retweeter and Retweetee Rates

  • Retweeter rates show dynamic behavior similar to tweet rates, while retweetee rates extend further right and have slopes more consistent with pure preferential attachment.The average retweet behavior rate is about 2× lower; the authors attribute retweetee growth to preferential attachment.Source: D. Distributions of Retweeter and… · p. 7

V. DISTRIBUTION OF INTERTWEET DURATIONS

  • The inter-tweet interval distribution follows a power law with an exponential cutoff, with fitted exponent α ≈ 0.8 and cutoff τc ≈ 8.1 d.Grouping users by total tweets and scaling by each group’s average interevent time collapses the distributions to one curve.Source: §V · pp. 7–8, Figure 8 · p. 8, Figure 7 · p. 8

VI. CHARACTERISTICS OF THE RETWEET GRAPH

  • The retweet graph is small-world and scale-free, like the social following graph, and its reported metrics can support generating random retweet graphs.The characterization reports R-MAT parameters a = 0.52, b = 0.18, c = 0.17, d = 0.13.Source: §VI · p. 8

A. Analyzing a Random Subsample of the Retweet Graph

  • The retweet graph is built from a 10% sample, with each edge treated as included at 10% probability for simplicity.The sample is weighted by retweet count, but 60% of edges have one retweet and 98% have fewer than ten; the analysis corrects measured properties with an EM-based method when possible.Source: A. Analyzing a Random Subsample of the… · p. 8, Figure 9 · p. 9

B. Degree Distributions

The retweet graph has heavy-tailed degree distributions, low reciprocity, and short paths. Compared with the follower graph, it is more assortative, with neutral in-degree assortativity and high out-degree assortativity.

B. Degree Distributions

  • The retweet graph’s upper-tail exponents are αin = 2.2 and αout = 3.75, with higher in-degree variance than out-degree variance.The authors describe the two-phase power law as a dynamic effect of adding nodes and preferentially attaching new edges; the higher out-degree exponent reflects extensivity not being inherently preferential.Source: Figure 10 · p. 9, B. Degree Distributions · p. 9

C. Reciprocity

  • Retweet reciprocity is 11.1%, below the Twitter follow graph’s 22.1%, consistent with retweeting being more discriminating than following.The authors note that malicious nodes can establish many outgoing links but have little control over incoming structure.Source: C. Reciprocity · p. 9

D. Average Shortest Path Length (Degree of Separation)

  • The estimated retweet-graph average path length is 4.8 and its 90th-percentile effective diameter is 8.5, with the difference from the follower graph within estimation error.The full-graph distribution is estimated by correcting the 10% edge-sampled graph using a 1.5× adjustment.Source: Figure 11 · p. 10, D. Average Shortest Path Length… · p. 10

E. Assortativity (Node Degree Correlation)

  • The retweet graph is more assortative than the weakly disassortative follower graph, with near-neutral in-degree measures and high out-out assortativity.High out-out assortativity indicates extensive retweeters retweet each other, while the authors note they are not tightly clustered.Source: Figure 13 · p. 10, E. Assortativity (Node Degree… · pp. 10–11

F. Clustering Coefficient

The retweet graph’s clustering is substantially stronger than the follower graph’s across most directed triplet measures. The authors also find frequent transitive retweeting and caution that their sample-based estimator is biased, though it performs well on large samples.

F. Clustering Coefficient

  • Clustering is significantly more prominent in the retweet graph than in the social following graph, except for the in coefficient.Cycle clustering is identified as the measure that should best reflect true clustering in underlying social groups and interest topics.Source: Figure 16 · p. 11, F. Clustering Coefficient · p. 11
  • The sample clustering estimator is biased because triplets are not independent and edges may concentrate toward open or closed triplets, but it performs well on large samples.The estimator accounts for triplet inclusion probabilities under edge sampling.Source: F. Clustering Coefficient · p. 11
  • Transitive retweeting yields Cmiddleman = 0.32 and Cout = 0.29, meaning about 30% of these possible two-degree retweet relationships exist.These coefficients reflect cases where one user retweets another user’s retweet, often closing the triplet.Source: F. Clustering Coefficient · p. 12

G. Summary

The paper presents the retweet graph as a potentially useful signal for decentralized systems and spammer detection. It discusses how behavioral distributions may inform system design and proposes local whitelisting based on retweet-graph connectivity.

G. Summary

  • The retweet graph’s clustering and assortativity are closer to real-world networks than typical online networks, suggesting it may better capture real-world relationships and serve as a trust proxy.The authors state that fully treating this conjecture is beyond the paper’s scope.Source: G. Summary · p. 12

VII. IMPLICATIONS FOR THE DESIGN OF DECENTRALIZED MICROBLOGGING ARCHITECTURES

  • Decentralized microblogging designs must account for heavy-tailed interevent times, two-phase tweet rates, and power-law long-term rates when modeling delivery, resource allocation, and storage.The authors warn that standard Poisson interevent distributions underpredict durations, while long-term power-law rates create archiving and retrieval challenges.Source: §VII · p. 12

VIII. LEVERAGING THE RETWEET GRAPH FOR SPAMMER DETECTION

  • The proposed spammer-detection approach uses retweet-graph structure because decentralized, censorship-less networks require filtering to be applied individually and locally.The approach focuses on sender classification, since short microblog messages make content analysis difficult.Source: §VIII · p. 12, A. Approach Overview and Background · p. 12

A. Approach Overview and Background

  • Participants classify users by distance from their own root and maximum flow in a partial retweet graph, then whitelist users classified as non-spammers.The graph is built from message histories; a new user can bootstrap by copying a trusted friend’s history or explicitly whitelisting friends.Source: A. Approach Overview and Background · p. 13

B. Performance on the Twitter Retweet Graph

The 10% retweet-graph sample shows that distance is correlated with spammer tendencies, while missing edges prevent connectivity from distinguishing benign from spam pairs. The authors therefore turn to synthetic graphs to test the combined classifier.

B. Performance on the Twitter Retweet Graph

  • The 10% graph sample omits 90% of edges, leaving most non-spammer paths absent and making it suitable to demonstrate hypothesized differences, not full-path performance.The authors state that connectivity shows no correlation because most pairs with one to ten original independent paths have zero or one sampled paths.Source: B. Performance on the Twitter Retweet… · pp. 13–14
  • A distance-only classifier achieves 75% TPR and 25% FPR on pairs with an extant source node.The ground truth labels are removed and extant accounts, with most removed users believed to be spammers.Source: B. Performance on the Twitter Retweet… · p. 14
  • Connectivity cannot distinguish benign pairs linked by many original paths from spam pairs linked by few, so the authors test the combined classifier on synthetic graphs.In the sampled graph, most pairs with one to ten independent paths in the original have only zero or one paths.Source: B. Performance on the Twitter Retweet… · p. 14

C. Performance on Synthetic Retweet Graphs

The paper evaluates retweet-graph spam detection on synthetic graphs generated with a modified R-MAT process. Under specified edge-density and retweet conditions, the classifier achieves high detection rates, while network size and clustering constrain where the approach applies.

C. Performance on Synthetic Retweet Graphs

  • The modified R-MAT model creates scale-free, small-world graphs while assigning fewer benign-to-spammer edges to model non-spammers rarely retweeting spammers.It divides the adjacency matrix into benign/benign, spammer/spammer, and spammer/benign quadrants, then recursively places edges using probabilities a, b, c, and d.Source: C. Performance on Synthetic Retweet… · p. 14
  • Because edge counts are expected to grow linearly with users, the density requirement limits network size; larger settings require classification within sufficiently dense clusters.The paper estimates that average out-degree 75 supports 25,000 participants, and warns that users outside their own cluster may be identified as spammers.Source: C. Performance on Synthetic Retweet… · pp. 14–15, Figure 20 · p. 15
  • Lower benign edge density raises false positives, while more benign-to-spammer edges per spammer lowers true positives; the latter sensitivity grows with edge density.The simulations hold spammer-to-benign and spammer-to-spammer densities equal to the benign-to-benign density.Source: C. Performance on Synthetic Retweet… · p. 15
  • Greater than 98% TPR and less than 5% FPR are achieved when fewer than one-tenth of spammers are retweeted and benign edge density is at least 0.3%.The paper gives 25,000 participants and average node degree 75 as the community-sized example; larger networks work best within denser sub-clusters.Source: C. Performance on Synthetic Retweet… · p. 15

IX. CONCLUSION

  • The conclusion presents spam detection through low retweet-graph connectivity as a contribution, while identifying the causes of structural differences from the followers graph as an open problem.The authors conjecture that retweets more closely mirror real-world relationships and trust.Source: §IX · p. 15

APPENDIX A PROCEDURES FOR IDENTIFYING RETWEETS

The appendix describes identifying retweets from user-written syntax or Twitter API metadata, then presents material for deriving an EM maximization procedure.

APPENDIX A PROCEDURES FOR IDENTIFYING RETWEETS

  • User-written retweets are detected by matching forms such as “RT@username,” “retweeting username,” or “via username” with a regular expression.Retweets represented in Twitter’s backend schema are instead identified through the API.Source: Appendix A · pp. 15–16

APPENDIX B DERIVATION OF THE EM METHOD

  • The EM derivation states a likelihood to maximize, an iterative maximization step, and a normalization constraint on the φ_i values.It also gives a matrix form for faster computer implementation.Source: Appendix B · p. 16
  • The appendix also expresses the original frequencies in terms of the derivation’s model quantities.Source: Appendix B · p. 16
Loading 1402.2671v1…