Different parts of the graphs may have different number of iterations, which is more efficient than our implementation of PageRank in assignment 3, where the entire graph was iterated on while there was any vertex that had not yet converged.
jmc
Signal is a useful primitive because it allows you finer control of computation on the level of individual vertices. In the PageRank case, we can use it to improve efficiency by only iterating on those vertices whose PageRank has not yet converged.
Here's what I wasn't sure about. For the PageRank problem, if a particular vertex converges (i.e. its PageRank value changes by less than a predefined small threshold in an iteration), does that mean it is "permanently" converged and we will not have to update its value at all for the rest of the algorithm? Is it not possible that updates to values of other vertices in the graph could eventually make it so that running another iteration on the vertex would change its value by more than the convergence threshold?
bochet
It's interesting to notice that in this
slide, pagerank is written as gather based, in this slide it's scatter based. I think this is because here each node needs to decide whether it's converged or not, and notify the adjacent nodes depending on the result.
Different parts of the graphs may have different number of iterations, which is more efficient than our implementation of PageRank in assignment 3, where the entire graph was iterated on while there was any vertex that had not yet converged.
Signal is a useful primitive because it allows you finer control of computation on the level of individual vertices. In the PageRank case, we can use it to improve efficiency by only iterating on those vertices whose PageRank has not yet converged.
Here's what I wasn't sure about. For the PageRank problem, if a particular vertex converges (i.e. its PageRank value changes by less than a predefined small threshold in an iteration), does that mean it is "permanently" converged and we will not have to update its value at all for the rest of the algorithm? Is it not possible that updates to values of other vertices in the graph could eventually make it so that running another iteration on the vertex would change its value by more than the convergence threshold?
It's interesting to notice that in this slide, pagerank is written as gather based, in this slide it's scatter based. I think this is because here each node needs to decide whether it's converged or not, and notify the adjacent nodes depending on the result.