Learnability of Competitive Threshold Models
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.