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


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
Issue number1
StatePublished - Jan 1 2014
Externally publishedYes


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

ASJC Scopus subject areas

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


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

Cite this