Graphs and Social Network Applications

Social networks are, at their mathematical core, graphs. Every time a user follows another account, sends a message, likes a post, or joins a group, they are creating a relationship that can be encoded as an edge between two nodes in a graph. Understanding how graph data structures work — and how algorithms operate on them — is fundamental to understanding how modern platforms like Facebook, Twitter/X, LinkedIn, and TikTok actually function under the hood. This topic builds a complete picture of graph fundamentals, storage strategies, traversal algorithms, centrality metrics, propagation models, and real-world engineering applications, all grounded in the social network domain.

Graph Fundamentals for Social Networks

A graph is formally defined as a pair G = (V, E), where V is a set of vertices (also called nodes) and E is a set of edges connecting pairs of vertices. In the social network context, every user or entity in the system is a node, and every relationship or interaction between them is an edge. This abstraction is powerful because it lets us apply decades of mathematical and algorithmic work to real engineering problems.

Nodes and edges as users and relationships. Consider a small network of five users: Alice, Bob, Carol, Dan, and Eve. Each is a node. If Alice and Bob are friends, there is an edge between them. If Carol follows Dan without Dan following back, that is also an edge — but a directional one. The same model scales from five users to five billion: the underlying graph abstraction does not change, only the algorithms and storage systems required to handle it efficiently.

Directed versus undirected edges. An undirected graph has edges with no orientation — if an edge exists between node A and node B, it implies a symmetric relationship. Friendship on Facebook is typically undirected: if you are my friend, I am your friend. A directed graph (or digraph) has edges with a specific direction, written as an ordered pair (u, v), meaning there is a connection from u to v but not necessarily the reverse. Twitter's "follow" model is directed: you can follow a celebrity without them following you back. Messaging is also naturally directed — a message goes from one user to another. Choosing the right edge direction matters enormously when designing algorithms, because traversal rules and neighbor definitions differ.

Weighted edges. Not all relationships are equal. Two users who exchange fifty messages a day have a fundamentally different relationship than two users who interacted once two years ago. A weighted graph assigns a numeric value to each edge, capturing the strength, frequency, or cost of the relationship. In a social context, edge weights might represent the number of mutual interactions in the past 30 days, the percentage of each other's posts that have been liked, or any other engagement signal. Weighted edges unlock richer algorithms: instead of simply asking "is there a path from A to B?", we can ask "what is the strongest-connection path from A to B?" — which is directly relevant to recommending people a user is likely to know and engage with.

Degree distribution and graph density. The degree of a node is the number of edges connected to it (in a directed graph, we distinguish in-degree — edges incoming — from out-degree — edges outgoing). The degree distribution of a graph describes how degrees are spread across all nodes. Real social networks almost universally exhibit a power-law degree distribution: most users have a modest number of connections, while a small number of nodes — celebrities, news outlets, viral meme accounts — have enormous numbers of connections. These high-degree nodes are called hubs. Graph density is the ratio of the number of actual edges to the maximum possible edges. A fully connected graph with V nodes has V*(V−1)/2 edges (undirected), giving density 1. Social networks are extremely sparse — even a user with 5,000 friends represents a tiny fraction of the billions of possible pairings — so density is close to zero, which has significant implications for which algorithms and data structures are efficient.

Adjacency Representations and Storage Trade-offs

Before any algorithm can run, the graph must be stored in memory (or on disk). The two classical representations — the adjacency matrix and the adjacency list — make very different trade-offs between speed and space, and the right choice is critical at platform scale.

Adjacency matrix. An adjacency matrix is a two-dimensional array M of size V × V. Entry M[i][j] is 1 (or the edge weight) if there is an edge from node i to node j, and 0 otherwise. For an undirected graph, the matrix is symmetric: M[i][j] = M[j][i].

Example: 4 nodes, edges A-B, A-C, B-D

     A  B  C  D
  A [0, 1, 1, 0]
  B [1, 0, 0, 1]
  C [1, 0, 0, 0]
  D [0, 1, 0, 0]

The key advantage is O(1) edge lookup: to check whether an edge exists between users i and j, a single array access suffices. The fatal disadvantage at social network scale is O(V²) space. With one billion users, V = 10⁹, and V² = 10¹⁸ entries. Even storing a single bit per entry would require 10¹⁸ bits — roughly 125 petabytes — which is completely impractical. Adjacency matrices are appropriate only for dense graphs with a small number of nodes.

Adjacency list. An adjacency list stores, for each node, only the list of nodes it is actually connected to. In Python it might look like a dictionary of lists:

graph = {
    'Alice': ['Bob', 'Carol'],
    'Bob':   ['Alice', 'Dan'],
    'Carol': ['Alice'],
    'Dan':   ['Bob']
}

Space usage is O(V + E). For a sparse social network where the average user has a few hundred friends out of a possible billion, E is much smaller than V², making the adjacency list dramatically more space-efficient. The cost is that checking whether a specific edge exists requires scanning the neighbor list, which is O(degree) rather than O(1). However, for most social network algorithms — which involve iterating over all neighbors of a node rather than testing arbitrary pairs — adjacency lists are ideal.

Hash-map-based adjacency lists. For dynamic platforms where users are added, deleted, and edges change constantly, a plain list is not enough. A hash-map (dictionary) of hash-sets combines the space efficiency of adjacency lists with fast membership testing. Each node maps to a hash set of its neighbors:

graph = {
    'Alice': {'Bob', 'Carol'},
    'Bob':   {'Alice', 'Dan'},
    'Carol': {'Alice'},
    'Dan':   {'Bob'}
}

# O(1) average-case edge check:
'Carol' in graph['Alice']  # True

Adding a new user is O(1) (insert a new key). Adding or removing a connection is O(1) average. This is the representation used in practice for real-time social platform backends, where millions of friendship updates may occur per second.

The following table summarizes the key trade-offs:

Breadth-First Search and Connection Discovery

Breadth-First Search (BFS) is one of the most important graph traversal algorithms and is directly responsible for features you use every day on social platforms. Starting from a source node, BFS explores all immediate neighbors first (distance 1), then all nodes at distance 2, then distance 3, and so on, using a queue (FIFO) as its core data structure to maintain the frontier of exploration.

from collections import deque

def bfs(graph, source):
    visited = {source}
    queue = deque([source])
    order = []

    while queue:
        node = queue.popleft()        # Dequeue the front node
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # Enqueue unvisited neighbors

    return order

Shortest path in an unweighted graph. Because BFS expands layer by layer, the first time it reaches a node is guaranteed to be via the shortest path from the source in an unweighted graph. This is how LinkedIn computes "2nd-degree connections" and "3rd-degree connections" — it is literally running BFS from your node and counting the layers. The classic result from sociology, the "six degrees of separation," posits that any two people on Earth are connected by at most six hops — BFS is the algorithm that verifies and quantifies this claim.

def bfs_shortest_path(graph, source, target):
    visited = {source}
    queue = deque([(source, 0)])   # (node, distance)

    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return float('inf')  # No path found

Mutual friend detection. A practical extension of BFS is identifying mutual connections between two users — a major factor in friend recommendation. One approach: run BFS from both source nodes up to depth 1 (just their immediate neighbors), then intersect the two neighbor sets. The intersection is exactly the set of mutual friends:

def mutual_friends(graph, user_a, user_b):
    neighbors_a = set(graph[user_a])
    neighbors_b = set(graph[user_b])
    return neighbors_a & neighbors_b   # Set intersection: O(min(|A|, |B|))

Time complexity. BFS visits every vertex at most once and examines every edge at most once (twice for undirected graphs, but still O(E) total). Its complexity is O(V + E). For practical bounded neighborhood searches — say, all users within 3 hops of a given user — the effective V and E are limited to that local subgraph, making BFS highly efficient even on networks with billions of total nodes.

Depth-First Search and Community Detection

Depth-First Search (DFS) takes a fundamentally different approach: starting from a source, it follows one path as deeply as possible before backtracking and trying another branch. It uses a stack — either explicitly or implicitly through recursion — as its core data structure.

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

Connected components and community detection. A connected component of an undirected graph is a maximal set of nodes such that there exists a path between every pair of nodes in the set. DFS can identify all connected components by repeatedly starting a new DFS from any unvisited node until all nodes are accounted for. In a social network, connected components represent isolated clusters of users — perhaps a regional network with no cross-cluster connections, or separate communities formed around different topics or demographics.

def find_components(graph):
    visited = set()
    components = []

    for node in graph:
        if node not in visited:
            component = dfs_recursive(graph, node, visited)
            components.append(component)

    return components

More sophisticated community detection — such as the Louvain algorithm or Girvan-Newman algorithm — builds on this foundation to find communities even within a single connected component by optimizing metrics like modularity, which measures how dense connections are within communities compared to between them.

Cycle detection. DFS is the standard approach for detecting cycles in a graph. In an undirected graph, a cycle exists if DFS visits a neighbor that is already in the current visited set (and is not the immediate parent). In a directed graph, a cycle exists if DFS reaches a node that is currently on the recursion stack. This is relevant in social networks for detecting circular referral chains (A refers B, B refers C, C refers A to game a referral reward system), or for finding feedback loops in content recommendation graphs.

Topological sorting. In a Directed Acyclic Graph (DAG) — a directed graph with no cycles — DFS can produce a topological ordering: an ordering of nodes such that for every directed edge (u, v), node u comes before node v in the ordering. Kahn's algorithm or DFS-based post-order reversal achieves this. In social platforms, topological sort applies to content prerequisite chains (course A must be completed before course B), task dependencies in ad campaign workflows, or ordering events in a user's timeline based on causal dependencies.

Influence and Centrality Metrics

Not all users in a social network are equally important or influential. Centrality metrics are graph-theoretic measures that quantify a node's importance based on its structural position in the network. Different metrics capture different notions of importance.

Degree centrality is the simplest: a node's centrality score is simply its degree (number of connections). In a directed graph, in-degree centrality (number of followers) is typically the more meaningful measure of popularity. A user with 10 million followers has high in-degree centrality. While easy to compute in O(V + E), degree centrality only captures local importance — it says nothing about where in the network those connections lead.

Betweenness centrality measures how often a node lies on the shortest path between other pairs of nodes. Formally:

BC(v) = Σ_{s≠v≠t} σ(s,t|v) / σ(s,t)

where σ(s,t) is the total number of shortest paths from s to t, and σ(s,t|v) is the number of those paths that pass through v. A node with high betweenness centrality is a bridge or gatekeeper — it controls information flow between different parts of the network. If you remove a high-betweenness node, the network may fragment or information flow may be severely disrupted. This metric identifies key influencers who connect otherwise separate communities, making them disproportionately powerful for spreading information. Computing betweenness centrality exactly requires O(VE) time using Brandes' algorithm, which is expensive for large graphs — so approximations are used in practice.

Closeness centrality measures how close a node is to all other nodes in the graph, defined as the reciprocal of the average shortest path distance from that node to all others:

CC(v) = (V − 1) / Σ_{u≠v} d(v, u)

A user with high closeness centrality can reach all other users in fewer hops on average — meaning they can spread information quickly to the entire network. In epidemic modeling (and viral marketing), nodes with high closeness centrality are ideal seeds for maximizing propagation speed.

PageRank was originally developed by Larry Page and Sergey Brin for Google's search engine and has since been applied extensively to social networks. It computes the importance of a node based on the importance of the nodes that link to it — a recursive definition. A connection from a highly influential node counts more than a connection from a low-influence node. The iterative formula is:

PR(v) = (1 − d) / V + d × Σ_{u → v} PR(u) / out_degree(u)

where d is a damping factor (typically 0.85) representing the probability that a random walker continues to follow links rather than jumping to a random node. PageRank can be computed iteratively until convergence. Twitter's "Who to Follow" recommendations incorporate PageRank-like scores to surface users with high-quality, influential follower networks — not just high follower counts.

Information Flow and Viral Propagation

One of the most consequential applications of graph algorithms to social networks is modeling how information — whether a news story, a meme, a public health message, or misinformation — spreads through the network. This is the domain of diffusion and propagation models.

Traversal-based propagation. The simplest model treats information spread as a graph traversal starting from a seed node. At each step, a node that has received the information can transmit it to each of its neighbors with some probability. BFS-based propagation assumes all edges have equal transmission probability and all transmissions happen simultaneously in rounds — the classic Independent Cascade model. At round 0, the seed has the information. At round 1, it transmits to each neighbor independently. Each newly infected node then attempts to transmit in round 2, and so on.

import random
from collections import deque

def simulate_cascade(graph, seed, transmission_prob=0.3):
    infected = {seed}
    queue = deque([seed])
    rounds = {seed: 0}

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in infected:
                if random.random() < transmission_prob:
                    infected.add(neighbor)
                    queue.append(neighbor)
                    rounds[neighbor] = rounds[node] + 1

    return infected, rounds

Weighted-edge propagation. When edge weights represent interaction frequency or trust strength, transmission probability can be set proportional to the edge weight. This produces a more realistic model where information is much more likely to spread along strong ties (close friends, frequent collaborators) than weak ties (distant acquaintances). Interestingly, the sociologist Mark Granovetter demonstrated the "strength of weak ties" paradox: while strong ties are more reliable transmission channels, weak ties bridge otherwise-disconnected communities and are therefore critical for broad propagation.

Seed selection for maximizing influence. If a platform wants to maximize the spread of a public health alert or a marketing campaign, which users should receive the initial message? This is the Influence Maximization problem, formally proven to be NP-hard in general, but a greedy algorithm achieves a (1 − 1/e) ≈ 63% approximation guarantee: repeatedly add the node that provides the greatest marginal increase in expected spread. High-centrality nodes — particularly those with high betweenness or high PageRank — are empirically excellent seeds because they sit at network crossroads and have access to diverse subpopulations.

Detecting anomalous spread (misinformation throttling). Normal organic information diffusion follows predictable statistical patterns. Coordinated inauthentic behavior — bot networks spreading misinformation — often creates anomalous diffusion signatures: too-fast spread, perfectly synchronized posting, suspiciously star-shaped diffusion trees (all paths trace back to a single root). Graph algorithms can detect these patterns by analyzing the BFS tree structure of a propagation event, flagging cases where the degree of the spread tree is abnormally shallow and wide, or where the same small cluster of accounts appears repeatedly as early transmitters. Platforms like Meta and Twitter employ such graph-based anomaly detection at scale.

Real-World Platform Applications of Graph Structures

The graph algorithms described above are not academic exercises — they are running in production at some of the world's largest engineering organizations, operating on graphs with billions of nodes and trillions of edges.

Friend and follower recommendation systems. LinkedIn's "People You May Know" and Facebook's "Friend Suggestions" are powered by graph algorithms. The core signal is the number of mutual connections between two users (computed via BFS neighbor-set intersection). Additional graph topology features — Jaccard similarity of neighbor sets, Adamic-Adar index (which weights common neighbors by the inverse log of their degree, preferring common friends who are not themselves hubs), and network embedding vectors — are fed into machine learning models that rank candidates. The graph traversal component typically runs on a distributed system, generating candidate pairs, while the ML layer re-ranks them using user activity signals.

Feed ranking. A user's content feed is not simply chronological — it is ranked by estimated engagement probability. Graph-derived features are central to this ranking. Edge weights between the viewer and the content creator (based on past interactions) serve as a strong prior for engagement likelihood. A post from a user with whom you have a high edge weight (you comment frequently, you react, you share their content) will rank highly. Centrality scores of the content creator influence organic reach — a post from a high-PageRank account gets shown more widely because the platform infers others will find it relevant.

Graph databases. Relational databases (SQL) store data in tables and perform joins to traverse relationships. For deeply nested relationship queries — "find all users who follow someone who works at a company that partnered with another company" — relational joins become extremely expensive. Graph databases like Neo4j, Amazon Neptune, and JanusGraph store nodes and edges natively, with traversal as a first-class operation. Neo4j's Cypher query language makes graph traversals intuitive:

// Find friends of friends of Alice who are not already Alice's friends
MATCH (alice:User {name: 'Alice'})-[:FRIEND]->(friend)-[:FRIEND]->(foaf)
WHERE NOT (alice)-[:FRIEND]->(foaf) AND foaf <> alice
RETURN foaf.name, count(friend) AS mutual_friends
ORDER BY mutual_friends DESC

This query, trivially expressed in Cypher, would require multiple expensive self-joins and subqueries in SQL, and would be orders of magnitude slower on billion-row tables.

Distributed graph processing. No single machine can hold the full graph of Facebook (3+ billion users, hundreds of billions of edges) in memory. Distributed graph processing systems partition the graph across many servers. Apache Giraph (used by Facebook), Google Pregel, and GraphX (part of Apache Spark) implement the Bulk Synchronous Parallel (BSP) model: in each "superstep," every vertex processes incoming messages and sends messages to its neighbors, then all vertices synchronize before the next superstep. This maps naturally to graph algorithms like PageRank (which iteratively passes scores along edges) and BFS (which passes distance labels along edges). Distributed graph systems allow platforms to run analytics — computing PageRank for all users, detecting communities, identifying influential spreaders — across the entire network in minutes rather than the years it would take on a single machine.

The following table summarizes how each graph concept maps to a concrete platform feature:

Graphs are not just a theoretical construct — they are the central data structure of the social web. Every recommendation you receive, every piece of content that surfaces in your feed, and every connection the platform suggests is the result of graph algorithms operating on an enormous, dynamic, continuously evolving graph. Mastering graph fundamentals, storage representations, traversal strategies, centrality metrics, and propagation models provides deep insight into how the largest software systems in human history actually work.