Design of PageRank algorithm for link analysis in JavaScript.
The idea behind this experiment (adjust-damping-factor-stepwise) was to
adjust the damping factor
in steps, to see if it might help reduce
PageRank computation time. The PageRank computation first starts with a small
initial damping factor
. After the ranks have converged, the damping
factor
is updated to the next damping factor step, say
and PageRank
computation is continued again. This is done until the final desired value of
is reached. For example, the computation starts initially with
,
lets ranks converge quickly, and then switches to
and
continues PageRank computation until it converges. This single-step change
is attempted with the initial (fast converge) damping factor
from 0.1
to 0.8
. Similar to this, two-step, three-step, and four-step changes are also
attempted. With a two-step approach, a midpoint between the initial
damping value
and
is selected as well for the second set of
iterations. Similarly, three-step and four-step approaches use two and
three midpoints respectively.
A small sample graph is used in this experiment, which is stored in
the MatrixMarket (.mtx) file format. The experiment is implemented in
Node.js, and executed on a personal laptop. Only the iteration count
of each test case is measured. The tolerance
is used for
all test cases. Statistics of each test case is printed to standard
output (stdout), and redirected to a log file, which is then processed
with a script to generate a CSV file, with each row representing the
details of a single test case. This CSV file is imported into Google
Sheets, and necessary tables are set up with the help of the FILTER
function to create the charts.
From the results it is clear that modifying the damping factor
in steps is not a good idea. The standard fixed damping factor
PageRank, with
, converges in 35
iterations. Using a
single-step approach increases the total number of iterations required,
by at least 4
iterations (with an initial damping factor
).
Increasing
further increases the total number of iterations needed
for computation. Switching to a multi-step approach also increases the
number of iterations needed for convergence. The two-step, three-step,
and four-step approaches require a total of atleast 49
, 60
, and 71
iterations respectively. Again, increasing
continues to increase
the total number of iterations needed for computation. A possible
explanation for this effect is that the ranks for different values of
the damping factor
are significantly different, and switching
to a different damping factor
after each step mostly leads to
recomputation.