Non-independent cascade formation: Temporal and spatial effects

Determining cascade size and the factors affecting cascade size are two fundamental research problems in social network analysis. The commonly considered independent cascade model, when applied to social networks such as Digg, produces a phase-transition phenomenon where the cascade is either very small or very large. This phenomenon can be explained based on the concept of Giant Propagation Component (GPC). The GPC is defined as a maximally connected component, such that, by applying the independent cascade model, once any node of the component is infected, most of the remaining nodes in the component will eventually become infected with a high probability. While GPC exists in social networks, the phase-transition phenomenon, is not observed in the actual cascade size distribution when the information propagation is due to actions such as "like" or "dig". This paper hypothesizes that the cascade process, i.e., the likeliness of a node being infected changes over time and depends on how far away the node is from the seed. Furthermore, each node will not be exactly independently considered for infection from each of its infected friends, because the chance of information propagation through "like" or "dig" does not necessarily increase when there are more friends like/dig the information. To this end, we develop and simulate a new non-independent infection cascade process. The experiment results show that the proposed cascade process generates power-law like cascade size distribution without phase transition, which resembles much better the real-world cascade distribution observed in the Digg social network.