# Social Network Analysis

Studying social structure through the graph of relationships — centrality, communities, brokerage and diffusion across ties.

**Rests on:** Graph Traversal BFS and DFS

**Leads to:** Fake News Detection

*Mathematical Foundations · Graph Theory*


## Why learn this

You use these ideas every time you decide who to trust, how an app shows you content, or why certain news stories go viral. Recommendation systems calculate which items are most 'central' to show you first. Security teams look for the specific people who connect criminal groups together to stop fraud before it spreads. When you see a post shared by many friends at once, that is a pattern of information spreading through your personal network. You will use these tools to measure importance in any connected system, find hidden groups of collaborators, and predict how fast an idea or problem will travel from one person to another.


## The intuition

Think of a social network as a map of people and the connections between them. Each person is a point on the map, and each relationship is a line connecting two points. The key insight is that your position in this map can be more important than your individual traits. Some people are important because they know many others directly; some are important because they are the only link between two otherwise separate groups of friends; some are important because they sit on the shortest path to everyone else. Social network analysis gives you tools to measure these different kinds of importance quantitatively. It also helps you find clusters of people who are tightly knit together, and to model how ideas or behaviors spread through the group. The central point is that the structure of connections matters as much as the individuals themselves.

Consider a specific example: Imagine a small office with 5 employees. Employee A knows B and C. Employee B knows A, C, and D. Employee C knows A and B. Employee D knows B and E. Employee E knows only D. If we ask who is the most connected person, it is B, who has 3 direct links (degree). If we ask who connects the 'left side' of the office to the 'right side', it is also B, because all paths from {A,C} to {E} must pass through B or D. If we ask about information spread, a rumor starting at E reaches everyone faster if it goes through D then B than if it tries to go around. By counting links and shortest paths, we can predict who will hear the rumor first and who has the most power in the group.


## An analogy

Imagine a city's road network. The city has neighborhoods, and roads connect them. Some intersections are important because they have many roads leading to them; some are important because they are the only bridge between two districts; some are important because they are on the shortest route between two ends of the city. Now imagine traffic flowing through the roads. The flow depends on the intersections and the capacities of the roads. In a social network, people are the intersections and relationships are the roads. Importance measures are like asking: which intersection is most critical? There are different answers because 'critical' can mean 'has the most roads', 'is the only bridge', or 'lies on the shortest paths'. Groups of neighbors are like districts: clusters of intersections with many internal roads and few exits. A key connector is a single intersection that bridges two districts—controlling it controls the flow between them. The spread of a trend is like a new driving habit spreading from one intersection to its neighbors. The analogy breaks down when you consider that in a social network, the roads themselves can change—people can make or break relationships—and the flow is not just physical but includes information and influence. Also, in a city, intersections are fixed locations; in a social network, the same person can act as a connector in multiple different groups at once.


## Definition

Social network analysis is the study of relationships by mapping them as points connected by lines, using specific counts of direct links, shortest paths, and bridge positions to quantify influence, find tight-knit groups, and track how things spread.


## How it connects

This concept sits beside Graph Theory, which is the mathematics of studying networks of points and lines to understand their structure. It also relates to Centrality Measures, which are specific formulas used to rank individuals or items by how important or influential they are within that network.


## The mathematics

Social network analysis uses graph theory to turn relationships into numbers we can calculate. A graph is just a collection of points (called vertices or nodes) and lines connecting them (called edges). In our context, the points are people, and the lines are their connections.

We will calculate three specific numbers for each person in the network. These numbers answer the question: 'How central is this person?'

1. Degree Centrality: This counts how many direct connections a person has. It is simply a count.

2. Closeness Centrality: This measures how close a person is to everyone else in the group. We do this by finding the shortest path from the person to every other person, adding those distances together, and then taking the reciprocal (one divided by that sum). A smaller total distance means a higher centrality score.

3. Betweenness Centrality: This measures how often a person acts as a bridge between two other people. We look at every possible pair of people in the network. For each pair, we find their shortest path. If our person lies on that shortest path, we count it. The score is the number of times they were on a shortest path divided by the total number of pairs.

Let us define the symbols we will use:
- Let G be the graph representing the network.
- Let V be the set of all vertices (people) in the network.
- Let E be the set of all edges (connections) in the network.
- Let v be a specific person (vertex) we are analyzing.
- Let u be another specific person (vertex) in the network, where u is not v.
- Let d(v, u) be the shortest distance between v and u. Distance is measured in steps: if two people are directly connected, the distance is 1. If they are connected through one other person, the distance is 2, and so on.

The formulas for the three centralities are:

Degree Centrality for v:
Count the number of edges connected to v. Let this count be k_v.

Closeness Centrality for v:
First, calculate the sum of distances from v to every other person in the network. We write this as the sum of d(v, u) for all u in V where u is not equal to v.
Let S_v = d(v, u_1) + d(v, u_2) + ... + d(v, u_last).
Closeness Centrality C_clo(v) = 1 / S_v.

Betweenness Centrality for v:
First, identify all unique pairs of people in the network who are not v. Let this set of pairs be Pairs.
For each pair (x, y) in Pairs, find the shortest path between x and y.
Count how many of these shortest paths include v as an intermediate node (meaning v is neither x nor y, but lies on the line between them). Let this count be N_v.
Let Total_Pairs be the total number of such pairs in the network.
Betweenness Centrality C_bet(v) = N_v / Total_Pairs.


## A worked example

We will apply these calculations to a small network of 5 people: A, B, C, D, and E.

The connections (edges) are:
- A is connected to B.
- A is connected to C.
- B is connected to C.
- C is connected to D.
- D is connected to E.

Visualizing the distances:
- A and B are neighbors (distance 1).
- A and C are neighbors (distance 1).
- B and C are neighbors (distance 1).
- C and D are neighbors (distance 1).
- D and E are neighbors (distance 1).

Note: There is no direct line between A and D, or A and E, or B and D, etc. To go from A to D, you must go through C. So the distance from A to D is 2 steps (A->C->D). Similarly, the distance from A to E is 3 steps (A->C->D->E).

Step 1: Calculate Degree Centrality for each person.
Degree centrality is just the number of direct lines connected to a person.
- Person A has lines to B and C. Count = 2.
- Person B has lines to A and C. Count = 2.
- Person C has lines to A, B, and D. Count = 3.
- Person D has lines to C and E. Count = 2.
- Person E has a line to D. Count = 1.

Result: By degree centrality, C is the most connected person with 3 connections.

Step 2: Calculate Closeness Centrality for Person A.
We need the shortest distance from A to every other person (B, C, D, E).
- Distance from A to B: They are directly connected. d(A, B) = 1.
- Distance from A to C: They are directly connected. d(A, C) = 1.
- Distance from A to D: The shortest path is A -> C -> D. This takes 2 steps. d(A, D) = 2.
- Distance from A to E: The shortest path is A -> C -> D -> E. This takes 3 steps. d(A, E) = 3.

Now, sum these distances:
Sum_A = 1 + 1 + 2 + 3 = 7.

Closeness Centrality for A is the reciprocal of this sum:
C_clo(A) = 1 / 7 ≈ 0.143.

Step 3: Calculate Closeness Centrality for all other people.
We repeat the process for B, C, D, and E.

For Person B:
- Distance from B to A: Direct connection. d(B, A) = 1.
- Distance from B to C: Direct connection. d(B, C) = 1.
- Distance from B to D: Shortest path is B -> C -> D. 2 steps. d(B, D) = 2.
- Distance from B to E: Shortest path is B -> C -> D -> E. 3 steps. d(B, E) = 3.
Sum_B = 1 + 1 + 2 + 3 = 7.
C_clo(B) = 1 / 7 ≈ 0.143.

For Person C:
- Distance from C to A: Direct. d(C, A) = 1.
- Distance from C to B: Direct. d(C, B) = 1.
- Distance from C to D: Direct. d(C, D) = 1.
- Distance from C to E: Shortest path is C -> D -> E. 2 steps. d(C, E) = 2.
Sum_C = 1 + 1 + 1 + 2 = 5.
C_clo(C) = 1 / 5 = 0.2.

For Person D:
- Distance from D to A: Shortest path D -> C -> A. 2 steps. d(D, A) = 2.
- Distance from D to B: Shortest path D -> C -> B. 2 steps. d(D, B) = 2.
- Distance from D to C: Direct. d(D, C) = 1.
- Distance from D to E: Direct. d(D, E) = 1.
Sum_D = 2 + 2 + 1 + 1 = 6.
C_clo(D) = 1 / 6 ≈ 0.167.

For Person E:
- Distance from E to A: Shortest path E -> D -> C -> A. 3 steps. d(E, A) = 3.
- Distance from E to B: Shortest path E -> D -> C -> B. 3 steps. d(E, B) = 3.
- Distance from E to C: Shortest path E -> D -> C. 2 steps. d(E, C) = 2.
- Distance from E to D: Direct. d(E, D) = 1.
Sum_E = 3 + 3 + 2 + 1 = 9.
C_clo(E) = 1 / 9 ≈ 0.111.

Result for Closeness: C has the highest score (0.2), meaning C is closest to everyone on average. E has the lowest score (0.111).

Step 4: Calculate Betweenness Centrality for Person C.
We look at all unique pairs of people in the network who are NOT C. The people are A, B, D, E. The possible pairs are:
1. (A, B)
2. (A, D)
3. (A, E)
4. (B, D)
5. (B, E)
6. (D, E)
Total number of pairs = 6.

For each pair, we check if the shortest path goes through C.
1. Pair (A, B): Shortest path is A -> B (direct). Does it go through C? No.
2. Pair (A, D): Shortest path is A -> C -> D. Does it go through C? Yes.
3. Pair (A, E): Shortest path is A -> C -> D -> E. Does it go through C? Yes.
4. Pair (B, D): Shortest path is B -> C -> D. Does it go through C? Yes.
5. Pair (B, E): Shortest path is B -> C -> D -> E. Does it go through C? Yes.
6. Pair (D, E): Shortest path is D -> E (direct). Does it go through C? No.

Count of pairs where C is on the shortest path = 4.
Betweenness Centrality for C = 4 / 6 ≈ 0.667.

Step 5: Calculate Betweenness Centrality for Person A.
Pairs not involving A are from the set {B, C, D, E}:
1. (B, C): Shortest path is B -> C (direct). Through A? No.
2. (B, D): Shortest path is B -> C -> D. Through A? No.
3. (B, E): Shortest path is B -> C -> D -> E. Through A? No.
4. (C, D): Shortest path is C -> D (direct). Through A? No.
5. (C, E): Shortest path is C -> D -> E. Through A? No.
6. (D, E): Shortest path is D -> E (direct). Through A? No.

Count of pairs where A is on the shortest path = 0.
Betweenness Centrality for A = 0 / 6 = 0.

Step 6: Calculate Betweenness Centrality for Person D.
Pairs not involving D are from the set {A, B, C, E}:
1. (A, B): Shortest path is A -> B. Through D? No.
2. (A, C): Shortest path is A -> C. Through D? No.
3. (A, E): Shortest path is A -> C -> D -> E. Through D? Yes.
4. (B, C): Shortest path is B -> C. Through D? No.
5. (B, E): Shortest path is B -> C -> D -> E. Through D? Yes.
6. (C, E): Shortest path is C -> D -> E. Through D? Yes.

Count of pairs where D is on the shortest path = 3.
Betweenness Centrality for D = 3 / 6 = 0.5.

Step 7: Calculate Betweenness Centrality for Person B.
Pairs not involving B are from the set {A, C, D, E}:
1. (A, C): Shortest path is A -> C. Through B? No.
2. (A, D): Shortest path is A -> C -> D. Through B? No.
3. (A, E): Shortest path is A -> C -> D -> E. Through B? No.
4. (C, D): Shortest path is C -> D. Through B? No.
5. (C, E): Shortest path is C -> D -> E. Through B? No.
6. (D, E): Shortest path is D -> E. Through B? No.

Count of pairs where B is on the shortest path = 0.
Betweenness Centrality for B = 0 / 6 = 0.

Step 8: Calculate Betweenness Centrality for Person E.
Pairs not involving E are from the set {A, B, C, D}:
1. (A, B): Shortest path is A -> B. Through E? No.
2. (A, C): Shortest path is A -> C. Through E? No.
3. (A, D): Shortest path is A -> C -> D. Through E? No.
4. (B, C): Shortest path is B -> C. Through E? No.
5. (B, D): Shortest path is B -> C -> D. Through E? No.
6. (C, D): Shortest path is C -> D. Through E? No.

Count of pairs where E is on the shortest path = 0.
Betweenness Centrality for E = 0 / 6 = 0.

Final Summary of Scores:
- Person A: Degree=2, Closeness≈0.143, Betweenness=0
- Person B: Degree=2, Closeness≈0.143, Betweenness=0
- Person C: Degree=3, Closeness=0.2, Betweenness≈0.667
- Person D: Degree=2, Closeness≈0.167, Betweenness=0.5
- Person E: Degree=1, Closeness≈0.111, Betweenness=0

Conclusion:
Person C is the most central by all three measures. They have the most connections, are closest to everyone on average, and act as a bridge for many other people.
Person D is the second most central, primarily because they are the only way to reach E from the rest of the group (giving them high betweenness).
Persons A, B, and E have lower centrality scores. A and B are symmetric in this small network, and E is a 'leaf' node with only one connection.


## From scratch, in Python

```python
# Build a simple graph as a dictionary of lists (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C', 'E'],
    'E': ['D']
}

# Degree centrality
def degree_centrality(graph):
    deg = {node: len(neighbors) for node, neighbors in graph.items()}
    max_deg = max(deg.values()) if deg else 1
    return {node: d / max_deg for node, d in deg.items()}

# BFS to compute shortest path distances from a source
def bfs_distances(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [start]
    while queue:
        current = queue.pop(0)
        for neighbor in graph[current]:
            if distances[neighbor] == float('inf'):
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

# Closeness centrality
def closeness_centrality(graph):
    closeness = {}
    for node in graph:
        distances = bfs_distances(graph, node)
        total = sum(d for d in distances.values() if d != float('inf'))
        # Avoid division by zero; if no reachable nodes, closeness is 0
        closeness[node] = 1 / total if total > 0 else 0
    return closeness

# Betweenness centrality (simplified: count of shortest paths through node)
# We'll enumerate all pairs and use BFS to find one shortest path each (for simplicity).
# A full implementation would count all shortest paths, but here we just detect if node is on at least one.

def compute_shortest_path(graph, start, end):
    # BFS to find a shortest path (return list of nodes)
    prev = {node: None for node in graph}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [start]
    while queue:
        current = queue.pop(0)
        for neighbor in graph[current]:
            if distances[neighbor] == float('inf'):
                distances[neighbor] = distances[current] + 1
                prev[neighbor] = current
                queue.append(neighbor)
    # Reconstruct path
    path = []
    node = end
    while node is not None:
        path.append(node)
        node = prev[node]
    path.reverse()
    return path

def betweenness_centrality(graph):
    nodes = list(graph.keys())
    betweenness = {node: 0 for node in nodes}
    total_pairs = 0
    for i, source in enumerate(nodes):
        for j, target in enumerate(nodes):
            if i < j:  # each unordered pair once
                total_pairs += 1
                path = compute_shortest_path(graph, source, target)
                for node in path[1:-1]:  # exclude endpoints
                    betweenness[node] += 1
    return {node: (betweenness[node] / total_pairs) if total_pairs > 0 else 0 for node in nodes}

print("Degree:", degree_centrality(graph))
print("Closeness:", closeness_centrality(graph))
print("Betweenness:", betweenness_centrality(graph))
```


## The same thing, with a framework

In practice, you would use a library like NetworkX:

```python
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D'), ('D', 'E')])

print(nx.degree_centrality(G))
print(nx.closeness_centrality(G))
print(nx.betweenness_centrality(G))
```

NetworkX does exactly the same operations under the hood but is optimized and handles edge weights, directed graphs, and millions of nodes. It is the standard tool for network analysis in Python.


## What the code does

First, we represent the network as a dictionary: each key is a person (node), and the value is a list of their friends (neighbors). For example, 'A': ['B', 'C'] means A is connected to B and C. This is called an adjacency list. Then we write three functions. Degree centrality is straightforward: count how many friends each person has (length of the list), and divide by the maximum to get a value between 0 and 1. For closeness, we need shortest path distances. We use a BFS (breadth-first search) from each node: we start a queue with the source, mark its distance as 0, and then visit neighbors, setting their distance to current+1. We store distances in a dictionary. Then we sum all distances and take the reciprocal. For betweenness, we need to find shortest paths between every pair of nodes. We use a BFS again, but this time we also record the previous node to reconstruct the path. We iterate over all unordered pairs (i < j), count how many pairs exist, and for each path we increment the betweenness count for all intermediate nodes. Finally, we avoid division by zero and print the results.


## Common misconceptions

**All centrality measures are the same** — Since all centrality measures rank importance, the most important node is the same no matter which measure I use.

Different measures capture different aspects of importance: degree counts direct connections, closeness values being near everyone, betweenness values being on the shortest paths between others. A node can be high on one and low on another. For example, a node that is the only link between two large groups (a bridge) has high betweenness but may have low degree. In fact: Centrality is not a single concept; it is a family of measures, each answering a different question about importance.

**A person with many connections is always the most influential** — If someone knows a lot of people, they must be the most influential in the network.

High degree does not imply that the person controls the flow of information. A person with moderate degree but who is the only bridge between two communities may be more influential in controlling what spreads. In fact: Influence depends on the pattern of connections, not just the number. Brokerage and betweenness can matter more than degree.

**Community detection is just clustering by degree** — Communities are simply groups of nodes with high degree.

Communities are defined by dense internal connections and sparse external ones, not by high degree. A node with many connections can be spread across multiple communities. In fact: Community detection finds groups that are more connected internally than they are to the outside, regardless of individual node degree.

**Network position is the only thing that matters** — Once I know the network structure, individual attributes (like age or income) become useless.

Network position and individual attributes both matter; they explain different parts of the outcome. The textbook example: two people with the same income may have different influence because of their position. In fact: Position often predicts outcomes better than attributes, but not exclusively. Both are inputs to a model or analysis.


## In short

Social network analysis is the study of relationships as a graph. The key tools are centrality measures (degree, closeness, betweenness) that quantify different kinds of importance, community detection that finds densely connected subgroups, and the concept of brokerage (connecting otherwise separate groups). Diffusion models how things spread across ties. Remember that centrality is not one thing; position in the network can be more informative than individual attributes alone.


## Where this is used

In large language models, social network analysis appears in attention networks: the attention matrix is a fully connected graph of tokens (nodes) and attention weights (edges). Centrality ideas help interpret which tokens are most influential in the representation; for example, high in-degree tokens are like hubs. In small models running on devices, network analysis on knowledge graphs compresses them by removing low-centrality nodes, enabling smaller embeddings and faster inference. In retrieval-augmented generation (RAG), the knowledge base is often a knowledge graph, and retrieval ranks nodes by centrality to select the most relevant documents or entities to augment the prompt. In agentic systems that plan and call tools, the agent builds a graph of subtasks and dependencies; centrality (e.g., which subgoal is most critical) drives planning priority, and network diffusion models how information or states propagate through the plan. In everyday applied machine learning, social network analysis is used in recommendation engines (similar users form communities, and centrality measures suggest popular items), fraud detection (fraud rings appear as communities, and broker nodes are often the paymasters), and social media analytics (finding influencers via centrality). A developer typically builds a graph from relational data (e.g., user-user interactions), computes centrality with NetworkX, and feeds those features into a supervised model. When done badly—ignoring the network structure—models miss crucial signals like the 'bridge' node that connects two criminal networks, leading to poor fraud detection. Conversely, when done well, centrality features can outperform individual attribute features alone.


---

Read this on the web: https://basavapurushottam.com/learn-ai/social-network-analysis
