A buzz and e-reputation monitoring tool for twitter based on galois lattices

Étienne Cuvelier, Albert BifetSPIRE 2011

TL;DR

This paper introduces a novel approach to monitoring Twitter "buzz" by using Galois Lattices (Formal Concept Analysis) to group related tweets, even when they have been modified by users. To make these complex mathematical structures readable, the authors propose a "topigraphic network of tags" that visualizes the most important conversation clusters as a 3D-inspired map.

What Problem Does This Paper Address?

In the fast-paced world of social media, tracking "e-reputation" isn't as simple as counting keywords. The authors identify a specific challenge they call the polymorphism of forwarded information.

When a tweet goes viral, it rarely stays identical. Users often edit retweets to add their own comments, include "via @user" tags, or truncate text to fit the 140-character limit (the standard at the time of writing). Traditional monitoring tools that rely on exact string matching or simple word frequencies often fail to see that these variations all carry the same "core" message. The authors sought a way to automatically identify the shared essence of these polymorphic tweets and present them in a way that a human analyst can actually understand.

Methods

The researchers turned to Formal Concept Analysis (FCA) and Galois Lattices.

  1. Data Structuring: They treat tweets as "objects" and the significant words within them as "attributes."
  2. Lattice Construction: By building a Galois Lattice, the system identifies every possible "concept"—a group of tweets that share a specific set of words. This naturally handles polymorphism: if five variations of a retweet all share a core sentence, the lattice will group them under a single concept representing that core information.
  3. Topigraphic Visualization: Standard lattices are notoriously difficult to read (often looking like a "spaghetti" of nodes and lines). The authors developed a topigraphic network of tags. They used the Fruchterman-Reingold algorithm for the layout and a bi-dimensional Gaussian probability density mixture to create a "topographic allegory."
    • Tops: General concepts with many tweets appear as "peaks."
    • Valleys: More specific sub-concepts appear further down.
  4. Lanes: Directed edges act as paths guiding the reader from general themes to specific details.

Datasets

The paper uses a small, illustrative dataset to prove the concept:

  • #ereputation Dataset: 50 tweets retrieved from a search for the hashtag "#ereputation."
  • While small, this dataset was sufficient to demonstrate how the tool handles various retweet styles and identifies the primary clusters of conversation surrounding the topic.

Key Insights and Ideas

  • FCA as a "Buzz" Detector: The "intent" of a concept in a Galois Lattice (the set of shared words) effectively represents the "core" of a viral message, regardless of how much "noise" users add during retweeting.
  • The Visualization Bottleneck: The authors realized that the mathematical elegance of Galois Lattices is useless if the output is a mess. Their "aha moment" was applying topographic map principles to network graphs.
  • Thresholding for Clarity: By only displaying concepts that appear in more than 10% of the dataset, they could filter out the "long tail" of unique, one-off tweets and focus on the actual "buzz."

Key Results

  • Polymorphism Handling: The tool successfully grouped variations of retweets (e.g., those starting with "RT @user" vs. those ending with "via @user") into coherent concepts.
  • Structural Discovery: In the #ereputation test, the tool identified three distinct, independent conversation clusters: one focused on professional branding (CVs), one on daily news summaries, and a large central cluster regarding a specific conference (#wikioconf).
  • Readability: The topographic map (Figure 9) proved significantly more intuitive than the raw lattice (Figure 6), allowing an observer to quickly see that "opinions" and "internauts" were the dominant sub-themes of the main search.

Limitations and Future Work

The authors acknowledge that the tool was at a prototype stage and identified several areas for growth:

  • Interactivity: The current version is a static map; future versions should allow users to click and "drill down" into specific sub-concepts.
  • URL Normalization: The system currently treats different shortened URLs (bit.ly vs. tinyurl) as different words, even if they point to the same page.
  • Sentiment Analysis: The authors plan to integrate sentiment detection to determine if a "buzz" is positive or negative (essential for e-reputation).
  • Scaling: While effective for 50 tweets, the computational complexity of Galois Lattices may require more optimized algorithms to handle the millions of tweets generated daily.

Summary updated

BibTeX
@inproceedings{cuvelier2011buzz,
  author = {Étienne Cuvelier and Albert Bifet},
  title = {{A buzz and e-reputation monitoring tool for twitter based on galois lattices}},
  booktitle = {SPIRE},
  year = {2011},
}
Figure