Inferring User Interests from Tweet Times

Dinesh Ramasamy, Sriram Venkateswaran and Upamanyu Madhow


We propose and demonstrate the feasibility of a probabilistic framework for mining user interests from their tweet times alone, by exploiting the known timing of external events associated with these interests. This approach allows for making inferences on the interests of a large number of users for which text-based mining may become cumbersome, and also sidesteps the difficult problem of semantic/contextual analysis required for such text-based inferences. The statistic that we propose for gauging the user’s interest level is the probability that he/she tweets more frequently at certain times when this topic is in the “public eye” than at other times. We report on promising experimental results using Twitter data on detecting whether or not a user is a fan of a given baseball team, leveraging the known timing of games played by the team. Since people often interact with others who share similar interests, we extend our probabilistic frame- work to use the interest level estimates for other users with whom a person interacts (by referring to them in his/her tweets). We demonstrate that it is possible to significantly improve the detection probability (for a given false alarm rate) by such information pooling on the social graph.

Guest: Dinesh Ramasamy (UCSB)

Host:  Chen Avin

Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths

Edith Cohen, Daniel Delling, Fabian Fuchs, Moises Goldszmidt, Andrew V. Goldberg and Renato F. Werneck


Similarity estimation between nodes based on structural properties of graphs is a basic building block used in the analysis of massive networks for diverse purposes such as link prediction, product rec- ommendations, advertisement, collaborative filtering, and community discovery. While local similarity measures, based on proper- ties of immediate neighbors, are easy to compute, those relying on global properties have better recall. Unfortunately, this better qual- ity comes with a computational price tag. Aiming for both accuracy and scalability, we make several contributions. First, we define closeness similarity, a natural measure that compares two nodes based on the similarity of their relations to all other nodes. Second, we show how the all-distances sketch (ADS) node labels, which are efficient to compute, can support the estimation of closeness similarity and shortest-path (SP) distances in logarithmic query time. Third, we propose the randomized edge lengths (REL) technique and define the corresponding REL distance, which captures both path length and path multiplicity and therefore improves over the SP distance as a similarity measure. The REL distance can also be the basis of closeness similarity and can be estimated using SP computation or the ADS labels. We demonstrate the effectiveness of our measures and the accuracy of our estimates through experiments on social networks with up to tens of millions of nodes.

Guest: Daniel Delling (Microsoft Research)

Host: Chen Avin

On the Performance of Percolation Graph Matching

Lyudmila Yartseva and Matthias Grossglauser


Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de- anonymization of social and information networks and, more generally, in the merging of structural data from different domains.

One class of graph-matching algorithms starts with a known seed set of matched node pairs. Despite the success of these algorithms in practical applications, their performance has been observed to be very sensitive to the size of the seed set. The lack of a rigorous understanding of parameters and performance makes it difficult to design systems and predict their behavior.

In this paper, we propose and analyze a very simple per- colation -based graph matching algorithm that incrementally maps every pair of nodes (i,j) with at least r neighboring mapped pairs. The simplicity of this algorithm makes pos- sible a rigorous analysis that relies on recent advances in bootstrap percolation theory for the G(n, p) random graph. We prove conditions on the model parameters in which per- colation graph matching succeeds, and we establish a phase transition in the size of the seed set. We also confirm through experiments that the performance of percolation graph match- ing is surprisingly good, both for synthetic graphs and real social-network data.

Guest: Lyudmila Yartseva

Host: Chen Avin