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.
Kijung Shin is a Ph.D. candidate in the Computer Science Department at Carnegie Mellon University, advised by Christos Faloutsos. His research interests include data mining, social network analysis, and scalable machine learning. He is a recipient of the KFAS Scholarship and the Siebel Scholar Fellowship. He also won the Best Research Paper Award at KDD 2016 and the Gold Prize at the 21th Samsung Humantech Paper Award. He has published over 20 research papers in major data mining and database venues, including KDD, ICDM, WWW, and SIGMOD. He received M.S. in Computer Science from Carnegie Mellon University in 2017, and he received B.S. in Computer Science and Engineering and B.A. in Economics from Seoul National University in 2015. He was a research intern at LinkedIn during the summers of 2017 and 2018, and he was an associate researcher at CYRAM from Feb 2011 to Dec 2013.