ASONAM-13 Tutorial

Big Graph Mining:
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. The sizes of these graphs are growing at unprecedented rate, now exceeding billions of nodes and edges. What are the patterns and anomalies in such massive graphs? How to design scalable algorithms to find them? What visual analytics techniques to use to make sense of such massive graphs? And what kind of real-world problems can we solve with such tools? These are exactly the goals of this tutorial. We start with important graph 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 massive graphs with billions of nodes (e.g., with Hadoop). Finally, we discuss how our aforementioned techniques help solve large-scale, real-world problems that make impact to society (e.g., fraud detection, malware detection).