book

Graph Algorithms

by Mark Needham, Amy E. Hodler

May 2019

Intermediate to advanced

265 pages

5h 58m

English

O'Reilly Media, Inc.

Book available

Read now

Unlock full access

What’s in This BookConventions Used in This BookUsing Code ExamplesO’Reilly Online LearningHow to Contact UsAcknowledgments
What Are Graphs?What Are Graph Analytics and Algorithms?Graph Processing, Databases, Queries, and AlgorithmsOLTP and OLAPWhy Should We Care About Graph Algorithms?Graph Analytics Use CasesConclusion
TerminologyGraph Types and StructuresRandom, Small-World, Scale-Free StructuresFlavors of GraphsConnected Versus Disconnected GraphsUnweighted Graphs Versus Weighted GraphsUndirected Graphs Versus Directed GraphsAcyclic Graphs Versus Cyclic GraphsSparse Graphs Versus Dense GraphsMonopartite, Bipartite, and k-Partite GraphsTypes of Graph AlgorithmsPathfindingCentralityCommunity DetectionSummary
Graph Platform and Processing ConsiderationsPlatform ConsiderationsProcessing ConsiderationsRepresentative PlatformsSelecting Our PlatformApache SparkNeo4j Graph PlatformSummary
Example Data: The Transport GraphImporting the Data into Apache SparkImporting the Data into Neo4jBreadth First SearchBreadth First Search with Apache SparkDepth First SearchShortest PathWhen Should I Use Shortest Path?Shortest Path with Neo4jShortest Path (Weighted) with Neo4jShortest Path (Weighted) with Apache SparkShortest Path Variation: A*Shortest Path Variation: Yen’s k-Shortest PathsAll Pairs Shortest PathA Closer Look at All Pairs Shortest PathWhen Should I Use All Pairs Shortest Path?All Pairs Shortest Path with Apache SparkAll Pairs Shortest Path with Neo4jSingle Source Shortest PathWhen Should I Use Single Source Shortest Path?Single Source Shortest Path with Apache SparkSingle Source Shortest Path with Neo4jMinimum Spanning TreeWhen Should I Use Minimum Spanning Tree?Minimum Spanning Tree with Neo4jRandom WalkWhen Should I Use Random Walk?Random Walk with Neo4jSummary
Example Graph Data: The Social GraphImporting the Data into Apache SparkImporting the Data into Neo4jDegree CentralityReachWhen Should I Use Degree Centrality?Degree Centrality with Apache SparkCloseness CentralityWhen Should I Use Closeness Centrality?Closeness Centrality with Apache SparkCloseness Centrality with Neo4jCloseness Centrality Variation: Wasserman and FaustCloseness Centrality Variation: Harmonic CentralityBetweenness CentralityWhen Should I Use Betweenness Centrality?Betweenness Centrality with Neo4jBetweenness Centrality Variation: Randomized-Approximate BrandesPageRankInfluenceThe PageRank FormulaIteration, Random Surfers, and Rank SinksWhen Should I Use PageRank?PageRank with Apache SparkPageRank with Neo4jPageRank Variation: Personalized PageRankSummary
Example Graph Data: The Software Dependency GraphImporting the Data into Apache SparkImporting the Data into Neo4jTriangle Count and Clustering CoefficientLocal Clustering CoefficientGlobal Clustering CoefficientWhen Should I Use Triangle Count and Clustering Coefficient?Triangle Count with Apache SparkTriangles with Neo4jLocal Clustering Coefficient with Neo4jStrongly Connected ComponentsWhen Should I Use Strongly Connected Components?Strongly Connected Components with Apache SparkStrongly Connected Components with Neo4jConnected ComponentsWhen Should I Use Connected Components?Connected Components with Apache SparkConnected Components with Neo4jLabel PropagationSemi-Supervised Learning and Seed LabelsWhen Should I Use Label Propagation?Label Propagation with Apache SparkLabel Propagation with Neo4jLouvain ModularityWhen Should I Use Louvain?Louvain with Neo4jValidating CommunitiesSummary
Analyzing Yelp Data with Neo4jYelp Social NetworkData ImportGraph ModelA Quick Overview of the Yelp DataTrip Planning AppTravel Business ConsultingFinding Similar CategoriesAnalyzing Airline Flight Data with Apache SparkExploratory AnalysisPopular AirportsDelays from ORDBad Day at SFOInterconnected Airports by AirlineSummary
Machine Learning and the Importance of ContextGraphs, Context, and AccuracyConnected Feature EngineeringGraphy FeaturesGraph Algorithm FeaturesGraphs and Machine Learning in Practice: Link PredictionTools and DataImporting the Data into Neo4jThe Coauthorship GraphCreating Balanced Training and Testing DatasetsHow We Predict Missing LinksCreating a Machine Learning PipelinePredicting Links: Basic Graph FeaturesPredicting Links: Triangles and the Clustering CoefficientPredicting Links: Community DetectionSummaryWrapping Things Up

Other AlgorithmsNeo4j Bulk Data Import and YelpAPOC and Other Neo4j ToolsFinding DatasetsAssistance with the Apache Spark and Neo4j PlatformsTraining

Overview

Learn how graph algorithms can help you leverage relationships within your data to develop intelligent solutions and enhance your machine learning models. With this practical guide,developers and data scientists will discover how graph analytics deliver value, whether they’re used for building dynamic network models or forecasting real-world behavior.

Mark Needham and Amy Hodler from Neo4j explain how graph algorithms describe complex structures and reveal difficult-to-find patterns—from finding vulnerabilities and bottlenecksto detecting communities and improving machine learning predictions. You’ll walk through hands-on examples that show you how to use graph algorithms in Apache Spark and Neo4j, two of the most common choices for graph analytics.