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 language | English (US) |
---|---|
Article number | 156 |
Pages (from-to) | 1-19 |
Number of pages | 19 |
Journal | Social Network Analysis and Mining |
Volume | 4 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1 2014 |
Funding
This work was principally funded by ONR grant N000140910685.
Keywords
- Social networks
- Spatio-temporal data
- Subgraph matching
- Uncertainty
ASJC Scopus subject areas
- Information Systems
- Communication
- Media Technology
- Human-Computer Interaction
- Computer Science Applications