Unifying information propagation models on networks and influence maximization

Abstract

Information propagation on networks is a central theme in social, behavioral, and economic sciences, with important theoretical and practical implications, such as the influence maximization problem for viral marketing. Here, we consider a model that unifies the classical independent cascade models and the linear threshold models, and generalise them by considering continuous variables and allowing feedback in the dynamics. We then formulate its influence maximization as a mixed integer nonlinear programming problem and adopt derivative-free methods. Furthermore, we show that the problem can be exactly solved in the special case of linear dynamics, where the selection criterion is closely related to the Katz centrality, and propose a customized direct search method with local convergence. We then demonstrate the close-to-optimal performance of the customized direct search numerically on both synthetic and real networks.

arXiv comment28 pages, 22 figures

References in corpus (8)

• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• Epidemic processes in complex networks
• The Dynamics of Viral Marketing
• Theory of Rumour Spreading in Complex Social Networks
• Influence of fake news in Twitter during the 2016 US presidential election
• Diffusion in a crowded environment
• Hopping in the crowd to unveil network topology

Cited by in corpus (2)

• Spreading and Structural Balance on Signed Networks
• Maximizing Influence with Graph Neural Networks