Production Graph Algorithms

Real-world graph use cases drive algorithm choice:

Recommendation engines:

• "People who bought X also bought Y" — co-occurrence in graph.
• Collaborative filtering via random walks.

Fraud detection:

• Detect rings: cyclic transactions among accounts.
• Anomalous degree: account suddenly has 1000 outgoing edges.
• Community detection: cluster of accounts behaving in concert.

Knowledge graphs:

• Entity linking: map text mentions to graph nodes.
• Type inference via class hierarchies.
• Question answering via graph traversal.

Social network analysis:

• Influence: PageRank, eigenvector centrality.
• Communities: Louvain, label propagation.
• Triangles: count of A-B-C triangles indicates clustering.

Supply chain & dependency:

• Cycle detection (e.g., circular dependencies).
• Topological sort (build order).
• Critical path (project management).

Algorithm packages:

• Neo4j Graph Data Science (GDS): 70+ algorithms, in-memory projection.
• NetworkX (Python): algorithm-rich, single-machine.
• GraphScope (Alibaba): distributed graph compute.
• Pregel-style (Google): vertex-centric distributed compute. Spark GraphX, Apache Giraph.

Distributed graph compute:

• Pregel: each vertex = a worker, exchanges messages with neighbors.
• Iteratively: each superstep, vertices receive messages, compute, send.
• Used for PageRank, shortest path, label propagation at scale.

Approximate algorithms for huge graphs:

• HyperLogLog for distinct count.
• Bloom filters for membership.
• Sampling for centrality.

Real-world scale:

• Twitter follower graph: 1.5B users × dozens of edges each = ~50B edges.
• Knowledge graphs: 100B+ triples.
• Social: Facebook friend graph billions of users.

Single machine maxes out around 10B edges. Beyond: distributed compute.