Search

An online community network such as Twitter or amazon.com links entities (e.g., users, products) with various relationships (e.g., friendship, co-purchase) and make such information available for access through a web interface. The web interfaces of these networks often support features such as keyword search and "get-neighbors" — so a visitor can quickly find entities (e.g., users/products) of interest. Nonetheless, the interface is usually too restrictive to answer complex queries such as (1) find 100 Twitter users from California with at least 100 followers who talked about ICWSM last year or (2) find 100 books with at least 200 5-star reviews at amazon.com. In this paper, we introduce the novel problem of answering complex queries that involve non-searchable attributes through the web interface of an online community network. We model such a network as a heterogeneous graph with two access channels, Content Search and Local Search. We propose a unified approach that transforms the complex query into a small number of supported ones based on a strategic query-selection process. We conduct comprehensive experiments on Twitter and amazon.com which demonstrate the efficacy of our proposed algorithms.

In a large number of applications, from biomedical literature to social networks, there are collections of text documents that are annotated by interconnected entities, which are related to each other through association graphs. For example, social posts are related through the friendship graph of their authors, and PubMed articles area annotated by Mesh terms, which are related through ontological relationships. To effectively query such collections, in addition to the text content relevance of a document, the semantic distance between the entities of a document and the query must be taken into account. In this paper, we propose a novel query framework, which we refer as keyword querying on graph-annotated documents, and query techniques to answer such queries. Our methods automatically balance the impact of the graph entities and the text content in the ranking. Our qualitative evaluation on real dataset shows that our methods improve the ranking quality compared to baseline ranking systems.

Many online services like Twitter and GNIP offer streaming programming interfaces that allow real-time information filtering based on keyword or other conditions. However, all these services specify strict access constraints, or charge a cost based on the usage. We refer to such streams as ``hidden streams'' to draw a parallel to the well-studied hidden Web, which similarly restricts access to the contents of a database through a querying interface. At the same time, the users' interest is often captured by complex classification models that, implicitly or explicitly, specify hundreds of keyword-based rules, along with the rules' accuracies. In this paper, we study how to best utilize a constrained streaming access interface to maximize the number of retrieved relevant items, with respect to a classifier, expressed as a set of rules. We consider two problem variants. The static version assumes that the popularity of the keywords is known and constant across time. The dynamic version lifts this assumption, and can be viewed as an exploration-vs.-exploitation problem. We show that both problems are NP-hard, and propose exact and bounded approximation algorithms for various settings, including various access constraint types. We experimentally evaluate our algorithms on real Twitter data.

Every day, users publish hundreds of millions of microblog postings in popular social-networking platforms such as Twitter and Facebook. When considered in aggregation, microblog postings have been shown to exhibit temporal patterns that reflect events of global significance. In this paper, we propose techniques to identify and quantify spatial patterns: for instance, a hashtag that is popular in one city on a given day, may become popular in a different city on the next day. Detecting these patterns is challenging given that the data are noisy and posts are not physically moving, i.e., they are not continuous trajectories in space like vehicles. Second, we introduce a multi-granular summarization model to describe the movement of a hashtag between two time periods. For interpretability, we seek representations of spatial changes that follow natural or administrative boundaries on a map, such as cities and states. We compare various movement measures using quantitative approaches and user surveys. We evaluate our movement summarization schemes by analytical loss and coverage functions. Our results show that it is possible to reliably detect relevant spatial changes automatically, and to produce simple summaries that represent accurately these changes.