Timezone: »

 
Poster
Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
Remi Lemonnier · Kevin Scaman · Nicolas Vayatis

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

In this paper, we derive theoretical bounds for the long-term influence of a node in an Independent Cascade Model (ICM). We relate these bounds to the spectral radius of a particular matrix and show that the behavior is sub-critical when this spectral radius is lower than 1. More specifically, we point out that, in general networks, the sub-critical regime behaves in O(sqrt(n)) where n is the size of the network, and that this upper bound is met for star-shaped networks. We apply our results to epidemiology and percolation on arbitrary networks, and derive a bound for the critical value beyond which a giant connected component arises. Finally, we show empirically the tightness of our bounds for a large family of networks.

[ PDF] 

Author Information

Remi Lemonnier (CMLA - ENS Cachan / 1000mercis, Paris)
Kevin Scaman (ENS Cachan - CMLA)
Nicolas Vayatis (Ecole Normale Supérieure de Cachan)

More from the Same Authors