Maximizing Social Influence in Nearly Optimal Time a result by Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier (SODA14)
| Speaker: | Alex Lange |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Door will open at 4:15 p.m. As usual we will have 15 mins for socializing and for eating pizza before the talk starts (at 4:30 p.m. sharp).
Abstract:
Diffusion
is
a
fundamental
graph
process,
underpinning
such
phenomena
as
epidemic
disease
contagion
and
the
spread
of
innovation
by
word-of-mouth.
We
address
the
algorithmic
problem
of
finding
a
set
of
k
initial
seed
nodes
in
a
network
so
that
the
expected
size
of
the
resulting
cascade
is
maximized,
under
the
standard
independent
cascade
model
of
network
diffusion.
Runtime
is
a
primary
consideration
for
this
problem
due
to
the
massive
size
of
the
relevant
input
networks.
We
provide
a
fast
algorithm
for
the
influence
maximization
problem,
obtaining
the
near-optimal
approximation
factor
of
(1
-
1/e
-
epsilon),
for
any
epsilon
>
0,
in
time
O((m+n)log(n)
/
epsilon^3).
Our
algorithm
is
runtime-optimal
(up
to
a
logarithmic
factor)
and
substantially
improves
upon
the
previously
best-known
algorithms
which
run
in
time
Omega(mnk
POLY(1/epsilon)).
Furthermore,
our
algorithm
can
be
modified
to
allow
early
termination:
if
it
is
terminated
after
O(beta(m+n)log(n))
steps
for
some
beta
<
1
(which
can
depend
on
n),
then
it
returns
a
solution
with
approximation
factor
O(beta).
Finally,
we
show
that
this
runtime
is
optimal
(up
to
logarithmic
factors)
for
any
beta
and
fixed
seed
size
k.
The
presentation
will
be
based
on
the
following
manuscript:
Maximizing
Social
Influence
in
Nearly
Optimal
Time.
For
more
information
about
our
reading
group,
please
visit
our
webpage.