WIN Workshop 2013
Keynote talk:
Large Graph Mining - Patterns, Tools and Cascade Analysis
Christos Faloutsos, CMU
ABSTRACT
Why do graphs exhibit so many power laws?
Why they often have no 'good cuts'?
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 the former, we show that self-similarity
naturally leads to power laws.
We describe the so-called ``Kronecker graphs''
which are self-similar by construction,
and which match a long list of the patterns
that appear in real graphs.
We also elaborate on the ``no good cuts'' discovery,
showing that the realistic-looking ``Kronecker graphs''
have no good cuts, either.
Finally, 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: Oct. 3, 2013, by Christos Faloutsos