Table of Contents for
Graph Algorithms
Close
Version ebook
/
Retour
Graph Algorithms
by Amy E. Hodler
Published by O'Reilly Media, Inc., 2019
Cover
nav
Graph Algorithms
Graph Algorithms
Preface
1. Introduction
2. Graph Theory and Concepts
3. Graph Platforms and Processing
4. Pathfinding and Graph Search Algorithms
5. Centrality Algorithms
6. Community Detection Algorithms
7. Graph Algorithms in Practice
8. Using Graph Algorithms to Enhance Machine Learning
About the Authors
Preface
Conventions Used in This Book
What’s in This Book
Using Code Examples
O’Reilly Safari
How to Contact Us
Acknowledgments
1. Introduction
What Are Graphs?
What Are Graph Analytics and Algorithms?
Graph Databases versus Graph Processing
OLTP and OLAP
Why should I care about graph algorithms?
Graph Analytics Use Cases
Conclusion
2. Graph Theory and Concepts
Terminology
Basic Graph Types and Structures
Random, Small-World, Scale-Free Structures
Flavors of Graphs
Connected versus Disconnected Graphs
Unweighted Graphs versus Weighted Graphs
Undirected Graphs versus Directed Graphs
Acyclic Graphs versus Cyclic Graphs
Sparse Graphs versus Dense Graphs
Monopartite, Bipartite, and K-Partite Graphs
Types of Graph Algorithms
Pathfinding
Centrality
Community Detection
Summary
3. Graph Platforms and Processing
Graph Platform and Processing Considerations
Platform Considerations
Processing Considerations
Representative Platforms
Selecting Our Platform
Apache Spark
Neo4j Graph Platform
Summary
4. Pathfinding and Graph Search Algorithms
Example Data: The Transport Graph
Importing the data into Apache Spark
Importing the data into Neo4j
Breadth First Search
Breadth First Search with Apache Spark
Depth First Search
Shortest Path
When should I use Shortest Path?
Shortest Path (weighted) with Apache Spark
Shortest Path (weighted) with Neo4j
Shortest Path Variation: A*
Shortest Path Variation: Yen’s K-shortest paths
All Pairs Shortest Paths
A Closer Look at All Pairs Shortest Paths
When should I use All Pairs Shortest Path?
All Pairs Shortest Paths with Apache Spark
All Pairs Shortest Paths with Neo4j
Single Source Shortest Path
When should I use Single Source Shortest Path?
Single Source Shortest Path with Apache Spark
Single Source Shortest Path with Neo4j
Minimum Spanning Tree
When should I use Minimum Spanning Tree?
Minimum Spanning Tree with Neo4j
Random Walk
When should I use Random Walk?
Random Walk with Neo4j
Summary
5. Centrality Algorithms
Importing the data into Apache Spark
Importing the data into Neo4j
Degree Centrality
When Should I Use Degree Centrality?
Degree Centrality with Apache Spark
Closeness Centrality
When Should I Use Closeness Centrality?
Closeness Centrality with Apache Spark
Closeness Centrality with Neo4j
Closeness Centrality Variation: Wasserman and Faust
Closeness Centrality Variation: Harmonic Centrality
Betweenness Centrality
When Should I Use Betweenness Centrality?
Betweenness Centrality with Neo4j
Betweenness Centrality Variation: Randomized-Approximate Brandes
PageRank
Iteration, Random Surfers and Rank Sinks
When should I use PageRank?
PageRank with Apache Spark
PageRank with Neo4j
PageRank Variation: Personalized PageRank
Summary
6. Community Detection Algorithms
Example Graph Data: The Software Dependency Graph
Importing the data into Apache Spark
Importing the data into Neo4j
Triangle Count and Clustering Coefficient
When Should I Use Triangle Count and Clustering Coefficient?
Triangle Count with Apache Spark
Triangles with Neo4j
Local Clustering coefficient with Neo4j
Strongly Connected Components
When Should I Use Strongly Connected Components?
Strongly Connected Components with Apache Spark
Strongly Connected Components with Neo4j
Connected Components
When should I use Connected Components?
Connected Components with Apache Spark
Connected Components with Neo4j
Label Propagation
Semi-Supervised Learning and Seed Labels
When Should I Use Label Propagation?
Label Propagation with Apache Spark
Label Propagation with Neo4j
Louvain Modularity
7. Graph Algorithms in Practice
Analyzing Yelp Data with Neo4j
Data Import
Graph Model
A Quick Overview of the Yelp Data
Trip Planning App
Bellagio cross promotion
Analyzing Airline Flight Data with Apache Spark
Exploratory Analysis
Popular airports
Delays from ORD
Bad day at SFO
Interconnected airports by airline
Summary
8. Using Graph Algorithms to Enhance Machine Learning
Machine Learning and the Importance of Context
Graphs, Context, and Accuracy
Connected Feature Extraction and Selection
Graphs and Machine Learning in Practice: Link Prediction
Tools and Data
Importing the Data into Neo4j
Co-Authorship Graph
Creating Balanced Training and Testing Datasets
How We Predict Missing Links
Creating a Machine Learning Pipeline
Predicting Links: Basic graph features
Accuracy
Precision
Recall (True Positive Rate)
False Positive Rate
ROC Curve X-Y Chart
Predicting Links: Triangles and The Clustering Coefficient
Predicting Links: Community Detection
Wrapping Things Up
Summary