Nonbacktracking Bounds on the Influence in Independent Cascade Models

Influence propagation is concerned with the diffusion of information (or viruses) from initially influenced (or infected) nodes, called seeds, in a network. Understanding how information propagates in networks has become a central problem in a broad range of fields, such as viral marketing [17], sociology [8, 19, 22], communication [12], epidemiology [20], and social network analysis [23]. One of the most fundamental questions on influence propagation is to estimate the influence, i.e. the expected number of influenced nodes at the end of the propagation given some seeds. Estimating the influence is central to various research problems related to influence propagation, such as the widely-known influence maximization problem -- finding a set of k nodes that maximizes the expected number of influenced nodes. Recent studies in the influence propagation have proposed heuristic algorithms [11, 18, 3, 7, 21] for the influence maximization problem while using Monte Carlo (MC) simulations to approximate the influence. Despite its simplicity, approximating the influence via MC simulations is far from ideal for large networks; in particular, MC may require a large amount of computations in order to stabilize the approximation.