1、Graph Algorithm闫宏飞北京大学信息科学技术学院7/16/2012http:/ This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United StatesSee http:/creativecommons.org/licenses/by-nc-sa/3.0/us/ for detailsJimmy LinUniversity of Maryland SEWMGroupTodays Agenda Graph problems and representat
2、ions Parallel breadth-first search PageRank2Whats a graph? G = (V,E), wherel V represents the set of vertices (nodes)l E represents the set of edges (links)l Both vertices and edges may contain additional information Different types of graphs:l Directed vs. undirected edgesl Presence or absence of c
3、ycles Graphs are everywhere:l Hyperlink structure of the Webl Physical structure of computers on the Internetl Interstate highway systeml Social networks3Source: Wikipedia (Knigsberg)456 Some Graph Problems Finding shortest pathsl Routing Internet traffic and UPS trucks Finding minimum spanning tree
4、sl Telco laying down fiber Finding Max Flowl Airline scheduling Identify “special” nodes and communitiesl Breaking up terrorist cells, spread of avian flu Bipartite matchingl M, M And of course. PageRank7Graphs and MapReduce Graph algorithms typically involve:l Performing computations at each node:
5、based on node features, edge features, and local link structurel Propagating computations: “traversing” the graph Key questions:l How do you represent graph data in MapReduce?l How do you traverse a graph in MapReduce?8Representing Graphs G = (V, E) Two common representationsl Adjacency matrixl Adjacency list9Adjacency MatricesRepresent a graph as an n x n square matrix Ml n = |V|l Mij = 1 means a link from node i to j1 2 3 41 0 1 0 12 1 0 1 13 1 0 0 04 1 0 1 0123410
