(Oct 10) Mining Large Dynamic Graphs and Tensors

Graphs are everywhere from online social networks to bipartite review graphs. Many of them are large and dynamic. Moreover, they are with extra information and thus naturally modeled as tensors (i.e., multi-dimensional arrays). Given large (e.g., terabyte-scale) dynamic graphs and tensors, how can we analyze their structure? How can we detect interesting anomalies? Lately, how can we model the behavior of the individuals in the data?

In this talk, I will focus on these closely related questions, all of which are fundamental to understand large growing data on user behavior. First, for structure analysis, I will present our one-pass, sublinear-space algorithms that incrementally update several connectivity measures in dynamic graphs. Then, for anomaly detection, I will discuss our near-linear-time approximation algorithms that detect abnormally dense subgraphs and subtensors, which signal interesting anomalies, such as “follower-boosters” on Twitter and “edit wars” on Wikipedia. Next, regarding behavior modeling, I will introduce our game-theoretic models for purchasing behavior of individuals on social networks.

Lastly, I will conclude with my future vision on big data mining, covering upcoming challenges, new approaches, and real-world applications.