Learnability of Influence Function in Competitive Threshold Diffusion Model

Abstract:

Many social phenomena like the spread of news and technology can be modeled as the diffusion of information across the network. There have been a few operational diffusion models for such a purpose, where the diffusion goes round by round from the initial states to the final states. 

In another issue, neural networks are central to machine learning, where the information is passed layer by layer from the input layer to the output layer. 

In this project, we show a subtle relationship between the diffusion models and the neural networks: the diffusion process in a social network can be simulated by the information propagation in a neural network with piece-wise linear units. This immediately implies the learnability of influence functions, suggesting that it is possible to learn a diffusion model from samples. In particular, this project establishes the Probably Approximately Correct (PAC) learnability of competitive influence models and shows that the Empirical Risk Minimization (ERM) can be computed using linear programming.