The Selection of Diffusion Models for Influence Optimization in Social Networks

Abstract

Given a network G = (V,E) and opinion data collected from independent diffusion processes, we might want to 1) learn the network’s influence function and 2) use this knowledge of influence to, under a constraint k, select the k nodes that will influence the maximal number of nodes in V. The process of learning and maximizing influence in a social network requires, as a presupposition, the underlying model class to be learned. However, though much attention has been paid to learning model parameters and their corresponding influence functions, and to maximizing influence in a graph given an influence function, the process of selecting the underlying model class has so far been neglected. I advance two main arguments regarding the process of learning and maximizing influence in social networks. First, I argue that the Linear Threshold model can be expected to outperform the Voter model at both predicting and maximizing influence, and empirically may outperform the Independent Cascade model as well. To do so, I examine the relationships between the Voter model, the Independent Cascade model, and the Linear Threshold model, and in particular the theoretical relationship between the Voter model and the Linear Threshold model. I argue that learning and maximizing influence under the Voter model are subsets of the tasks of learning and maximizing influence under the Linear Threshold model. This conclusion is also weakly supported by data collected from Twitter. Second, I argue that the task of maximizing influence is a distinct process from predicting influence, and models that perform well at one task do not necessarily perform well at the other. This possibly complicates the application of traditional model selection techniques to the problem of model selection for influence maximization.