Everyone is welcome to attend the lecture of Yllka Velaj (CWI) with the title 'Information spreading with network augmentation'.
Abstract:
When a new idea or innovation arises in a network, it can either quickly
propagate to a large part of the network or immediately expire.
Understanding the dynamics that regulate these behaviours has been one of
the main goals in the field of complex network analysis and has been
studied under the name of influence spreading or information diffusion
analysis problem.
An interesting question, in the analysis of the information diffusion, is
how to shape a given diffusion process so as to maximize or minimize the number
of activated nodes at the end of the process by taking intervention actions.
We study the problem of maximizing the information spread in a network
by creating a limited amount of new edges incident to a given initial set of
active nodes called seeds. We show that the problem cannot be approximated within a constant
factor greater than 1-1/2e, unless P=NP.
We then propose an algorithm that guarantees an approximation factor of
1−1/e−epsilon, where epsilon is any positive real number.
We experimentally show that, with a small number of added edges our algorithm
increases by far the expected number of active nodes with respect to an initial set of seeds.
