Flexible Modeling of Information Diffusion on Networks with Statistical Guarantees

Alexander Kagan; Elizaveta Levina; Ji Zhu

Modeling information spread through a network is one of the key problems of network analysis. Most approaches assume the spread is governed by some probabilistic diffusion model, often parameterized by the strength of connections between network members (edge weights), highlighting the need for methods that can accurately estimate them. Multiple prior works suggest estimators for particular diffusion models, but lack a rigorous statistical analysis establishing their asymptotic properties and allowing for uncertainty quantification. In this paper, we develop a likelihood-based approach to estimate edge weights from the observed information diffusion paths under the proposed General Linear Threshold (GLT) model, a broad class of discrete-time information diffusion models that includes both the well-known linear threshold (LT) and independent cascade (IC) models. We derive a finite-sample error bound for the estimator and demonstrate that it is asymptotically normal under mild conditions. We conclude by studying the GLT model in the context of the Influence Maximization (IM) problem. Extensive experiments on synthetic and real-world networks demonstrate that the proposed estimation and inference frameworks for the GLT model parameters can significantly improve estimation of spread from a given subset of nodes, prediction of node activation, and the quality of the IM problem solutions.

Flexible Modeling of Information Diffusion on Networks with Statistical Guarantees

Abstract