2014/07/17 by Lemonnier, Remi, Scaman, Kevin, Vayatis, Nicolas
#FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Probability (math.PR) #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.1407.4744
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(√(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.