Large Graph Mining - Patterns, Tools and Cascade Analysis
Christos Faloutsos
Wayne State Univ.
Feb. 2013
ABSTRACT:
What do graphs look like? How do they evolve over time?
How to handle a graph with a billion nodes?
Graphs appear in numerous settings,
with important applications, for example:
in computer communication networks,
where anomalies may correspond to attacks;
in social networks, where strange patterns may correspond
to fraud or account hijacking;
in banking transactions (users-accessing-accounts), where we want to detect
money-laundering activities and related abnormalities.
In order to find anomalies/rare-events,
we need to know what is normal and popular.
We present a long list of static and temporal laws,
and some recent observations on real graphs (like, e.g., ``eigenSpokes'').
In addition to listing observations from large graphs,
we also present tools,
for discovering anomalies and patterns,
as well as an overview of the PEGASUS system
which is designed for handling Billion-node graphs,
running on top of the ``hadoop'' system.
Finally, one of the most interesting phenomena on graphs
is the propagation (of ideas, memes, viruses, rumors).
For cascades and propagation, we present
results on epidemic thresholds
as well as fast immunization algorithms.
FOILS
in pdf
BIOGRAPHICAL NOTE
Christos Faloutsos is a Professor at Carnegie Mellon University.
He received the Research Contributions Award in ICDM 2006,
the SIGKDD Innovations Award (2010),
nineteen ``best paper'' awards (including two ``test of time'' awards),
and four teaching awards.
He is an ACM Fellow,
he has published over 200 refereed articles, 11 book chapters
and one monograph. He holds six patents and
he has given over 30 tutorials and over 10 invited distinguished lectures.
His research interests include data mining
for graphs and streams, fractals, database performance,
and indexing for multimedia and bio-informatics data.