A Framework for Discovering Evolving Domain Related Spatio-Temporal Patterns in Twitter

Yan Shi, Min Deng, Xuexi Yang, Qiliang Liu, Liang Zhao, Chang-Tien Lu

TL;DR

This paper introduces a novel framework for identifying evolving spatio-temporal patterns within Twitter data, specifically focusing on events related to a particular domain like civil unrest. By combining dynamic query expansion with advanced spatial and spatio-temporal clustering techniques, the method can uncover how these patterns emerge and change over time, offering a deeper understanding of real-world events.

What Problem Does This Paper Address?

The vast amount of data generated on social media platforms like Twitter presents a significant challenge for extracting meaningful insights. While existing methods can detect spatio-temporal hotspots or clusters, they often fail to capture the dynamic, evolving nature of events. For instance, a civil unrest event doesn't just appear; it develops, shifts, and potentially fades. This paper addresses the gap in understanding how these spatio-temporal patterns evolve over time, moving beyond static snapshots to reveal the underlying processes. The authors highlight that previous research often focuses on detecting fixed patterns or simply identifying outliers, neglecting the temporal evolution of these phenomena.

Methods

The proposed framework consists of two main parts:

  1. Domain Related Twitter Event Detection:
    • Dynamic Query Expansion: This technique goes beyond simple keyword matching. It leverages a "Twitter information graph" to identify hidden relationships between tweets and features (users, terms, hashtags). By starting with a "seed query" (initial keywords), the system iteratively expands the query to capture more relevant tweets, even those that don't explicitly contain the initial keywords but are semantically linked. This is achieved through a weighted system that reflects the relevance of features and tweets to the target domain.
  2. Spatio-Temporal Twitter Event Extraction: Tweets identified through dynamic query expansion, along with their geo-location and time information, are then defined as spatio-temporal Twitter events.
  3. Evolving Spatio-Temporal Patterns Discovery:
    • Spatial Distribution Pattern Detection: This step uses a multi-constrained Delaunay triangulation approach. This method is designed to overcome limitations of standard spatial clustering and outlier detection by hierarchically identifying and removing different types of "long edges" in the triangulation. These edges represent relationships between points that might obscure the true spatial clusters and outliers. The process identifies global, local, and inner spatial outliers and clusters based on the volume of connected sub-graphs.
  4. Spatio-Temporal Clustering: This is the core of the "evolving" aspect. It builds upon the identified spatial patterns by considering spatio-temporal neighborhoods. This involves defining spatial neighborhoods (based on proximity in the Delaunay triangulation) and temporal neighborhoods (based on time windows). By combining these, spatio-temporal neighborhoods are constructed, and then spatio-temporal connected graphs are analyzed to discover evolving spatio-temporal clusters (STC), outlier points (STOP), and outlier regions (STOR). These collectively form the "evolving spatio-temporal patterns."

Datasets

The study utilizes a real-world Twitter dataset related to "civil unrest" in Mexico.

  • Dataset Source: The data was purchased from www.datasift.com, representing 10% of tweets sent between June 21, 2012, and May 31, 2013, across 10 Latin American countries.
  • Case Study Focus: A specific subset from June 21 to September 1, 2012, in Mexico was selected.
  • Data Cleaning: Tweets with significant errors (e.g., published in the ocean) were removed.
  • Ground Truth: A Gold Standard Report (GSR) from http://www.mitre.org/, based on influential newspapers and expert input, provided significant event information for validation.
  • Seed Query: 10 tweets related to civil unrest were selected by domain experts to initiate the dynamic query expansion.

Key Insights and Ideas

  • Beyond Static Hotspots: The paper convincingly argues that understanding the evolution of spatio-temporal patterns is crucial, not just identifying static clusters or outliers. Events unfold over time, and this temporal dimension is key to their interpretation.
  • Hidden Relationships in Tweets: The dynamic query expansion highlights that semantically related tweets can be missed by simple keyword searches. Capturing these hidden relationships is vital for comprehensive event detection.
  • Delaunay Triangulation for Nuanced Spatial Analysis: The multi-constrained Delaunay triangulation approach is a clever way to disentangle complex spatial structures, allowing for the identification of different types of clusters and outliers that might otherwise be masked.
  • Evolving Patterns as Predictors: The identified evolving spatio-temporal patterns (STC, STOP, STOR) are shown to evolve into the final spatial distribution patterns, suggesting they can offer insights into the precursors and development of events.

Key Results

  • The proposed framework successfully extracted spatio-temporal Twitter events related to "civil unrest" in Mexico.
  • Experimental results demonstrated the effectiveness of the framework in discovering evolving spatio-temporal patterns.
  • Comparisons with existing methods (ST-DBSCAN and STSNN) showed that the proposed method could better capture the evolving nature of patterns and their relationship to final spatial distributions.
  • The analysis of evolving spatio-temporal patterns revealed how parameters like d (spatial neighborhood size) and ε (temporal window size) influence the extent and nature of pattern evolution, with larger values leading to wider and more continuous extensions.
  • The identified patterns were found to be highly consistent with significant events reported in the Gold Standard Report, validating the method's ability to capture real-world occurrences. For example, specific spatio-temporal clusters and outliers were found to align with reported events in cities like Ciudad de México, Pachuca de Soto, and Monterrey.

Limitations and Future Work

  • Data Quality: The authors acknowledge that errors and biases inherent in social media data (e.g., "published in the ocean" tweets, population bias) can influence detection results. Future work will focus on analyzing data quality and incompleteness.
  • Modifiable Temporal Unit Problem (MTUP): The impact of different time window widths on detection results is recognized. Future research will investigate optimal time window selection considering MTUP and specific applications.
  • Multi-Dataset and Multi-Domain Analysis: Handling spatio-temporal data from multiple datasets with varying representations, distributions, scales, and densities is a significant challenge. Future work aims to address this.
  • Geographical Visualization: Developing methods for presenting complex analyzed results vividly and comprehensibly is an area for future development.

Summary updated

Abstract

In massive Twitter datasets, tweets deriving from different domains, e.g., civil unrest, can be extracted to constitute spatio-temporal Twitter events for spatio-temporal distribution pattern detection. Existing algorithms generally employ scan statistics to detect spatio-temporal hotspots from Twitter events and do not consider the spatio-temporal evolving process of Twitter events. In this paper, a framework is proposed to discover evolving domain related spatio-temporal patterns from Twitter data. Given a target domain, a dynamic query expansion is employed to extract related tweets to form spatio-temporal Twitter events. The new spatial clustering approach proposed here is based on the use of multi-level constrained Delaunay triangulation to capture the spatial distribution patterns of Twitter events. An additional spatio-temporal clustering process is then performed to reveal spatio-temporal clusters and outliers that are evolving into spatial distribution patterns. Extensive experiments on Twitter datasets related to an outbreak of civil unrest in Mexico demonstrate the effectiveness and practicability of the new method. The proposed method will be helpful to accurately predict the spatio-temporal evolution process of Twitter events, which belongs to a deeper geographical analysis of spatio-temporal Big Data.
BibTeX
@article{shi2016framework,
  author = {Yan Shi and Min Deng and Xuexi Yang and Qiliang Liu and Liang Zhao and Chang-Tien Lu},
  title = {{A Framework for Discovering Evolving Domain Related Spatio-Temporal Patterns in Twitter}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2016},
  doi = {10.3390/ijgi5100193},
}
Figure