Graph Algorithms

This is a “graph algorithms topic navigation” page. The goal is not to stack articles together, but to give you an executable learning path from basic traversal to distributed graph computation. Current Directory Status (Topic Structuring Completed) The graph algorithms series has been migrated to: content/zh/dev/algorithm/graph/ It also uses two-digit prefixes (00/10/20...) to mark reading order, which makes it easier to: Browse in sequence within the file system Insert new articles incrementally later (while preserving numbering gaps) Locate stages quickly during batch maintenance Recommended Reading Order (By Capability Building) Stage 0: Traversal Fundamentals (Lay the Foundation First) BFS / DFS Engineering Intro: k-hop Queries, Subgraph Extraction, and Path Reachability Shortest Path in Practice: Engineering Selection of BFS, Dijkstra, and A* Goals: ...

A systematic walkthrough of Pregel (BSP) and GAS (Gather-Apply-Scatter), focused on execution paths, convergence strategies, and engineering trade-offs for PageRank, Connected Components, and parallel BFS.

Starting from Edge-cut/Vertex-cut objective functions, this article systematically explains METIS-style multilevel partitioning and production implementation, with emphasis on how partitioning affects query latency and cross-machine traffic.

Subtitle / Abstract In dynamic-graph workloads, the real pain point is not “do you know the algorithm,” but “can the system survive continuous updates.” Following the ACERS template, this article explains three engineering essentials: incremental shortest path, incremental PageRank, and connectivity maintenance, along with three practical strategies: local recomputation, lazy updates, and approximate results. Estimated reading time: 14-18 minutes Tags: dynamic graph, incremental computation, shortest path, PageRank, connectivity maintenance SEO keywords: dynamic graph, incremental shortest path, incremental PageRank, connectivity maintenance, local recomputation, lazy updates, approximate results Meta description: An engineering guide to dynamic graphs: how to control latency and cost in high-frequency update scenarios with incremental algorithms and practical system strategies. Target Audience Engineers building online services for graph databases, relationship graphs, and recommendation graphs Developers moving from offline graph computation to real-time incremental computation Tech leads who want to replace “full recomputation” with a production-ready update pipeline Background / Motivation Static graph algorithms look elegant in papers, but real production graphs are constantly changing: ...

Subtitle / Abstract Community detection is not just “splitting a graph into a few groups.” In production, you must balance accuracy, interpretability, speed, and maintainability. Following the ACERS structure, this article breaks down two of the most common engineering choices: Louvain (modularity optimization) and Label Propagation (LPA). Estimated reading time: 12-16 minutes Tags: Community Detection, Louvain, Label Propagation, Graph Partitioning SEO keywords: community detection, Louvain, Label Propagation, modularity, graph partition Meta description: Engineering primer for community detection: principles, complexity, algorithm selection, and implementation templates for Louvain and LPA across group discovery, graph partitioning, and cold start. Target Audience Engineers working on social graphs, risk-control graphs, or recommender-system graph analytics Developers who want to move community detection from paper concepts into production workflows Practitioners modeling group structure for graph partitioning and cold-start scenarios Background / Motivation Community detection appears frequently in production: ...

Subtitle / Abstract Subgraph matching is one of the hardest parts of graph querying: NP-hard in theory, but not automatically “too slow” in production. Following the ACERS template, this article explains VF2 and Ullmann clearly, and focuses on what actually decides performance: candidate generation and pruning strategy. Estimated reading time: 15-20 minutes Tags: Subgraph Matching, VF2, Ullmann, Graph Database SEO keywords: Subgraph Isomorphism, VF2, Ullmann, candidate pruning, graph pattern matching Meta description: Starting from NP-hard subgraph isomorphism, this article explains VF2/Ullmann mechanics and practical pruning strategies for constrained graph-database pattern queries. Target Audience Engineers building pattern queries, rule detection, or risk-relationship mining in graph databases Developers who already know BFS/DFS/connected components and want stronger graph-matching skills Algorithm practitioners balancing explainable rule matching against performance limits Background / Motivation In graph databases, you regularly face requirements like: ...

Subtitle / Abstract Centrality is not just a paper concept. In graph systems, it is a practical node-importance ranking engine. This article follows the ACERS structure to explain Degree / Betweenness / Closeness and gives one pragmatic conclusion: most online systems reliably support only Degree + approximate Betweenness. Estimated reading time: 12-16 minutes Tags: Graph Theory, Centrality, Degree, Betweenness, Closeness SEO keywords: graph centrality, Degree Centrality, Betweenness, Closeness, approximate Betweenness Meta description: Engineering guide to graph centrality: definitions, complexity, approximation methods, and production strategies, with runnable code. Target Audience Engineers working on relationship graph analysis, knowledge graphs, or graph-database query optimization Developers who need to turn “node importance” from concept into production metric Practitioners who want to understand why Betweenness is expensive in production and how to approximate it Background / Motivation In graph systems, you will eventually face questions like these: ...

Subtitle / Abstract Connectivity tells you how a graph is partitioned, while PageRank tells you who matters inside each component. This is one of the core advantages of graph databases over relational databases: not only linking data, but propagating structural importance. This article follows ACERS to explain PageRank / PPR principles and production implementation. Estimated reading time: 15-20 minutes Tags: PageRank, PPR, Graph Database, Sparse Matrix SEO keywords: PageRank, Personalized PageRank, sparse matrix, incremental updates, graph database Meta description: From classic PageRank to Personalized PageRank, covering iterative computation, sparse-matrix optimization, and incremental update strategy, with runnable multi-language implementations. Target Audience Engineers building ranking, recommendation, or influence analysis on graph databases Developers who already know BFS/DFS/connected components and want to level up to graph scoring Algorithm engineers focused on iteration performance and update latency on large online graphs Background / Motivation You may already have split graphs into connected components and SCCs, but production systems still face a harder question: ...

This article walks through k-hop and reachability queries in practice: BFS+hop limits, transitive-closure tradeoffs, and engineering rollout paths for bitmap indexes and 2-hop labeling.

Subtitle / Abstract Components are foundational for graph algorithms: undirected graphs ask “are nodes connected,” while directed graphs ask “are nodes mutually reachable.” Following the ACERS template, this article moves from naive methods to Tarjan / Kosaraju, then shows production graph-database use cases with runnable multi-language code. Estimated reading time: 14-18 minutes Tags: Graph Theory, Connected Components, SCC, Tarjan SEO keywords: Connected Components, SCC, Tarjan, Kosaraju, graph database Meta description: From undirected connected components to directed SCCs, with clear Tarjan/Kosaraju mechanics, complexity, and production rollout guidance. Target Audience Learners who need BFS/DFS to become second nature Engineers doing subgraph analysis and partition planning in graph-database systems Intermediate developers who want one unified framework for “undirected CC + directed SCC” Background / Motivation In production, you quickly hit three types of questions: ...