Dr. Gerardo Iñiguez from Institute for Research in Applied Mathematics and Systems, National Autonomous University of Mexico. He is going to talk about:

Modelling complex contagion with tie heterogeneities

Social influence, the effect that the past behaviour of acquaintances has on
our daily decisions, is arguably the main driving mechanism of many complex collective
phenomena in society, including the spreading of innovations, ideas and fads,
or the growth of political and social movements. Many of these processes have
been studied empirically in the past, particularly with regards to the
existence of so-called adoption cascades, where large number of people adopt
the same behaviour in a relatively short time. Moreover, they have been
modelled either as simple contagion (where adoption is driven by independent
contagion stimuli, like the Bass model of innovation diffusion), or as complex
contagion (where a threshold on the number of adopting neighbours in a
network determines spreading, like the Watts model of adoption cascades).
However, it is still unclear whether real spreading phenomena is regulated by
simple or complex contagion (or a combination of both), which makes it difficult to identify
cognitive and social mechanisms that may control the collective action of
large groups of people. Furthermore, most spreading models disregard one relevant
property of real social networks, namely tie heterogeneities in terms of social influence.
Influence arriving on social ties may vary from neighbour to neighbour, as it largely depends
on the nature and frequency of interaction with a given friend.

Here we close this gap on the understanding of social contagion by extending
the conventional Watts cascade model to account for tie heterogeneities. We focus on the case of a
bimodal weight distribution, such that spreading is determined by the adoption
threshold of nodes and the standard deviation of tie weights. We find that the
presence of tie heterogeneities induce unexpected dynamical behaviour, as
they either speed up or slow down contagion with respect to the unweighted
case, depending on the adoption threshold and weight standard
deviation. We found this effect to be present in both synthetic and real social networks,
which we verify via numerical simulations and an analytical approach based on
approximate master equations. Moreover, we find that our model with tie heterogeneities
bridges the theoretical descriptions of simple and complex contagion, and
thus hints at the existence of a single mechanism driving social spreading, regardless of the initial
hypotheses used to describe contagion stimuli between individuals. These
results may be instrumental in developing more accurate spreading models that manage to
gauge the rise and extent of real behavioural cascades in society.

Date: 10th January 2017, at 15:00
Place: Amphi J (ENS Lyon, site Monod).

Abstract :

What are the performance guarantees of the algorithms used in practice
for clustering problems?
In a paper with Phil Klein and Claire Mathieu, we give the
first polynomial-time approximation schemes for the following problems:
(1) uniform facility location in edge-weighted planar graphs;
(2) $k$-median and $k$-means in edge-weighted planar graphs;
(3) $k$-means in Euclidean space of bounded dimension.
The algorithm is a standard, widely-used local search heuristic where
the local neighborhood of a solution $S$ consists of all solutions
obtained from $S$ by removing and adding $1/\eps^{O(1)}$ centers.
In a second line of work with Chris Schwiegelshohn, we show that this
algorithm also performs near-optimaly for several types of instances
that aim at characterizing the structure of real-world instances
stemming from machine learning and data analysis.
Those results make a step toward understanding the success of local
search heuristics in practice.

When: Friday Nov, 25th 2016
Where: Amphi B – ENS de Lyon — Site Monod

HDR dissertation by Tommaso Venturini under the Supervision of Pablo Jensen Ecole Normale Supérieure de Lyon

Jury: Richard Rogers, Dominique Pestre, Dominique Vinck, didier bigo, Pablo Jensen, Eric Fleury

Monday September 26th, 10:30AM. ENS de Lyon.