What is the set of nodes of a social network that, under a probabilistic contagion model, would get infected if a given node s get infected? We call this set the sphere of influence of s. Due to the stochastic nature of the contagion model we need to define a notion of "expected" or "typical" cascade: this is a set of nodes which is the closest to all the possible cascades starting from s. In this work (to be presented at SIGMOD
2016) we formalize the Typical Cascade problem which requires, for a given source node s, to find the set of nodes minimizing the expected Jaccard distance to all the possible cascades from s. The expected cost of a typical cascade also provides us a measure of the stability of cascade propagation, i.e., how much random cascades from a source node s deviate from the "typical" cascade. In this sense source nodes with lower expected costs are more reliable.
We show that, while computing the quality of a candidate solution is #P-hard, a method based on (1) sampling random cascades and (2) computing their Jaccard Median, can obtain a multiplicative approximation with just
O(1) samples. We thus devise an index that allows to efficiently compute the sphere of influence for any node in the network. Finally, we propose an approach to the influence maximization problem based on the spheres of influence and set cover. Trough exhaustive evaluation using real-world networks and different methods of assigning the influence probability to each edge, we show that our approach outperforms in quality the theoretically optimal greedy algorithm.
Copyright. All Rights Reserved.