Source-linked AI summary
Geotagging One Hundred Million Twitter Accounts with Total Variation Minimization
Ryan Compton, David Jurgens, David Allen
TL;DR
Public Twitter data contains too little location information for many geographic social-media applications. This work frames social-network geotagging as total variation minimization and demonstrates a large-scale database of user locations constructed from publicly visible data.
Problem
Publicly available Twitter locations are sparse, limiting geographic social-media analytics and profile-based geotagging coverage to below 20% when nonsensical or ambiguous locations are ignored.
Method
The method constructs a bidirectional @mention network, formulates geotagging as a globally defined convex optimization using total variation, and estimates per-user accuracy from geographic dispersion.
Results
The study produces the largest database of Twitter user locations known in the literature using publicly visible data.
Takeaways & Limitations
A publicly constructable dataset of Twitter user locations opens the door for future research directions.
Abstract
from arXiv · showhide
Geographically annotated social media is extremely valuable for modern information retrieval. However, when researchers can only access publicly-visible data, one quickly finds that social media users rarely publish location information. In this work, we provide a method which can geolocate the overwhelming majority of active Twitter users, independent of their location sharing preferences, using only publicly-visible Twitter data. Our method infers an unknown user's location by examining their friend's locations. We frame the geotagging problem as an optimization over a social network with a total variation-based objective and provide a scalable and distributed algorithm for its solution. Furthermore, we show how a robust estimate of the geographic dispersion of each user's ego network can be used as a per-user accuracy measure which is effective at removing outlying errors. Leave-many-out evaluation shows that our method is able to infer location for 101,846,236 Twitter users at a median error of 6.38 km, allowing us to geotag over 80\% of public tweets.
I. INTRODUCTION
The paper addresses sparse public location data by inferring Twitter users’ locations from social ties, formulating geotagging as total variation minimization, and demonstrating the approach at massive scale.
- Motivation: Public Twitter locations are sparse, limiting geographic analysis of flu trends, linguistic patterns, elections, unrest, and disasters.Existing applications depend on physical user locations that are rarely publicly available.
- Motivation: Online friends often live nearby, enabling location inference from publicly known friend locations and avoiding content-based language difficulties.The approach relies on communicative locality and public Twitter metadata.
- Method: A globally defined convex optimization solves network geotagging by minimizing weighted geographic distances while fixing locations voluntarily disclosed by users.The objective uses geodesic distances and edge weights based on reciprocated @mentions.
- Motivation: Profile-based geotagging covers at most 63% of tweet volume with unambiguous locations and below 20% when nonsensical or ambiguous profiles are excluded.These results motivate using social-network information rather than relying solely on profile locations.
- Scope: The approach cannot estimate within-city motion and instead targets high-volume, static, city-level location inference.Training uses users who primarily tweet within the same radius, with median location treated as home.
- Accuracy: The method estimates per-user accuracy from ego-network geographic dispersion, allowing error control while coverage remains high under tight dispersion restrictions.This provides a confidence measure for filtering outlying errors.
- Scale: On a network of 110,893,747 users and 1,034,362,407 connections, the authors inferred locations for 101,846,236 users using distributed coordinate descent.The implementation uses Apache Spark for scalable parallel optimization.
II. BACKGROUND AND RELATED WORK
Social-media geotagging research uses two prevalent approaches: language-based methods and network-based methods.
- Two major classes of social-media geotagging solutions are language-based and network-based.
- Language-based methods infer location from location-specific terms and related tweet features.
- Network-based methods infer location through users’ social connections.
A. Language-based Geotagging
Language-based geotagging uses textual and profile features but faces geographic-language assumptions and limited worldwide extensibility, while network methods infer locations from friends’ known locations.
- 68% city-accuracy was reported for 9,551 test users by the cited content-based state-of-the-art method.
- Language-based geotagging requires geographically distinct dialects that support accurate location inference.
- Network-based geotagging can infer locations from friends’ known locations using public data alone.
- The paper cannot compare its method with IP-based Twitter geolocation because Twitter users’ IP addresses are not public.
- Prior work also used social ties, network structure, language processing, and landmark users across Flickr, Twitter, United States, and Korean settings.
- Robust statistics are used to estimate center and spread because averages can be sensitive to outliers in social data.
III. METHOD
The method constructs a bidirectional @mention network, establishes ground-truth locations from GPS and profiles, and assigns unknown users locations through network-based inference.
- A. Data and Network Construction: A bidirectional @mention network represents users as vertices and reciprocated mentions as weighted edges.Weights use the minimum number of reciprocated @mentions between users; this avoids Twitter API rate limiting.
- A. Data and Network Construction: 1,034,362,407 reciprocated-mention edges connect 110,893,747 users in the experimental network.The data came from a 10% public-tweet sample collected between April 2012 and April 2014.
- B. Ground Truth User Locations: The location function f assigns each user an estimated physical location, with known users separated from unknown users.GPS-tagged locations use the l1-multivariate median of users’ tweeted locations.
- B. Ground Truth User Locations: 13,899,315 users had at least three GPS tweets, and filtering mobile users left 12,435,622 potential GPS-known users.Users with GPS-location median absolute deviation over 30km were filtered out.
- B. Ground Truth User Locations: 15,360,494 additional users received home locations from unambiguous, recent self-reported profile locations.Self-reports older than 90 days and profiles listing several locations were excluded; GPS locations took precedence.
- B. Ground Truth User Locations: 24,545,425 users had ground-truth locations from GPS or self-reports.
C. Global Optimization Algorithm
The algorithm uses geographic proximity among socially connected users and parallel coordinate descent to optimize location estimates at large scale.
- A majority of GPS-known users have at least one GPS-known friend within 10km.The observed contact pattern indicates that online social ties typically connect users living near each other.
- The optimization models proximity by minimizing a nondifferentiable total-variation objective over the network.Because the functional is nondifferentiable, finding a global minimum is challenging.
- At each iteration, every user’s location is simultaneously updated to the l1-multivariate median of their friends’ locations.Results are communicated only after all updates in the iteration finish.
- Parallel coordinate descent provides the concise algorithmic procedure used to solve the optimization.
D. Individual Error Estimation
The method estimates each user's geolocation error from the geographic dispersion of friends and suppresses updates when that dispersion is too large. Its optimization is implemented as parallel coordinate descent for total variation minimization, with constraints preserving known locations.
- Individual Error Estimation: Users with globally dispersed friends should not have their locations inferred by this approach.The method is intended for users whose contacts are geographically close.
- Individual Error Estimation: The per-user error estimate is the median absolute deviation of inferred friend locations.This robust dispersion estimate is incorporated into the optimization as an additional parameter, γ.
- Individual Error Estimation: Locations are not updated when friend dispersion exceeds the selected threshold, preventing unreliable locations from propagating.The algorithm initializes known locations and iteratively updates only users passing the dispersion restriction.
- Individual Error Estimation: Each coordinate update minimizes a weighted l1 multivariate median of neighboring locations.Removing the restriction on γ reduces this computation to the previously described Spatial Label Propagation algorithm.
- Individual Error Estimation: The algorithm is a parallel coordinate descent method designed to minimize total variation.Convergence analysis is complicated by spherical metrics and the requirement that ground-truth users retain their initial locations.
E. Implementation Remarks
The implementation distributes the algorithm and its network data across Spark cluster memory. RDD operations parallelize computation and coordinate updated locations through joins and grouped adjacency lists.
- Implementation Remarks: Apache Spark implements the algorithm using resilient distributed datasets and arbitrary Scala code.Spark distributes data in cluster memory and uses available cluster CPU resources.
- Implementation Remarks: Updated user locations are communicated by joining the edge list and grouping results into the next adjacency list.The parallel loop can be implemented with map and filter operations.
- Implementation Remarks: More advanced distributed graph frameworks, including Pregel or GraphX, are proposed as future implementation directions.The current implementation uses Spark-based RDD operations.
F. Mobility Considerations
The method targets static, city-level inference and can misclassify fast-moving users with large activity radii. GPS-based mobility analysis finds that large radii exist but are atypical, while unusually high speeds identify problematic accounts.
- Mobility Considerations: Fast-moving users with large activity radii may be tagged incorrectly because the technique performs only static location inference.The study evaluates this assumption using activity radii from GPS-annotated tweets.
- Mobility Considerations: The first iterations produce the most accurate geotags and the highest coverage.Table I reports geolocated users and accuracy separately for each iteration.
- Mobility Considerations: 13,899,315 users with at least three GPS-annotated tweets were analyzed using median tweet locations as home locations.Mean and median distances from home define the empirical activity-radius distributions.
- Mobility Considerations: Large activity radii exist but are atypical among Twitter users.The analysis uses empirical cumulative distribution functions of mean and median distances from home.
- Mobility Considerations: 0.02 km/h is the median user speed, rising to 0.20 km/h for users with activity radii over 20 km.The corresponding average speeds are 233.63 km/h and 1024.04 km/h, respectively.
IV. RESULTS
The results use five iterations of the algorithm on the bidirectional @mention network, with γ set to 100 km after experiments with alternative values.
- Results: 5 iterations on the bidirectional @mention network produced the reported results, with γ = 100 km.The parameter was selected after experiments with different values, and high coverage could be obtained sooner.
A. Coverage
The method substantially expands Twitter geotagging coverage, especially for active users, while ego-network dispersion controls help remove outlying location errors. It geotags 81.9% of sampled tweets and achieves a 6.38 km median error on the evaluated test users.
- Coverage: Users who quickly stop tweeting form a large group that is difficult to geocode with the proposed method.Figure 5 links the concentration of low-activity users to the coverage pattern in Figure 4.
- Coverage: 81.9% of sampled tweets were geotagged, exceeding the maximum possible coverage from unambiguous nonempty profile locations.The sample contained 37,400,698,296 tweets from 359,583,211 users.
- Coverage: The method’s geolocation probability increases dramatically with activity, whereas GPS and self-reported location probabilities change little.The figure compares geolocation fractions across activity levels using method-based geotagging, GPS, and self-reports.
- Accuracy: 6.38 km was the median error for 971,731 inferred test users after five algorithm iterations with γ = 100km.The evaluation used a 10% holdout from 12,297,785 GPS-located users; mean error was 289.00km.
- Accuracy: 89.7% of test users were accurate to city resolution when reverse-geocoded to cities with populations above 5,000.The result covered 770,498 test users, and the paper notes that reverse-geocoding can itself introduce errors.
V. CONCLUSION
The paper frames Twitter geotagging as global convex optimization and adds a per-user accuracy estimate based on ego-network dispersion. Demonstrated at scale, the approach produces a large publicly constructible dataset while keeping errors small through accuracy filtering.
- Conclusion: The method formulates home-location inference for millions of Twitter users as a total variation-based global convex optimization.This connects network geotagging with established convex optimization techniques.
- Conclusion: A novel per-user accuracy estimate uses ego-network information to help ensure that geotagging errors remain small.The estimate is presented as an additional technique beyond the location-inference algorithm.
- Conclusion: γ = 100km reduces mean error to 200km while retaining 80% of users in the geolocation database.Median error is less responsive to γ, indicating that the restriction primarily controls outlying errors.
- Conclusion: 101,846,236 user locations were inferred from publicly visible data at a scale described as the largest and most accurate dataset known to the authors.The authors state that public-data construction opens future research directions.