Map-Reduce Graph Processing Adapted from UMD Jimmy Lin’s slides, which is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States. See http://creativecommons.org/licenses/by-nc-sa/3.0/us/ for details Roadmap Graph problems and representations Parallel breadth-first search PageRank What’s a graph? G = (V,E), where V represents the set of vertices (nodes) E represents the set of edges (links) Both vertices and edges may contain additional information Different types of graphs: Directed vs. undirected edges Presence or absence of cycles Graphs are everywhere: Hyperlink structure of the Web Physical structure of computers on the Internet Interstate highway system Social networks Source: Wikipedia (Königsberg) Some Graph Problems Finding shortest paths Routing Internet traffic and UPS trucks Finding minimum spanning trees Telco laying down fiber Finding Max Flow Airline scheduling Identify “special” nodes and communities Breaking up terrorist cells, spread of avian flu Bipartite matching Monster.com, Match.com And of course... PageRank Ubiquitous Network (Graph) Data Social Network Biological Network Road Network/Map WWW Sematic Web/Ontologies XML/RDF …. Semantic Search, Guha et. al., WWW’03 http://belanger.wordpress.com/2007/06/28/ the-ebb-and-flow-of-social-networking/ 6 Graph (and Relational) Analytics General Graph Count the number of nodes whose degree is equal to 5 Find the diameter of the graphs Web Graph Rank each webpage in the webgraph or each user in the twitter graph using PageRank, or other centrality measure Transportation Network Return the shortest or cheapest flight/road from one city to another Social Network Determine whether there is a path less than 4 steps which connects two users in a social network Financial Network Find the path connecting two suspicious transactions; Temporal Network Compute th