Time is of the Essence: Improving Recency Ranking Using Twitter Data (paper)(slides)
Author: Anlei Dong, Ruiqiang Zhang, Pranam Kolari, Bai Jing, Yi Chang, Fernando Diaz, Zhaohui Zheng, Hongyuan Zha
In Proceedings of WWW'10

Abstract:
Twitter is a social network and a micro-blogging service, which becomes very popular nowadays. People use Twitter to exchange messages, which contain fresh and useful information. This paper proposes a ranking system for web search which utilizes Twitter data to improve ranking results, especially to improve the freshness of ranking results. We treat the urls that were ever referred by Twitter users (called as Twitter urls) differently compared with regular urls. A challenging problem for Twitter urls is that they lack click information and anchor-text information due to their freshness, which restrict them from being promoted appropriately in ranking results. We analyze the unique characteristics within the twitter microcosm such as Twitter users’ following relationship and the texts of tweets, and we use them as new evidences for ranking Twitter urls appropriately in web search. We then use a compositional modeling algorithm to fully use the available data and different categories of rank features. This approach solves the dilemma in recency ranking that fresh documents cannot be promoted appropriately due to the lack of favorable rank features that need to be aggregated over time. To evaluate ranking results, we not only incorporate recency demotion into discounted cumulative grade (DCG) for stale documents, but also use discounted cumulative freshness (DCF) to evaluate the most fresh documents in ranking results. The efficacy of this approach is illustrated by the experiments on real data.

Group Formation in Large Social Networks: Membership, Growth, and Evolution (paper)
by Lars Backstrom, Dan Huttenlocher, Jon Kleinberg and Xiangyang Lan,
In Proceedings of KDD'06

Abstract:

The processes by which communities come together, attract new members, and develop over time is a central research issue in the social sciences—political movements, professional organizations, and religious denominations all provide fundamental examples of such communities. In the digital domain, on-line groups are becoming increasingly prominent due to the growth of community and social networking sites such as MySpace and LiveJournal. However, the challenge of collecting and analyzing large-scale time-resolved data on social groups and communities has left most basic questions about the evolution of such groups largely unresolved: what are the structural features that influence whether individuals will join communities, which communities will grow rapidly, and how do the overlaps among pairs of communities change over time? Here we address these questions using two large sources of data:friendship links and community membership on LiveJournal, and co-authorship and conference publications in DBLP. Both of these datasets provide explicit user-defined communities, where conferences serve as proxies for communities in DBLP. We study how the evolution of these communities relates to properties such as the structure of the underlying social networks. We find that the propensity of individuals to join communities, and of communities to grow rapidly, depends in subtle ways on the underlying network structure. For example, the tendency of an individual to join a  community is influenced not just by the number of friends he or she has within the community, but also crucially by how those friends are connected to one another. We use decision-tree techniques to identify the most significant structural determinants of these properties. We also develop a novel methodology for measuring movement of individuals between communities, and show how such movements are closely aligned with changes in the topics of interest within the communities.

Detecting Leaders in Behavioral Networks (paper)(slides)

Author: Ilham Esslimani, Armelle Brun, Anne Boyer
Appeared in the Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2010)

Learning to detect events with Markov-modulated poisson processes (paper)(slides)

Alexander Ihler University of California, Irvine
Jon Hutchins University of California, Irvine
Padhraic Smyth University of California, Irvine, CA. 

The paper was published in ACM Transactions on Knowledge Discovery from Data (TKDD) Volume 1, Issue 3, (December 2007). 

in proceedings of KDD '10

Abstract

User generated information in online communities has been characterized with the mixture of a text stream and a network structure both changing over time. A good example is a web-blogging community with the daily blog posts and a social network of bloggers.
An important task of analyzing an online community is to observe and track the popular events, or topics that evolve over time in the community. Existing approaches usually focus on either the burstiness of topics or the evolution of networks, but ignoring the interplay between textual topics and network structures.
In this paper, we formally define the problem of popular event tracking (PET) in online communities, focusing on the interplay between textual content and social networks. We propose a novel statistical method that models the popularity of events over time, taking into consideration the burstiness of user interest, information diffusion in the network structure, and the evolution of textual topics. Specifically, a Gibbs Random Field is defined to model the influence of historical status of actors in the network and the dependency relationships among them; thereafter a topic model generates the words in text content of the event, regularized by the Gibbs Random Field. We prove that two classical models of information diffusion and text burstiness are special cases of our model under certain conditions. Empirical experiments with two different communities and datasets (i.e., Twitter and DBLP) show that our approach is effective and outperforms existing methods.

Suggesting Friends Using the Implicit Social Graph (paper) (slides)
by M. Roth, A. Ben-David, D. Deutscher, G. Flysher, I. Horn, A. Leichtberg, N. Leiser, Y. Matias & R. Merom
In KDD'10

Abstract:

Although users of online communication tools rarely categorize their contacts into groups such as "family", "co-workers", or "jogging buddies", they nonetheless implicitly cluster contacts, by virtue of their interactions with them, forming implicit groups. In this paper, we describe the implicit social graph which is formed by users' interactions with contacts and groups of contacts, and which is distinct from explicit social graphs in which users explicitly add other individuals as their "friends". We introduce an interaction-based metric for estimating a user's affinity to his contacts and groups. We then describe a novel friend suggestion algorithm that uses a user's implicit social graph to generate a friend group, given a small seed set of contacts which the user has already labeled as friends. We show experimental results that demonstrate the importance of both implicit group relationships and interaction-based affinity ranking in suggesting friends. Finally, we discuss two applications of the Friend Suggest algorithm that have been released as Gmail Labs features.

Title: Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors (paper)(slide)

appeared in WWW '10

Abstract: Twitter, a popular microblogging service, has received much attention recently. An important characteristic of Twitter is its real-time nature. For example, when an earthquake occurs, people make many Twitter posts (tweets) related to the earthquake, which enables detection of earthquake occurrence promptly, simply by observing the tweets. As described in this paper, we investigate the real-time interaction
of events such as earthquakes, in Twitter, and propose an algorithm to monitor tweets and to detect a target event. To detect a target event, we devise a classifier of tweets based on features such as the keywords in a tweet, the number of words, and their context. Subsequently, we produce a probabilistic spatiotemporal model for the target event that can find the center and the trajectory of the event location. We consider each Twitter user as a sensor and apply Kalman filtering and particle filtering, which are widely used for location estimation in ubiquitous/pervasive computing. The particle filter works better than other compared methods in estimating the centers of earthquakes and the trajectories of typhoons. As an application, we construct an earthquake reporting system in Japan. Because of the numerous earthquakes and the large number of Twitter users throughout the country, we can detect an earthquake by monitoring tweets with high probability (96% of earthquakes of Japan Meteorological Agency (JMA) seismic intensity scale 3 or more are detected). Our system detects earthquakes promptly and sends e-mails to registered users. Notification is delivered much faster than the announcements that are broadcast by the JMA.