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

Content preview from Graph Algorithms

Chapter 7. Graph Algorithms in Practice

The approach we take to graph analysis evolves as we become more familiar with the behavior of different algorithms on specific datasets. In this chapter, we’ll run through several examples to give you a better feeling for how to tackle large-scale graph data analysis using datasets from Yelp and the US Department of Transportation. We’ll walk through Yelp data analysis in Neo4j that includes a general overview of the data, combining algorithms to make trip recommendations, and mining user and business data for consulting. In Spark, we’ll look into US airline data to understand traffic patterns and delays as well as how airports are connected by different airlines.

Because pathfinding algorithms are straightforward, our examples will use these centrality and community detection algorithms:

PageRank to find influential Yelp reviewers and then correlate their ratings for specific hotels
Betweenness Centrality to uncover reviewers connected to multiple groups and then extract their preferences
Label Propagation with a projection to create supercategories of similar Yelp businesses
Degree Centrality to quickly identify airport hubs in the US transport dataset
Strongly Connected Components to look at clusters of airport routes in the US

Analyzing Yelp Data with Neo4j

Yelp helps people find local businesses based on reviews, preferences, and recommendations. Over 180 million reviews had been written on the platform as of the end of ...