LocusRank: Solving the "London Problem" via Social PageRank

TL;DR

When a user writes "London" on their profile, are they in the UK or Canada? LocusRank solves this by looking at their friends. By treating geographic interpretations as nodes in a graph and applying PageRank, the algorithm achieves over 84% accuracy in pinpointing a user's specific city, even when the surrounding social data is also ambiguous.

Background: The Context Vacuum

In traditional Natural Language Processing (NLP), we disambiguate "Paris" by looking for neighboring words like "Eiffel Tower" or "Texas Rangers." However, on social media profiles (Flickr, LiveJournal, Twitter), a location often stands alone. This Context Vacuum makes traditional toponym resolution fail.

The authors' core insight is that geography is social. Most people cluster their social ties geographically. Therefore, the "context" for your location isn't the words you write, but the (possibly ambiguous) locations your friends report.

Methodology: The Location Graph

LocusRank doesn't just look for the most frequent city among friends. Instead, it builds a Location Graph ($L_v$).

1. Interpretation Extraction

Using OpenStreetMap (OSM), the algorithm fetches the top 50 possible interpretations for every toponym in a user's social circle.

2. Weighted Voting

Links are created between interpretations based on administrative hierarchies:

• Country Match ($w_{co}=1$): Broadest connection.
• State Match ($w_s=2$): Moderate connection.
• City Match ($w_{ci}=3$): Strongest connection.

3. PageRank Centrality

Once the graph is built, PageRank identifies the "most important" nodes. If many of your friends have interpretations in "Texas, USA," the "Paris, Texas" interpretation for your profile will receive a high centrality score, winning over "Paris, France."

Figure: The Location Graph represents interpretations as nodes; links are weighted by administrative overlap.

Experiments: More Than Just Disambiguation

The authors tested LocusRank on 2,347 real-world profiles from Flickr and LiveJournal.

Key Findings:

• High Precision: Even on Flickr, where toponyms are "noisier," the Top-1 city accuracy reached 72% (93% for Top-5).
• Inference Power: The algorithm was tested on users who provided no location at all. By purely looking at friends, it predicted the correct city with 65% accuracy, significantly outperforming a standard frequency-based baseline.
• Friendship Type Matters: In LiveJournal, mutual "in-out" links (verified friendships) provided much better signals than one-way follows.

Figure: Performance across different degrees of match (Country, State, City).

Critical Insight: Collective Wisdom Over Individual Noise

The beauty of LocusRank lies in its ability to handle cascading ambiguity. It doesn't require "ground truth" for the friends; it allows the probabilistic overlap across an entire social network to converge on the correct answer.

However, the paper acknowledges a "U-shaped" performance curve regarding friend counts: having too few friends provides insufficient data, while having too many (e.g., bridge users or celebrities) introduces geographic "noise" that can dilute the PageRank signal.

Conclusion & Future Work

LocusRank demonstrates that social metadata is a high-fidelity proxy for geographic context. As we move toward more integrated social graphs, the next step—as the authors suggest—is collective disambiguation: solving the entire network's locations simultaneously rather than one user at a time.

Takeaway: In the world of metadata, your friends define your "where" as much as your "who."