Link Evolution: Analysis and Algorithms As the web grows, its link structure (and content) evolves rapidly. Consequently, large-scale static hyperlink-based ranking computations become too expensive to be performed frequently. We present an efficient algorithm to incrementally compute good approximations to PageRank, as links evolve. Theoretical analysis of our algorithm suggests it should work well, and preliminary experiments reveal that this algorithm is both fast and yields excellent approximations to PageRank, even in light of large changes to the link structure. Analysis of the algorithm lead us to two monotonicity results for Markov Chains. For PageRank our results imply that (1) adding a link to a page cannot cause the PageRank of the target page to decrease and (2) adding a link to a page cannot cause the ordinal ranking of the target page to decrease. Joint work with Steve Chien, Ravi Kumar, Daniel Simon, and D. Sivakumar.