Tweeque: Decoding User Location through the Lens of Social Migration
Tweeque: Spatio-Temporal Analysis of Social Networks for Location Mining Using Graph Partitioning
The paper introduces Tweeque, a spatio-temporal location mining algorithm designed to predict a Twitter user's current city based solely on their social network graph. By utilizing graph partitioning (Normalized Cuts) to identify social cliques and a purity-based voting mechanism, it effectively distinguishes a user's current residence from past locations.
TL;DR
Predicting where a Twitter user lives is notoriously difficult because 85% of users hide their location. Tweeque solves this by analyzing "Social Cliques." By recognizing that people form new, geographically dense friend groups when they move (migration), the algorithm uses graph partitioning to separate current friends from old ones, achieving a 76.3% accuracy in city-level prediction.
The "Static Graph" Fallacy
Most traditional location mining tools treat a user's social circle as a static entity. However, people are mobile. Data from Facebook and the U.S. Census indicates that nearly 70% of social media users live away from their hometowns. If an algorithm simply averages the locations of all your friends, it will likely point to a place where you used to live or where you grew up, rather than where you are typing from today.
The core insight of Tweeque is that migration is a latent time factor. As time passes, old social circles become geographically dispersed, while your current city will manifest as a "pure" social clique—a group of people who are not only friends with you but also friends with each other and live in the same proximity.
Methodology: Cliques and Normalized Cuts
Tweeque operates on a three-stage pipeline:
1. Defining "Real" Friendship
On Twitter, "following" is often one-directional (e.g., following a celebrity). Tweeque defines true friendship strictly as bidirectional follows (A follows B AND B follows A). This filters out the noise of spammers and public figures.
2. Social Clique Identification
The algorithm represents a user's friends as a graph and uses the Shi-Malik Normalized Cut (NCut) algorithm to partition them.
The goal is to minimize the "cut" between groups while maximizing the volume within them. This mathematical approach effectively clusters friends into distinct real-world contexts: your college buddies, your current coworkers, and your childhood neighbors.
3. Purity-Based Voting
Once cliques are formed, the algorithm looks for the "purest" group. A clique where 90% of members live in San Francisco is a stronger indicator of current residency than a dispersed group spread across the country.
Figure: The data proves that as users age, the likelihood of them living in their hometown drops significantly, justifying the need for temporal analysis.
Experimental Results
The researchers tested Tweeque against a hand-annotated dataset of 1,000 users. Compared to content-based methods (which analyze text like "I'm at the beach"), Tweeque is significantly more robust.
| Method | City Accuracy | Country Accuracy |
|---|---|---|
| Content-Based | 35.6% | 52.3% |
| Tweethood | 72.1% | 80.1% |
| Tweeque | 76.3% | 84.9% |
The jump in accuracy highlights that who you know (and how they group together) is a much more reliable signal than what you say.
Figure: The Power Law of Friendship—Even in the digital age, the probability of friendship drops sharply as geographical distance increases.
Critical Analysis & Conclusion
Tweeque represents a pivot from simple "spatial mining" to "spatio-temporal mining." By treating graph structure as a proxy for time, it overcomes the lack of timestamps in social connections.
Limitations:
- The system relies on some of the user's friends having "public" locations to seed the voting process.
- It might struggle with "digital nomads" or users whose social circles remain entirely online and geographically agnostic.
Future Outlook: This work paves the way for deeper "Digital Sociology." In the future, similar graph partitioning could be used to detect not just where a person is, but their current life stage, profession, or even shifting political affiliations, all through the changing "purity" of their social cliques.