Graph algorithms are used to compute metrics for graphs, nodes, or relationships. They can provide insights on relevant entities in the graph (centralities, ranking), or inherent structures like communities (community-detection, graph-partitioning, clustering).
Many graph algorithms are iterative approaches that frequently traverse the graph for the computation using random walks, breadth-first or depth-first searches, or pattern matching.
Due to the exponential growth of possible paths with increasing distance, many of the approaches also have high algorithmic complexity.
Fortunately, optimized algorithms exist that utilize certain structures of the graph, memoize already explored parts, and parallelize operations. Whenever possible, we’ve applied these optimizations.
- PageRank algorithm
- Betweenness Centrality algorithm
- Closeness Centrality algorithm
- Harmonic Centrality algorithm
- Minimum Weight Spanning Tree algorithm
- Shortest Path algorithm
- Single Source Shortest Path algorithm
- A* algorithm
- Yen’s K-shortest paths algorithm
- All Pairs Shortest Path algorithm
- Triangle Counting / Clustering Coefficient algorithm
- Label Propagation algorithm
- Louvain algorithm
- Connected Components algorithm
- Strongly Connected Components algorithm
- Random Walk algorithm