STUN: querying spatio-temporal uncertain (social) networks

Chanhyun Kang, Andrea Pugliese*, John Grant, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In this paper, we consider the problem of social networks whose edges may be characterized with uncertainty, space, and time. We propose a model called spatio-temporal uncertain networks (STUN) to formally define such networks, and then we propose the concept of STUN subgraph matching (or SM) queries. We develop a hierarchical index structure to answer SM queries to STUN databases and show that the index supports answering very complex queries over 1M+ edge networks in under a second. We also introduce the class of STUNRank queries in which we characterize the importance of vertices in STUN databases, taking space, time, and uncertainty into account. We show query-aware and query-unaware versions of STUNRank as well as alternative ways of defining it. We report on an experimental evaluation of STUNRank showing that it performs well on real world networks.

Original languageEnglish (US)
Article number156
Pages (from-to)1-19
Number of pages19
JournalSocial Network Analysis and Mining
Volume4
Issue number1
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

Keywords

  • Social networks
  • Spatio-temporal data
  • Subgraph matching
  • Uncertainty

ASJC Scopus subject areas

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'STUN: querying spatio-temporal uncertain (social) networks'. Together they form a unique fingerprint.

Cite this