Diffusion on Social Networks: Bursting Filter Bubbles and Reconstructing Cascades

Thursday, September 20, 2018

3:00 p.m.

ISI seminar room 1st floor

Dr. Cigdem Aslay, Aalto University (Finland)

In this talk I will present two recent results in the area of diffusion on
social networks.

The first result provides a novel approach to contribute towards bursting
filter bubbles. We formulate the problem as a task of recommending news
articles to selected users with the aim to maximize the overall diversity
of information exposure in a social network. We consider a realistic
setting where we take into account the political leanings of users and
articles, and the probability of users to further share articles. This
setting allows us to strike a balance between maximizing the spread of
articles and ensuring the exposure of users to diverse viewpoints. We show
that the problem can be cast as maximizing a monotone and submodular
function subject to a matroid constraint on the allocation of articles to
users. It is a challenging generalization of the influence maximization
problem. Yet, we are able to devise scalable approximation algorithms.
Experimentally, we demonstrate the scalability and efficiency of our
method on several real-world datasets.

The second result provides a robust approach to the cascade-reconstruction
problem. We consider a network where an infection has taken place and a
subset of infected nodes has been partially observed. Our goal is to
reconstruct the underlying cascade that is likely to have generated these
observations. We reduce this cascade-reconstruction problem to computing
the marginal probability that a node is infected given the partial
observations, which is a #P-hard problem. To circumvent this issue, we
resort to estimating infection probabilities by generating a sample of
probable cascades, which span the nodes that have already been observed to
be infected, and avoid the nodes that have been observed to be uninfected.
The sampling problem corresponds to sampling directed Steiner trees with a
given set of terminals, which is a problem of independent interest and has
received limited attention in the literature. For this problem, we propose
two novel algorithms with provable guarantees on the sampling distribution
of the returned Steiner trees, providing a robust approach to the
cascade-reconstruction problem. Our method is an improvement over
state-of-the-art approaches that often make explicit assumptions about the
infection model, or require additional parameters. Empirically, we
validate the proposed reconstruction algorithm on real-world graphs with
both synthetic and real cascades.