UofT, DSL, Nov. 2014
Mining Large Graphs
Christos Faloutsos, CMU

ABSTRACT

Given a large graph, like who-likes-whom, or who-calls-whom, what behavior is normal and what should be surprising, possibly due to fraudulent activity? How do graphs evolve over time? How does influence/news/viruses propagate, over time? We focus on three topics: (a) anomaly detection in large static graphs (b) patterns and anomalies in large time-evolving graphs and (c) cascades and immunization.
For the first, we present a list of static and temporal laws, including advances patterns like 'eigenspokes'; we show how to use them to spot suspicious activities, in on-line buyer-and-seller settings, in FaceBook, in twitter-like networks.
For the second, we show how to handle time-evolving graphs as tensors, how to handle large tensors in map-reduce environments, as well as some discoveries such settings.
For the third, we show that for virus propagation, a single number is enough to characterize the connectivity of graph, and thus we show how to do efficient immunization for almost any type of virus (SIS - no immunity; SIR - lifetime immunity; etc)
We conclude with some open research questions for graph mining.

FOILS

Last edited: Nov 4, 2014, by Christos Faloutsos