Efficient spread-size approximation of opinion spreading in general social networks

Choe, Byeongjin; Lin, Yishi; Lim, Sungsu; Lui, John C. S.; Jung, Kyomin

In contemporary society, understanding how information, such as trends and viruses, spreads in various social networks is an important topic in many areas. However, it is difficult to mathematically measure how widespread the information is, especially for a general network structure. There have been studies on opinion spreading, but many studies are limited to specific spreading models such as the susceptible-infected-recovered model and the independent cascade model, and it is difficult to apply these studies to various situations. In this paper, we first suggest a general opinion spreading model (GOSM) that generalizes a large class of popular spreading models. In this model, each node has one of several states, and the state changes through interaction with neighboring nodes at discrete time intervals. Next, we show that many GOSMs have a stable property that is a GOSM version of a uniform equicontinuity. Then, we provide an approximation method to approximate the expected spread size for stable GOSMs. For the approximation method, we propose a concentration theorem that guarantees that a generalized mean-field theorem calculates the expected spreading size within small error bounds for finite time steps for a slightly dense network structure. Furthermore, we prove that a “single simulation” of running the Monte Carlo simulation is sufficient to approximate the expected spreading size. We conduct experiments on both synthetic and real-world networks and show that our generalized approximation method well predicts the state density of the various models, especially in graphs with a large number of nodes. Experimental results show that the generalized mean-field approximation and a single Monte Carlo simulation converge as shown in the concentration theorem.