WSDM-14 Tutorial

Big Graph Mining for the Web and Social Media:
Algorithms, Anomaly Detection, and Applications

by U Kang (KAIST), Leman Akoglu (Stony Brook), and Polo Chau (Georgia Tech.)

Graphs are everywhere in our lives: social networks, the World Wide Web, biological networks, and many more. These graphs are growing at unprecedented rate, now exceeding billions of nodes and edges. What are the patterns and anomalies in such big graphs? How to design scalable algorithms to discover them? What visual analytics techniques to use to make sense of such big graphs? And what kind of real-world problems, associated with the Web and social media, can we solve with such tools? These are exactly the goals of this tutorial. We start with important algorithms that are central to graph mining and pattern discoveries, including graph-based anomaly detection techniques (complement of pattern discoveries) that are playing increasingly important role in exploratory analysis and helping users gain insight into data. Then we describe how to scale up these techniques to big graphs with more than billions of nodes. Finally, we discuss how our aforementioned techniques help solve real-world problems that make impact to society (e.g., fraud/malware detection, recommendations, community detection).