Page 1
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
Page 3
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
Page 5
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
Page 6
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
Page 8
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 the number of computers who were affected by a particular computer virus in three days, thirty days since its discovery
Page 9
Challenge in Dealing with Graph Data • Flat Files – No Query Support • RDBMS – Can Store the Graph – Limited Support for Graph Query • Connect-By (Oracle) • Common Table Expressions (CTEs) (Microsoft) • Temporal Table
Page 10
Native Graph Databases • Emerging Field – http://en.wikipedia.org/wiki/Graph_database • Storage and Basic Operators – Neo4j (an open source graph database) – InfiniteGraph – VertexDB • Distributed Graph Processing (mostly in- memory-only) – Google’s Pregel (vertex centered computation)
Page 11
Graph analytics industry practice status • Graph data in many industries • Graph analytics are powerful and can bring great business values/insights • Graph analytics not utilized enough in enterprises due to lack of available platforms/tools (except leading tech companies which have high caliber in house engineering teams and resources)
Page 12
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 • Key questions: – How do you represent graph data in MapReduce? – How do you traverse a graph in MapReduce?
Page 14
Adjacency Matrices Represent a graph as an n x n square matrix M ⚫ n = |V| ⚫ Mij = 1 means a link from node i to j 1 2 3 4 2 1 0 1 0 1 1 2 1 0 1 1 3 3 1 0 0 0 4 1 0 1 0 4
Page 15
Adjacency Matrices: Critique • Advantages: – Amenable to mathematical manipulation – Iteration over rows and columns corresponds to computations on outlinks and inlinks • Disadvantages: – Lots of zeros for sparse matrices – Lots of wasted space
Page 16
Adjacency Lists Take adjacency matrices… and throw away all the zeros 1 2 3 4 1 0 1 0 1 1: 2, 4 2 1 0 1 1 2: 1, 3, 4 3 1 0 0 0 3: 1 4: 1, 3 4 1 0 1 0
Page 17
Adjacency Lists: Critique • Advantages: – Much more compact representation – Easy to compute over outlinks • Disadvantages: – Much more difficult to compute over inlinks
Page 18
Single Source Shortest Path • Problem: find shortest path from a source node to one or more target nodes – Shortest might also mean lowest weight or cost • First, a refresher: Dijkstra’s Algorithm
Affichage des 18 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !