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 αあるふぁ = αあるふぁ₀ = 0.5, lets ranks converge quickly, and then switches to αあるふぁ = αあるふぁₑ = 0.85 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 αあるふぁₑ = 0.85 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 τたう = 10⁻⁵ 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 αあるふぁ = 0.85, 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 αあるふぁ₀ = 0.1). 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.