N&O seminar: Yllka Velaj (CWI)

Yllka Velaj (CWI) will give a lecture with the title 'Information spreading with network augmentation'.
  • What Networks & Optimization English
  • When 11-09-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC200)
  • Where CWI, Lecture room L016
  • Contact Name
  • Contact Phone 020-592 4189
  • Web Visit external website
  • Add event to calendar iCal

Everyone is welcome to attend the lecture of Yllka Velaj (CWI) with the title 'Information spreading with network augmentation'.


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.