Graph Algorithms in Practice

📋 At a Glance

┌─────────────────────────────────────────────────────────────────┐
│           GRAPH ALGORITHMS IN THE REAL WORLD                    │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  SOCIAL NETWORKS              SEARCH & RANKING                  │
│  ┌─────────────────┐          ┌─────────────────┐               │
│  │  U1 ─── U2      │          │    PageRank     │               │
│  │   │ ╲   │       │          │   ┌───┐         │               │
│  │   │  ╲  │       │          │  →│ A │→ 0.35   │               │
│  │  U3 ─── U4      │          │   └───┘         │               │
│  │                 │          │    ↓ ↓          │               │
│  │ Friend-of-friend│          │  ┌───┐ ┌───┐    │               │
│  │ recommendations │          │  │ B │ │ C │    │               │
│  └─────────────────┘          │  └───┘ └───┘    │               │
│                               └─────────────────┘               │
│                                                                 │
│  COMMUNITY DETECTION          RECOMMENDATIONS                   │
│  ┌─────────────────┐          ┌─────────────────┐               │
│  │ ┌─────┐ ┌─────┐ │          │  User → Item    │               │
│  │ │     │ │     │ │          │   ↓      ↓      │               │
│  │ │  A  │─│  B  │ │          │ Similar users   │               │
│  │ │     │ │     │ │          │ bought this     │               │
│  │ └─────┘ └─────┘ │          │                 │               │
│  │   Clusters      │          │ Collaborative   │               │
│  └─────────────────┘          │ filtering       │               │
│                               └─────────────────┘               │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

1. Analyze social networks: Calculate centrality measures, find influencers
2. Implement PageRank: Understand and code the algorithm behind Google
3. Detect communities: Use modularity-based algorithms
4. Build recommendation systems: Graph-based collaborative filtering
5. Use graph databases: Basic Neo4j patterns

🔥 Production Story: The Friend Recommendation Engine

A social gaming platform grew to 50 million users. Their friend recommendation system was struggling - suggestions were irrelevant, and user engagement was dropping.

The Problem

❌ Original system (2018):
- Simple: "People who played same game"
- Result: Recommending strangers with one common game
- Click-through rate: 2.1%
- Friend request acceptance: 0.8%

The team realized they needed to understand the social graph structure.

The Investigation

JAVA(17 lines)
Code
Loading syntax highlighter...

The Solution

They implemented a multi-signal graph-based approach:

JAVA(54 lines)
Code
Loading syntax highlighter...
Show all 54 lines

The Impact

🧠 Mental Model: The Social Graph

Think of a social network as a city with different neighborhoods:

┌─────────────────────────────────────────────────────────────────┐
│                    SOCIAL GRAPH AS A CITY                       │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  CENTRALITY = IMPORTANCE                                        │
│  ┌─────────────────────────────────────────────────────────┐   │
│  │                                                         │   │
│  │  Degree: How many direct connections (popular person)   │   │
│  │     👤─👤─👤                                            │   │
│  │        └─👤                                             │   │
│  │                                                         │   │
│  │  Betweenness: How many paths go through you (broker)    │   │
│  │     👤──[👤]──👤   (bridge between groups)             │   │
│  │     👤     👤                                          │   │
│  │                                                         │   │
│  │  Closeness: How quickly you can reach everyone          │   │
│  │     (central location)                                  │   │
│  │                                                         │   │
│  │  PageRank: Who points to you matters                    │   │
│  │     (endorsed by important people)                      │   │
│  │                                                         │   │
│  └─────────────────────────────────────────────────────────┘   │
│                                                                │
│  COMMUNITIES = NEIGHBORHOODS                                   │
│  ┌─────────────────────────────────────────────────────────┐   │
│  │                                                         │   │
│  │    ┌─────────┐      ┌─────────┐      ┌─────────┐        │   │
│  │    │ Gaming  │──────│ Bridge  │──────│  Tech   │        │   │
│  │    │ Friends │      │ Person  │      │ Friends │        │   │
│  │    │ 👤👤👤  │      │   👤    │      │ 👤👤👤  │       │   │
│  │    └─────────┘      └─────────┘      └─────────┘        │   │
│  │                                                         │   │
│  │    Dense connections within, sparse between             │   │
│  │                                                         │   │
│  └─────────────────────────────────────────────────────────┘   │
│                                                                │
└────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: Centrality Measures

Degree Centrality

The simplest measure - just count connections:

JAVA(34 lines)
Code
Loading syntax highlighter...

Betweenness Centrality

Measures how often a node appears on shortest paths:

JAVA(90 lines)
Code
Loading syntax highlighter...
Show all 90 lines

┌─────────────────────────────────────────────────────────────────┐
│                 BETWEENNESS CENTRALITY                          │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│     A ─── B ─── C                                               │
│     │           │                                               │
│     D ───[E]─── F     E has high betweenness                    │
│     │           │     (bridge between left and right)           │
│     G ─── H ─── I                                               │
│                                                                 │
│  Shortest paths through E:                                      │
│  A↔F, A↔I, B↔D, B↔G, C↔D, C↔G, etc.                             │
│                                                                 │
│  Betweenness(E) = Σ (paths through E / total paths)             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Closeness Centrality

How close a node is to all others:

JAVA(48 lines)
Code
Loading syntax highlighter...
Show all 48 lines

🔬 Deep Dive: PageRank Algorithm

The Intuition

PageRank models a "random surfer" browsing the web:

┌─────────────────────────────────────────────────────────────────┐
│                    PAGERANK INTUITION                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Random Surfer Model:                                           │
│  1. Start on a random page                                      │
│  2. With probability d (0.85), follow a random link             │
│  3. With probability (1-d), jump to random page                 │
│  4. PageRank = long-term probability of being on each page      │
│                                                                 │
│  Example:                                                       │
│       ┌─────────────────┐                                       │
│       │                 │                                       │
│       ▼                 │                                       │ 
│       A ────→ B ────→ C │                                       │
│       │       │         │                                       │
│       │       ▼         │                                       │
│       └─────→ D ────────┘                                       │
│                                                                 │
│  Page C: Only incoming from B                                   │
│  Page A: Incoming from C (sole outlink), D                      │
│  A likely has higher PageRank than C                            │
│                                                                 │
│  Formula:                                                       │
│  PR(A) = (1-d)/N + d × Σ PR(v)/out(v)                           │
│              for all v linking to A                             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

JAVA(99 lines)
Code
Loading syntax highlighter...
Show all 99 lines

Matrix Formulation

PageRank can be computed using matrix operations:

JAVA(45 lines)
Code
Loading syntax highlighter...
Show all 45 lines

Personalized PageRank

For recommendations, bias the random jump toward specific nodes:

JAVA(35 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Community Detection

Modularity

Modularity measures the quality of a community partition:

┌─────────────────────────────────────────────────────────────────┐
│                    MODULARITY CONCEPT                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Q = (1/2m) × Σ [A_ij - (k_i × k_j)/(2m)] × δ(c_i, c_j)         │
│                                                                 │
│  Where:                                                         │
│  - A_ij: adjacency matrix (1 if edge exists)                    │
│  - k_i: degree of node i                                        │
│  - m: total number of edges                                     │
│  - c_i: community of node i                                     │
│  - δ: 1 if same community, 0 otherwise                          │
│                                                                 │
│  Intuition: Q > 0 means more edges within communities           │
│            than expected by random chance                       │
│                                                                 │
│  Good partition: Q ≈ 0.3 to 0.7                                 │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Louvain Algorithm

Fast and effective community detection:

JAVA(127 lines)
Code
Loading syntax highlighter...
Show all 127 lines

Label Propagation

Simpler algorithm, often faster:

JAVA(86 lines)
Code
Loading syntax highlighter...
Show all 86 lines

🔬 Deep Dive: Graph-Based Recommendations

Collaborative Filtering with Graphs

JAVA(95 lines)
Code
Loading syntax highlighter...
Show all 95 lines

Random Walk Recommendations

JAVA(56 lines)
Code
Loading syntax highlighter...
Show all 56 lines

🔬 Deep Dive: Graph Databases (Neo4j Patterns)

Basic Cypher Queries

CYPHER(30 lines)
Code
Loading syntax highlighter...

Java Integration with Neo4j

JAVA(51 lines)
Code
Loading syntax highlighter...
Show all 51 lines

⚠️ Common Mistakes

Mistake 1: PageRank Dangling Nodes

JAVA(16 lines)
Code
Loading syntax highlighter...

Mistake 2: Community Detection Convergence

JAVA(15 lines)
Code
Loading syntax highlighter...

Mistake 3: Jaccard Similarity Division by Zero

JAVA(6 lines)
Code
Loading syntax highlighter...

🐛 Debug This: PageRank Convergence Issue

This PageRank implementation doesn't converge properly. Can you find the bug?

JAVA(39 lines)
Code
Loading syntax highlighter...

JAVA(5 lines)
Code
Loading syntax highlighter...

💻 Exercises

Exercise 1: Influence Maximization ⭐⭐

Find k nodes that, if they adopt a product, maximize spread through the network (greedy approximation).

JAVA(6 lines)
Code
Loading syntax highlighter...

Exercise 2: Link Prediction ⭐⭐

Predict which edges are likely to form in a social network.

JAVA(9 lines)
Code
Loading syntax highlighter...

Exercise 3: Community Evolution ⭐⭐⭐

Track how communities change over time given snapshots of the network.

JAVA(7 lines)
Code
Loading syntax highlighter...

Exercise 4: Personalized Recommendations ⭐⭐⭐

Implement Personalized PageRank for item recommendations.

JAVA(7 lines)
Code
Loading syntax highlighter...

Exercise 5: Network Robustness ⭐⭐⭐⭐

Analyze how the network's connectivity degrades as nodes fail.

JAVA(7 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Q1: "How would you find the most influential person in a social network?"

JAVA(4 lines)
Code
Loading syntax highlighter...

JAVA(3 lines)
Code
Loading syntax highlighter...

JAVA(3 lines)
Code
Loading syntax highlighter...

Q2: "Design a 'People You May Know' feature."

JAVA(30 lines)
Code
Loading syntax highlighter...

• Privacy: Don't reveal why someone is recommended
• Diversity: Don't recommend only from one circle
• Freshness: Boost recently active users

Q3: "Explain how PageRank handles the 'spider trap' problem."

Spider trap:    Normal web:
A → B → C       A → B → C
↑     ↓         ↓   ↓   ↓
└─────┘         external links

PR(A) = (1-d)/N + d × Σ PR(v)/out(v)
         ↑                    ↑
    Random jump          Link following
    (15% chance)         (85% chance)

With probability 15%, the surfer teleports to a random page, escaping the trap. This ensures:

1. All pages have minimum rank (1-d)/N
2. Rank flows out of traps through random jumps
3. Algorithm converges to unique solution

Q4: "How do you detect fake accounts in a social network?"

JAVA(40 lines)
Code
Loading syntax highlighter...
Show all 40 lines

Q5: "How would you implement real-time recommendations at scale?"

Architecture:
┌─────────────────────────────────────────────────────────────────┐
│                                                                 │
│  1. Offline Pipeline (daily/hourly)                             │
│     - Compute PageRank, communities                             │
│     - Build similarity indices                                  │
│     - Store in Redis/Cassandra                                  │
│                                                                 │
│  2. Near-real-time (minutes)                                    │
│     - Stream processing (Kafka + Flink)                         │
│     - Update user activity vectors                              │
│     - Incremental graph updates                                 │
│                                                                 │
│  3. Real-time (milliseconds)                                    │
│     - Pre-computed candidates from Redis                        │
│     - Light re-ranking with fresh signals                       │
│     - A/B test different algorithms                             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

JAVA(23 lines)
Code
Loading syntax highlighter...

📋 Quick Reference

Algorithm Complexity

Key Formulas

Degree Centrality:       C_D(v) = degree(v) / (n-1)
Closeness Centrality:    C_C(v) = (n-1) / Σ d(v,u)
Betweenness Centrality:  C_B(v) = Σ σ_st(v) / σ_st
PageRank:                PR(v) = (1-d)/n + d × Σ PR(u)/out(u)
Modularity:              Q = (1/2m) × Σ [A_ij - k_i×k_j/2m] × δ(c_i,c_j)
Jaccard Similarity:      J(A,B) = |A ∩ B| / |A ∪ B|

Decision Guide

Need to find important nodes?
├── Most connected → Degree centrality
├── Information brokers → Betweenness centrality
├── Endorsed by important → PageRank
└── Quick access to all → Closeness centrality

Need to find groups?
├── High quality → Louvain (modularity optimization)
├── Fast, large graphs → Label Propagation
└── Overlapping communities → BigCLAM, DEMON

Need recommendations?
├── User-based → Find similar users
├── Item-based → Find similar items
└── Graph-based → Random walks, PPR

🔗 What's Next?

• Optimal substructure and overlapping subproblems
• Memoization vs tabulation
• State definition techniques
• Classic problems: Fibonacci, climbing stairs

📅 Review Schedule