大规模数据处理与云计算-图与路由算法.ppt

* Stopping Criterion How many iterations are needed in parallel BFS (positive edge weight case)? Practicalities of implementation in MapReduce * Graphs and MapReduce Graph algorithms typically involve: Performing computations at each node: based on node features, edge features, and local link structure Propagating computations: “traversing” the graph Generic recipe: Represent graphs as adjacency lists Perform local computations in mapper Pass along partial results via outlinks, keyed by destination node Perform aggregation in reducer on inlinks to a node Iterate until convergence: controlled by external “driver” Don’t forget to pass the graph structure between iterations * Random Walks Over the Web Random surfer model: User starts at a random Web page User randomly clicks on links, surfing from page to page PageRank Characterizes the amount of time spent on any given page Mathematically, a probability distribution over pages PageRank captures notions of page importance Correspondence to human intuition? One of thousands of features used in web search Note: query-independent * Given page x with inlinks t1…tn, where C(t) is the out-degree of t ? is probability of random jump N is the total number of nodes in the graph PageRank: Defined X t1 t2 tn … * Computing PageRank Properties of PageRank Can be computed iteratively Effects at each iteration are local Sketch of algorithm: Start with seed PRi values Each page distributes PRi “credit” to all pages it links to Each target page adds up “credit” from multiple in-bound links to compute PRi+1 Iterate until values converge * Simplified PageRank First, tackle the simple case: No random jump factor No dangling links Then, factor in these complexities… Why do we need the random jump? Where do dangling links come from? * Sample PageRank Iteration (1) n1 (0.2) n4 (0.2) n3 (0.2) n5 (0.2) n2 (0.2) 0.1 0.1 0.2 0.2 0.1 0.1 0.066 0.066 0.066 n1 (0.066) n4 (0.3) n3 (0.166) n5 (0.3) n2 (0.166) Iteration 1 * Sample PageRank Itera