Article Contents
Article Contents

# Influence prediction for continuous-time information propagation on networks

• * Corresponding author: Xiaojing Ye
• We consider the problem of predicting the time evolution of influence, defined by the expected number of activated (infected) nodes, given a set of initially activated nodes on a propagation network. To address the significant computational challenges of this problem on large heterogeneous networks, we establish a system of differential equations governing the dynamics of probability mass functions on the state graph where each node lumps a number of activation states of the network, which can be considered as an analogue to the Fokker-Planck equation in continuous space. We provides several methods to estimate the system parameters which depend on the identities of the initially active nodes, the network topology, and the activation rates etc. The influence is then estimated by the solution of such a system of differential equations. Dependency of the prediction error on the parameter estimation is established. This approach gives rise to a class of novel and scalable algorithms that work effectively for large-scale and dense networks. Numerical results are provided to show the very promising performance in terms of prediction accuracy and computational efficiency of this approach.

Mathematics Subject Classification: Primary: 65C40, 65Y10; Secondary: 68U35.

 Citation:

• Figure 1.  Influence prediction on small sized network (when our matlab implementation of $\texttt{FPE-dist}$ still takes short time in computing). Left two: Erdős-Rényi's network of size $K = 16, 32$. Right: Small-world network $K = 32$. Average degree $(1/K)\sum_i|N_i^{{\rm out}}| = 4$

Figure 2.  Influence prediction on Left: Erdős-Rényi's network, Middle: small-world network, and Right: scale-free network. All have size $K = 1024$ and average degree are $(1/K)\sum_i|N_i^{{\rm out}}| = 8, 6, 6$ respectively

Figure 3.  Left: Influence prediction on dense Erdős-Rényi's random network with $K = 1024$ and $(1/K)\sum_i|N_i^{{\rm out}}| = 32, 64,128$ respectively. Middle: Influence prediction on the same Kronecker network of size $1024$ using three different choices of source set $S_1, S_2, S_3$ ($|S_i| = 10$ in all three cases). Right: Comparison with the state-of-the-arts learning-based ConTinEst method

Figure 4.  Top row: $\hat q_k$ estimated in $\texttt{FPE-dist}$ and $q_k(t)$ shown by ground truth (MCMC simulation) for $k = 10, 70,130,190$ using a dense Erdős-Rényi's network of size $K = 300$ and average degree $150$. Bottom row from left to right: $|\hat\rho_k(t)-\rho_k(t)|/\rho_k(t)$; $|\hat\mu(t)-\mu(t)|/\mu(t)$ and plot of $\mu(t)$ and $\hat\mu(t)$ for this $K = 300$ network; and CPU time (in seconds) of $\texttt{FPE-dist}$ using Runge-Kutta 4th order ODE solver on networks with $K$ range from $10^4$ to $10^8$

Figures(4)