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

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.

Figure 1

“$S$” state density for the SIS model with the parametric value sets $P_1$ and $P_2$ and initial state distribution $D_1=(0.4,0.6)$. (a) $P_1, B{A}_{10000}$, (b) $P_1$, Slashdot, (c) $P_2, B{A}_{10000}$, (d) $P_2$, Slashdot.

Figure 2

Error with respect to the true expected density of state $S$ for the SIS model with parametric value sets (a) $P_1$ and (b) $P_2$ and initial state distribution $D_1=(0.4,0.6)$ on the $B{A}_{10000}$ data set.

Figure 3

Error with respect to the true expected density of state $S$ at time $t=50$ for the SIS model with a fixed value of $\gamma =0.001$, various values of $\beta$ and initial state distribution $D_1=(0.4,0.6)$.

Figure 4

Positive state density for the binary voter model with data sets (a) $W{S}_{1000,10}$ and (b) $W{S}_{10000,100}$.

Figure 5

State density for the DAU model with the self-sustainable parametric value set $P_1$ and the initial state distribution $D_1=(0.5,0.4,0.1)$. The set $W$ contains all nodes with nonzero (in)degrees. (a) $B{A}_{10000}$, (b) Gowalla.

Figure 6

State density for the DAU model with the self-sustainable parametric value set $P_1$ and the initial state distribution $D_1=(0.5,0.4,0.1)$. The set $W$ contains the (a) top $1\%$, (b) $5\%$, or (c) $10\%$ of the nodes as ranked by (in)degree.

Figure 7

State density for the DAU model with the unsustainable parametric value set $P_2$ and the initial state distribution $D_2=(0.7,0.1,0.2)$. The set $W$ contains all nodes with nonzero (in)degrees. (a) $B{A}_{10000}$, (b) Gowalla.

Figure 8

State density for the DAU model with the unsustainable parametric value set $P_1$ and data sets (a) $B{A}_{10000}$ and (b) Gowalla. Initially, the nodes with the top 50 highest (in)degrees are selected as active nodes, while all other nodes are in the “nonmember” state. The set $W$ contains all nodes with nonzero (in)degrees.

Figure 9

State density for the DAU model with the unsustainable parametric value set $P_1$ and data set $B{A}_{10000}$. Initially, the nodes with the top 50 highest (in)degree are selected as active nodes, while the other nodes are in the “nonmember” state. The set $W$ contains the (a) top $1\%$, (b) $5\%$, or (c) $10\%$ of the nodes as ranked by (in)degree.

Figure 10

Results for the DAU model with the self-sustainable parametric value set $P_1$ and the initial state distribution $D_1=(0.5,0.4,0.1)$. The set $W$ contains all nodes with nonzero (in)degrees. (a) $W{S}_{1000,10}$, (b) $W{S}_{10000,100}$, (c) $B{A}_{1000}$, (d) Slashdot.

Figure 11

Results for the DAU model with the unsustainable parametric value set $P_2$ and the initial state distribution $D_2=(0.7,0.1,0.2)$. The set $W$ contains all nodes with nonzero (in)degrees. (a) $W{S}_{1000,10}$, (b) $W{S}_{10000,100}$, (c) $B{A}_{1000}$, (d) Slashdot.

Figure 12

Results for the DAU model with the unsustainable parametric value set $P_1$ and Gowalla data set. Initially, the nodes with the top 50 highest (in)degree are selected as active nodes, while the other nodes are in the “nonmember” state. The set $W$ contains the (a) top $1\%$, (b) $5\%$, or (c) $10\%$ of the nodes as ranked by (in)degree.