CMU Conf. on Electricity Industry
Lunch Speaker - title:
Large Graph Mining - Patterns, Explanations, and Cascade Analysis
Christos Faloutsos, CMU
Feb. 4, 2014
ABSTRACT
Why do graphs exhibit so many power laws?
How does influence/news/viruses propagate, over time?
We present a long list of static and temporal laws,
a possible explanation using fractals and self-similarity,
and some recent results in virus propagation and immunization,
for a single, as well as competing viruses.
For virus/influence propagation and immunization,
we describe the 'G2' theorem, which states
that (a) for any graph and (b) for almost any virus type
(SIS, SIR, SIRS, etc),
the only measure of the graph connectivity that matters
for the epidemic threshold (`tipping point')
is the first eigenvalue of the adjacency matrix.
Based on that, we show several, fast heuristics
for immunization, in static and dynamic graphs.
FOILS
- Slides of presentation in
pdf
Last edited: Feb. 4, 2014, by Christos Faloutsos