Variable Damping Effect on Network Propagation

Sun, Xiaobai

Qian, Yuchen

2018-05-31T21:19:05Z

2018-05-31T21:19:05Z

2018

Computer Science

In modern network analysis, the PageRank algorithm has been used as an indispens-

able tool to determine the importance and relevance of the network nodes. Inspite

of extensive research conducted to accelerate the algorithm or its variants, there are

few studies about the effects of the damping factors on the ranking distribution.

To understand how the damping factor can affect the rank distribution in different

PageRank models, specifically, the directed surfer model by Brin and Page, and the

heat-kernel PageRank by Chung. We studied the ranking vector (steady state distri-

bution) under different damping factor values with each model. Enabled by efficient

batch calculation of the ranking vectors, we conducted systematic experiments to

measure the discrepancies of the distributions, explored and explained the capability

of adjusting the steady-state distribution via the change in damping factors. Experi-

mental results show that the steady-state distribution by Brin-Page model responses

non-linearly to the change in damping factor α, while by Chung’s heat-kernel model,

the damping factor β casts negligble effect on steady-state distribution. With this

phenomenon, Brin-Page model may be preferable over Chung’s model on utilizing

the non-linear relationship between the damping factor and steady-state distribution.

The relationship can be utilized also to find the propagation speed(damping factor)

from observations of two or more consecutive distributions.

https://hdl.handle.net/10161/17067

Computer science

Damping Factor

Distribution

KL divergence

PageRank

Variable Damping Effect on Network Propagation

Master's thesis