Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
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.
The authors present novel theoretical upper bounds on the total numberof nodes that are eventually activated/influenced in the IndepnedentCascade (IC) model in terms of spectral properties of the "hazardmatrix" (defined in terms of the edge probabilities). They firstpresent a worst case bound where the initial influencers are chosen tomaximize the influence, and then present an average case bound wherethe initially influencers are chosen at random. In each case,the bounds demonstrate sub-critical and super-critical behavior. Inparticular, the sub-critical regime occurs when the spectral radius ofthe appropriate matrix is less than one, and gives bounds ofO(sqrt(n)) infected nodes in the worst case and O(1) in the averagecase. The show how their general results can apply to improveresults on SIR epidemic models and characterizing giant components inrandom graphs. They also give results for particular families ofgraphs and demonstrate the accuracy of their bounds empirically.The analysis of the paper is sophisticated and rigorous and givesdetailed upper bounds that seem to match or beat existing bounds in anumber of areas. The paper is well-written and clear.While the flavor of the results is not incredibly surprising---thereare many similar results relating giant components, epidemic spread,etc. to the spectral radius of some matrix---these results aresignificant because of their tightness, broad applicability, andquality of the analysis. They could potentially have algorithmicsignificance by providing upper bounds for the influence maximizationproblem (provided that the upper bounds are tighter than those givenby the approximation guarantee of the algorithm).The paper is atypical for NIPS in that it is a theoretical analysis ofa mathematical model without a real algorithmic component. Since itsheds light on models that are actively being researched by the NIPScommunity and makes interesting connections between those and othermodels I believe it is within scope.Comments / questions:* I believe the statement of Lemma 1 can be strenghtened to say that  the distribution of the final set of infected nodes is identical  under each of these processes (not just that the marginal  probability of each node i being infected is the same).* I think there is a minor problem with the proof of Lemma 1 in the  supplementary material. Eq. (1) gives a system of equations that  must be satisfied by the random variables {X_i}, but it does not  uniquely define the random process because there are also other  solutions to the set of equations. In particular, one can set  X_i = 1 for all nodes in some cycle that is *not* reachable from  from A and still satisfy these equations. So, showing that all three  processes give random variables that satisfy these equations doesn't  prove their equivalence. It should be easy to fix the proof, e.g.,  by using Eq. (8) instead as the characterization of the process.* The difference between O(sqrt(n)) and O(1) in the sub-critical  regimes for worst and average cases is interesting. Can you provide  any more intuition for this? Are there any other phase transitions  in the average case behavior?* Can you say anything about lower bounds in the super-critical cases?* The applicability of DTIC to undirected graphs in Lemma 3 was a  minor confusion DTIC was defined for directed graphs. The  supplementary material makes it clear that this this can be  interpreted as DTIC in the bidirected graph where p_{ij} =  p_{ji}. Perhaps this can be clarified in the main paper. * In the experiments, how are the edge probabilities set? What  parameter(s) are tuned to vary the spectral radius? More details  would help understand the experiments better.* Is each point in your plots the result of a single simulation or the  average over multiple trials? An average over multiple trials would  be a cleaner match to your bounds on the expected value. Error bars  would also help illustrate the variability. On that note (assuming  data points are individual trials), in Figure 3(a) it looks like the  variance of the number of infected nodes is higher in the  sub-critical regime. Can you say anything about this theoretically?