Abstract
How do graphs look like? How do they evolve over time?
How do rumors and viruses propagate on real graphs?
We review some static and temporal 'laws',
fast algorithms to spot deviations and outliers,
and recent developments on virus propagation and immunization.
Abstract Given the specifics of a virus (or product, or hashtag)
how quickly will it propagate on a contact network?
Will it create an epidemic, or will it quickly die out?
The way a virus/product/meme propagates on a graph is important,
because it can help us design immunization policies
(if we want to stop it) or marketing policies
(if we want it to succeed).
We present some surprising results on the so-called 'epidemic threshold',
we discuss the effects of time-varying contact networks,
and we present fast algorithms to achieve near-optimal immunization.
We also review ``oddBall'', an anomaly detection algorithm
for large graphs, as well as ``eigenSpokes'', which may be useful
to spot botnets.
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),
eighteen ``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.