Variable Damping Effect on Network Propagation

Abstract

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. Inspiteof extensive research conducted to accelerate the algorithm or its variants, there arefew studies about the effects of the damping factors on the ranking distribution.To understand how the damping factor can affect the rank distribution in differentPageRank models, specifically, the directed surfer model by Brin and Page, and theheat-kernel PageRank by Chung. We studied the ranking vector (steady state distri-bution) under different damping factor values with each model. Enabled by efficientbatch calculation of the ranking vectors, we conducted systematic experiments tomeasure the discrepancies of the distributions, explored and explained the capabilityof adjusting the steady-state distribution via the change in damping factors. Experi-mental results show that the steady-state distribution by Brin-Page model responsesnon-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 thisphenomenon, Brin-Page model may be preferable over Chung’s model on utilizingthe 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.