Learnability of Competitive Threshold Models
This provides theoretical foundations and practical methods for social computing applications, though it appears incremental in extending threshold models to competitive settings.
The paper tackles the problem of modeling competitive social contagion spread by theoretically analyzing the learnability of competitive threshold models, showing they can be simulated by neural networks with finite VC dimensions to derive sample complexity bounds, and demonstrates decent performance with less data than existing methods.
Modeling the spread of social contagions is central to various applications in social computing. In this paper, we study the learnability of the competitive threshold model from a theoretical perspective. We demonstrate how competitive threshold models can be seamlessly simulated by artificial neural networks with finite VC dimensions, which enables analytical sample complexity and generalization bounds. Based on the proposed hypothesis space, we design efficient algorithms under the empirical risk minimization scheme. The theoretical insights are finally translated into practical and explainable modeling methods, the effectiveness of which is verified through a sanity check over a few synthetic and real datasets. The experimental results promisingly show that our method enjoys a decent performance without using excessive data points, outperforming off-the-shelf methods.