Why Graphs? - Learning Module

Loading content...

0/276

Examples — Social Networks, Road Maps, Dependencies

Graphs Are Everywhere

Now that we understand why hierarchical trees can't capture all relationships, let's embark on a tour of the real world. As we explore diverse domains—from social platforms to city streets to software systems—a remarkable pattern emerges: graphs appear everywhere.

This isn't coincidence. Graphs are the mathematical structure for representing relationships, and relationships permeate every domain of human activity. The power of learning graph algorithms isn't that you'll solve one narrow problem—it's that you'll gain tools applicable to an extraordinary range of challenges.

What You Will Learn

By the end of this page, you will recognize graph structures in social networks, transportation systems, software dependencies, biological systems, and many other domains. You'll understand how the same graph algorithms apply across completely different fields, and why mastering graphs is one of the highest-leverage investments in your algorithmic education.

Social Networks

Perhaps the most intuitive example of graphs in the modern world is the social network. Whether it's Facebook, LinkedIn, Twitter, Instagram, or a dating app, the underlying structure is identical: people (vertices) connected by relationships (edges).

Facebook's Social Graph:

Consider Facebook's friend network:

Vertices: Each user is a vertex (billions of them)
Edges: Friendships connect users (edges are undirected—if you're my friend, I'm your friend)
Properties tracked: When the friendship was formed, interaction frequency, mutual friends

This graph enables fundamental features:

Friend suggestions: Find vertices close to you in the graph but not yet connected
Mutual friends: Count vertices connected to both you and another user
Degrees of separation: Find the shortest path between any two users
Community detection: Identify clusters of densely connected users

Undirected Social Graphs

•Facebook: Mutual friendships
•LinkedIn: Professional connections
•Dating apps: Mutual matches
•Collaborative networks: Co-authorship
•Gaming: Friendship lists

Directed Social Graphs

•Twitter/X: Follows (you follow someone, they may not follow you back)
•Instagram: Followers/Following
•YouTube: Subscriptions
•Twitch: Channel follows
•RSS/Blogs: Subscriptions

The Directed vs Undirected Distinction:

Notice how some social networks use undirected graphs (mutual relationships) while others use directed graphs (one-way relationships). This distinction matters algorithmically:

Undirected (Facebook): If Alice is connected to Bob, paths can traverse the edge in either direction. Connectivity is symmetric.
Directed (Twitter): If Alice follows Bob, we can only traverse from Alice to Bob. Finding who Alice follows is different from finding who follows Alice.

Twitter's directed graph enables concepts like:

Influencer identification: Vertices with high in-degree (many followers) but low out-degree (follow few)
Information flow: How does a tweet propagate through the network? It follows directed edges from followed to follower.
PageRank-style importance: Algorithms borrowed from web search rank users by their position in the directed graph

Scale Matters

Facebook's social graph has billions of vertices and hundreds of billions of edges. At this scale, even O(V) algorithms are expensive. Graph algorithms must be carefully designed for distributed processing across thousands of servers. The fundamental graph concepts remain the same; the engineering challenges multiply.

Transportation Networks

Transportation systems are among the oldest applications of graph theory. Whether you're planning a road trip, navigating a subway system, or scheduling airline routes, you're working with graphs.

Road Networks:

Consider a road map:

Vertices: Intersections, cities, or locations
Edges: Roads connecting them
Edge weights: Distance, travel time, or toll costs
Edge direction: One-way streets create directed edges; two-way streets create undirected edges

Every time you use Google Maps, Waze, or Apple Maps, you're asking graph questions:

Shortest path: What's the fastest route from A to B?
Alternative routes: What other paths exist, and how much longer are they?
Traffic-aware routing: If edge weights change (due to traffic), what's the new optimal path?
Multi-stop routing: Visit locations L1, L2, L3 in optimal order (a variant of the Traveling Salesman Problem)

Transportation Graphs at Different Scales
Scale	Vertices	Edges	Typical Edge Weight	Key Algorithms
City streets	Intersections	Street segments	Travel time/distance	Dijkstra, A*
Highway network	Exits/Junctions	Highway stretches	Travel time	Contraction Hierarchies
Subway/Metro	Stations	Track segments	Transfer time + travel time	Multi-criteria shortest path
Airline routes	Airports	Direct flights	Flight time, cost, layover	Weighted shortest path
Shipping routes	Ports	Shipping lanes	Shipping time, cost	Minimum cost flow

Subway and Transit Networks:

Public transit introduces additional complexity:

Transfer penalties: Changing lines takes extra time
Schedules: Unlike roads, transit has fixed departure times
Multi-modal: Combining bus, subway, and walking requires integrating multiple graphs

These constraints lead to specialized graph representations:

Time-expanded graphs: Create a vertex for each (station, time) pair
Multi-layer graphs: Separate layer per transit mode, with transfer edges between layers

Air Travel Networks:

Airline route networks have fascinating properties:

Hub-and-spoke structure: Major airlines route through hub cities
Layover constraints: Flight sequences must have sufficient connection time
Pricing complexity: Edge weights (ticket prices) vary dramatically and non-additively

Finding the cheapest route isn't just shortest path—it requires considering entire itineraries and complex pricing rules.

The Power of Preprocessing

For large road networks (millions of intersections), naive Dijkstra is too slow for real-time queries. Systems like Google Maps use preprocessed structures (Contraction Hierarchies, Highway Hierarchies) that answer queries in milliseconds despite the graph's size. The preprocessing is expensive but done once; queries are then nearly instant.

Software Dependencies

As a software developer, you work with graphs daily—often without realizing it. Every software project is a graph of dependencies.

Package/Module Dependencies:

When you run npm install, pip install, or cargo build, the package manager is solving graph problems:

Vertices: Packages/modules
Edges: Dependencies (directed: A depends on B means edge from A to B)
Problem 1: What packages must be installed? (Reachability from root)
Problem 2: In what order should they be installed? (Topological sort)
Problem 3: Are there conflicting version requirements? (Cycle detection, constraint satisfaction)

The Directed Acyclic Graph (DAG) Requirement:

Healthy dependency graphs should be DAGs—directed acyclic graphs. Why?

Imagine:

Package A depends on Package B
Package B depends on Package C
Package C depends on Package A

This cycle is problematic: to build A, you need B. To build B, you need C. To build C, you need A. There's no valid build order. This is called a circular dependency, and it's a bug that dependency solvers must detect.

dependency_graph_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# Example: Building a dependency graph from package.json-style dependencies
from collections import defaultdict, deque
from typing import Dict, List, Set
 
def build_dependency_graph(packages: Dict[str, List[str]]) -> Dict[str, List[str]]:
    """
    Build an adjacency list representation of a dependency graph.
    
    Args:
        packages: Dict mapping package name to list of dependencies
                  e.g., {"app": ["react", "lodash"], "react": ["react-dom"]}
    
    Returns:
        Adjacency list: package -> list of packages that depend on it
    """
    graph = defaultdict(list)
    for package, deps in packages.items():
        for dep in deps:
            # Edge from dependency to dependent (for topological sort)
            graph[dep].append(package)
    return dict(graph)
 
def topological_sort(packages: Dict[str, List[str]]) -> List[str]:
    """
    Find a valid installation order using Kahn's algorithm.
    Returns empty list if a cycle is detected.
    """
    # Calculate in-degree (number of dependencies) for each package
    in_degree = defaultdict(int)
    all_packages: Set[str] = set()
    
    for package, deps in packages.items():
        all_packages.add(package)
        for dep in deps:
            all_packages.add(dep)
            in_degree[package] += 1  # package has one more dependency
    
    # Packages with no dependencies can be installed first
    queue = deque([pkg for pkg in all_packages if in_degree[pkg] == 0])
    install_order = []
    
    while queue:
        current = queue.popleft()
        install_order.append(current)
        
        # For each package that depends on current...
        for dependent in packages.get(current, []):
            continue  # Skip - we need reverse lookup
        
        # Actually: for each package that current enables
        for pkg, deps in packages.items():
            if current in deps:
                in_degree[pkg] -= 1
                if in_degree[pkg] == 0:
                    queue.append(pkg)
    
    # If we couldn't install all packages, there's a cycle
    if len(install_order) != len(all_packages):
        return []  # Cycle detected!
    
    return install_order
 
# Example usage
dependencies = {
    "my-app": ["react", "lodash", "axios"],
    "react": ["react-dom", "scheduler"],
    "react-dom": ["scheduler"],
    "axios": [],
    "lodash": [],
    "scheduler": []
}
 
order = topological_sort(dependencies)
print(f"Installation order: {order}")
# Output: scheduler, react-dom, lodash, axios, react, my-app (one valid order)

Build System Graphs:

Beyond package dependencies, build systems like Make, Bazel, and Gradle model the entire build as a graph:

Vertices: Build targets (executables, libraries, test suites)
Edges: Dependencies between targets
Incremental builds: Only rebuild vertices whose dependencies have changed
Parallel builds: Build-independent vertices simultaneously

The graph structure enables efficient incremental and parallel builds. Without it, every change would require rebuilding everything.

Microservices and API Dependencies:

In distributed systems, services depend on other services:

Vertices: Microservices
Edges: API calls between services
Challenges: Detecting circular dependencies, modeling failure propagation, optimizing call chains

When Service A calls Service B calls Service C calls Service A, a single slow response can cascade into system-wide deadlock.

Dependency Hell

The term 'dependency hell' describes situations where version constraints in the dependency graph become unsatisfiable. Package A requires B >= 2.0, but Package C requires B < 2.0. This is a constraint satisfaction problem on the dependency graph—and it's NP-hard in general. Modern package managers use sophisticated solvers to find valid configurations when they exist.

The World Wide Web

The World Wide Web is literally named after a graph structure—a 'web' of interconnected pages.

The Web Graph:

Vertices: Web pages (URLs)
Edges: Hyperlinks (directed: page A links to page B)
Scale: Billions of pages, trillions of links

This graph is the foundation of web search. When you enter a query into Google, the search engine:

Crawls the graph (follows edges to discover vertices)
Indexes the vertices (extracts and stores page content)
Ranks the vertices (determines importance based on graph structure)
Retrieves top-ranked relevant vertices for your query

PageRank: The Algorithm That Built Google

Google's original breakthrough was realizing that a page's importance could be computed from the graph structure. The intuition:

A page is important if many pages link to it
A link from an important page counts more than a link from an unimportant page
This creates a recursive definition that can be solved iteratively

PageRank models a 'random surfer' who:

Starts at a random page
With probability 0.85, clicks a random link on the current page
With probability 0.15, jumps to a random page anywhere

The long-term probability of the surfer being at each page is the page's PageRank. Pages where the surfer spends more time are more important.

Why This Is Profound:

PageRank demonstrated that the structure of the web graph contains information beyond the content of individual pages. Two pages with identical content will have different rankings based on who links to them. This insight—extracting meaning from graph structure—underpins much of modern AI and network analysis.

Beyond PageRank

Modern search engines use hundreds of ranking signals beyond PageRank. But the core insight—that graph structure conveys importance and relevance—remains fundamental. Similar algorithms power 'people you may know' on social networks, recommendation systems, and fraud detection.

Biological Networks

Biology is rich with network structures. From molecular interactions to ecological food webs, graphs model life at every scale.

Protein-Protein Interaction Networks:

Proteins don't work in isolation—they interact with other proteins to perform biological functions:

Vertices: Proteins
Edges: Physical interactions between proteins
Applications:
- Predicting protein function from network neighbors
- Identifying drug targets (highly connected proteins are often essential)
- Understanding disease mechanisms (which interactions are disrupted?)

Gene Regulatory Networks:

Genes regulate each other's expression:

Vertices: Genes
Edges: Regulatory relationships (gene A activates or inhibits gene B)
Direction matters: Gene A activating B is different from B activating A
Cycles are meaningful: Feedback loops create oscillations (like circadian rhythms)

Biological Networks Across Scales
Network Type	Vertices	Edges	Key Questions
Metabolic network	Chemical compounds	Biochemical reactions	What pathways produce this compound?
Protein interaction	Proteins	Physical binding	What proteins work together?
Gene regulatory	Genes	Activation/Inhibition	How is gene expression controlled?
Neural network (brain)	Neurons	Synaptic connections	How does information flow?
Food web	Species	Predator-prey relationships	What happens if a species goes extinct?
Phylogenetic tree	Species/Genes	Evolutionary relationships	What's the common ancestor?

The Brain as a Graph:

The human brain contains approximately 86 billion neurons, each connected to thousands of others. This forms one of the most complex graphs known:

Vertices: Neurons
Edges: Synaptic connections
Edge weights: Synaptic strength (how strongly one neuron influences another)
Dynamics: Weights change over time (learning!)

Neuroscience increasingly uses graph-theoretic tools:

Small-world property: The brain is highly clustered locally but has short paths globally
Hub regions: Some brain areas are highly connected and crucial for integration
Modularity: The brain has distinct functional modules that are densely connected internally

Understanding the brain's graph structure may be key to understanding consciousness, treating neurological disorders, and building artificial general intelligence.

The Connectome Project

The 'connectome' is the complete map of neural connections in a brain. The C. elegans worm (302 neurons) has a fully mapped connectome. Ongoing projects aim to map larger brains. This is essentially extracting the graph from biological tissue—a profound technological challenge with immense scientific value.

Computer Networks

The internet itself is a graph—a network of networks. Understanding this structure is crucial for everything from routing packets to designing resilient infrastructure.

The Internet Graph:

At the highest level:

Vertices: Autonomous Systems (AS)—large networks like ISPs, universities, corporations
Edges: Peering/Transit relationships between ASes
Routing: Border Gateway Protocol (BGP) finds paths through this graph

At lower levels:

Vertices: Routers
Edges: Physical or logical connections
Edge weights: Latency, bandwidth, reliability

Data Center Networks:

Inside large data centers, thousands of servers are interconnected:

Topology design: How to connect servers for maximum bandwidth and fault tolerance?
Traffic engineering: How to route flows to avoid congestion?
Failure resilience: If a switch fails, do alternative paths exist?

Routing as Shortest Path:

When you send a packet across the internet, routers make forwarding decisions. Each router knows the 'next hop' for each destination. How are these routing tables built?

Link-State Routing (OSPF): Each router learns the entire graph topology and computes shortest paths using Dijkstra's algorithm
Distance-Vector Routing (RIP): Each router iteratively learns distances to destinations through neighbors (Bellman-Ford style)
Path-Vector Routing (BGP): Between autonomous systems, routers exchange entire path information to avoid loops

Every time you load a webpage, packets traverse paths computed by graph algorithms running on routers worldwide.

Network Reliability:

Network engineers worry about connectivity:

Is the network connected? — Can every node reach every other node?
What's the minimum cut? — How many edges must fail to disconnect the network?
Are there articulation points? — Single vertices whose failure disconnects the graph?

These are graph-theoretic questions with real-world consequences. A poorly designed network might have a single point of failure that brings down everything.

The Fragility of the Internet

Despite its redundancy, the internet has vulnerabilities. Cutting a few key undersea cables can isolate entire continents. BGP misconfigurations can route traffic through malicious networks. Understanding the graph structure reveals both the internet's resilience and its weak points.

Other Fascinating Graph Examples

Graphs appear in countless other domains. Here's a rapid tour:

Knowledge Graphs:

Google, Wikipedia, and enterprises build knowledge graphs:

Vertices: Entities (people, places, concepts)
Edges: Relationships ('Barack Obama' — 'president of' → 'United States')
Applications: Question answering, recommendation, semantic search

Financial Networks:

Vertices: Banks, companies, individuals
Edges: Transactions, loans, ownership stakes
Applications: Fraud detection, risk assessment, systemic risk analysis

The 2008 financial crisis revealed how interconnected bank liabilities created systemic risk. Graph analysis now helps regulators identify 'too connected to fail' institutions.

Supply Chain Networks:

Vertices: Suppliers, manufacturers, distributors, retailers
Edges: Supply relationships
Applications: Identifying bottlenecks, planning for disruptions, optimizing inventory

The Ubiquity of Graphs
Domain	Example Graph	Key Algorithms Used
Natural Language	Word co-occurrence graphs	PageRank for word importance
Recommendation	User-item bipartite graphs	Collaborative filtering, random walks
Fraud Detection	Transaction networks	Anomaly detection, community detection
Epidemiology	Contact networks	Disease spread simulation (SIR models)
Citation Networks	Paper-cites-paper graphs	Impact analysis, trend detection
Game AI	State space graphs	BFS/DFS, Minimax, MCTS
Compiler Design	Control flow graphs, SSA	Dominators, liveness analysis
Database Query Optimization	Query plan graphs	Cost-based optimization, join ordering

Criminal Networks:

Law enforcement uses graph analysis to understand organized crime:

Vertices: Individuals
Edges: Communications, transactions, associations
Applications: Identifying leaders, understanding hierarchy, disrupting networks

Power Grids:

Vertices: Power plants, substations, consumers
Edges: Transmission lines
Critical concern: Cascading failures—one line failure overloads others, which fail, which overload more...

The massive 2003 Northeast blackout affected 55 million people due to cascading failures in the power grid graph.

The lesson is clear: Whether your domain is technology, biology, society, or infrastructure, you'll encounter graphs. The algorithms you learn in this chapter aren't academic exercises—they're tools you'll use throughout your career.

Summary: Graphs in the Wild

We've surveyed an astonishing variety of domains where graphs naturally arise. Let's consolidate the key insights:

Key Takeaways

•Social networks model human relationships—both symmetric (friends) and asymmetric (followers)
•Transportation networks are the foundation of navigation—shortest paths are computed billions of times daily
•Software dependencies are graphs—every install, build, and deploy involves graph algorithms
•The web is a massive directed graph whose structure determines search rankings
•Biological systems are networked at every scale—from molecules to ecosystems
•Computer networks route packets using graph algorithms running on routers worldwide
•Graphs appear everywhere relationships exist—and relationships are fundamental to virtually every domain

What's Next:

Having seen graphs everywhere in the real world, you might wonder: are these examples replacing trees, or are trees somehow related to graphs? The next page addresses exactly this question. We'll explore when trees aren't enough and how graphs generalize the tree concept while preserving trees as an important special case.

Page Complete

You now appreciate the ubiquity of graphs across diverse domains. From social platforms to city streets to software systems, graphs underlie the systems we use daily. This broad applicability makes graph algorithms among the most valuable tools in computer science. Next, we'll examine when trees fall short and why graphs are needed.