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 3. Graph Platforms and Processing

In this chapter, we’ll quickly cover different methods for graph processing and the most common platform approaches. We’ll look more closely at the two platforms used in this book, Apache Spark and Neo4j, and when they may be appropriate for different requirements. Platform installation guidelines are included to prepare you for the next several chapters.

Graph Platform and Processing Considerations

Graph analytical processing has unique qualities such as computation that is structure-driven, globally focused, and difficult to parse. In this section we’ll look at the general considerations for graph platforms and processing.

Platform Considerations

There’s debate as to whether it’s better to scale up or scale out graph processing. Should you use powerful multicore, large-memory machines and focus on efficient data structures and multithreaded algorithms? Or are investments in distributed processing frameworks and related algorithms worthwhile?

A useful evaluation approach is the Configuration that Outperforms a Single Thread (COST), as described in the research paper “Scalability! But at What COST?” by F. McSherry, M. Isard, and D. Murray. COST provides us with a way to compare a system’s scalability with the overhead the system introduces. The core concept is that a well-configured system using an optimized algorithm and data structure can outperform current general-purpose scale-out solutions. It’s a method for measuring performance ...