Design of Levelwise Dynamic PageRank algorithm for link analysis.
Levelwise PageRank is the STIC-D algorithm, without ICD optimizations (using a single-thread here). We use a rank pull based approach, and perform the computation upon the CSR representation of a graph. If the size of a component is fewer than 50 vertices, we combine multiple components together (comp-50). To take into account removed/added vertices upon the dynamic graph, we scale the previous ranks using the scaled-fill approach.
We attempt each experiment (mentioned below) on different types of graphs,
running each with multiple batch sizes (1, 5, 10, 50, ...). Each
pagerank computation was run 5 times for both approaches to get a good time
measure. The input data used for each experiment is available at "graphs" (for
small ones), the SuiteSparse Matrix Collection, and the Stanford Large
Network Dataset Collection. Experiments were done with guidance from Prof. Dip
Sankar Banerjee and Prof. Kishore Kothapalli.
We first check the correctness of Levelwise PageRank when unchanged (unaffected) components are skipped (validate-skip-unchanged-components). We then perform the same experiment as above, but skip the unchanged components with Levelwise PageRank. On average, we observe that skipping unchanged components is barely faster than not skipping; on both temporal graphs (skip-unchanged-components), and fixed graphs with randomly generated batches of edge insertions (skip-unchanged-components-with-mtx-insertions).
In this experiment (compare-monolithic, main), we compare the performance of static and dynamic Monolithic/Levelwise PageRank on temporal graphs. Our results indicated that dynamic Levelwise PageRank faster is than the static approach for most batch sizes. We repeat this experiment on fixed graphs with randomly generated batches of edge insertions (with-mtx-insertions), and observe a similar result.
- STIC-D: algorithmic techniques for efficient parallel pagerank computation on real-world graphs
- PageRank Algorithm, Mining massive Datasets (CS246), Stanford University
- Stanford Large Network Dataset Collection
- SuiteSparse Matrix Collection
- Merge git repo into branch of another repo
