Computing competing cascades on signed networks

Often in marketing, political campaigns and social media, two competing products or opinions propagate over a social network. Studying social influence in such competing cascade scenarios enables building effective strategies for maximizing the propagation of one process by targeting the most “influential” nodes in the network. The majority of prior work, however, focuses on unsigned networks where individuals adopt the opinion of their neighbors with certain probability. In real life, relationships between individuals can be positive (e.g., friend of relationship) or negative (e.g., connection between “foes”). According to social theory, people tend to have similar opinions to their friends but opposite of their foes. We study the problem of competing cascades on signed networks, which has been relatively unexplored. Particularly, we study the progressive propagation of two competing cascades in a signed network under the Independent Cascade Model and Generalized Linear Threshold Model and provide an approximate analytical solution to compute the probability of infection of a node at any given time. We validate the quality of our approximation on several synthetic graphs. We leverage our analytical solution to the problem of competing cascades in signed networks to develop a heuristic for the influence maximization problem. We allow the seed-set to be initialized with populations of both cascades with the end goal of maximizing the spread of one cascade. We validate our approach on several large-scale real-world and synthetic networks. Our experiments demonstrate that our influence maximization heuristic significantly outperforms state-of-the-art methods, particularly when the network is dominated by distrust relationships.