A Novel Exploration of Diffusion Process based on Multi-types Galton-Watson Forests
This provides a theoretical foundation for understanding diffusion in graph-based systems like PageRank, though it appears incremental in its application to existing methods.
The paper tackled the problem of interpreting diffusion processes on graphs by establishing an equivalence with a degenerated multi-types Galton-Watson forest model, resulting in improved convergence behavior for iterative diffusion and Google PageRank systems.
Diffusion is a commonly used technique for spreading information from point to point on a graph. The rationale behind diffusion is not clear. And the multi-types Galton-Watson forest is a random model of population growth without space or any other resource constraints. In this paper, we use the degenerated multi-types Galton-Watson forest (MGWF) to interpret the diffusion process and establish an equivalent relationship between them. With the two-phase setting of the MGWF, one can interpret the diffusion process and the Google PageRank system explicitly. It also improves the convergence behaviour of the iterative diffusion process and Google PageRank system. We validate the proposal by experiment while providing new research directions.