Social Network Analysis Part5: Breadth-First Search, Depth-First Search & Dijkstra
Analyze how information or influence can travel through a network.
Introductions.
Recap.
Over the previous blogs:
- In Part 1, we established the foundations of graph theory, exploring how networks are structured using nodes and edges, the differences between directed and undirected graphs, and how link prediction can forecast future relationships.
- In Part 2, we moved beyond messy “hairball” diagrams and learned how to visualize network patterns using structured techniques like e.g., Plots, Arc Plots, and Circos Plots.
- In Part 3, we began quantifying network structures using fundamental centrality measures e.g., Degree Centrality to count direct connections and Betweenness Centrality to get the number of shortest paths in a graph that pass through a node.
- In Part4, we explored how each of these measures works, understoad the intuition behind their mathematical definitions, visualized them using simple network examples. We also compared the 3 measures and saw how they can produce different interpretations of importance within the same network.
What is path finding?
Shortest Path finding algorithms has a wide range of important applications from GPS and Satellite Navigation optimization problems, video games robotics, logistics to Computer Networks and Telecommunications and more. They enable machines to navigate efficiently through complex environments by finding the shortest or most efficient path between two points.
It’s also important in modeling the spread of things, such as the spread of disease in an outbreak, or information spread in a social network.
The goal of a pathfinding algorithm is to explore a graph to find the optimal path from a starting point to a destination point, while considering obstacles, barriers, and other constraints.
Over the years, numerous pathfinding algorithms have been developed, each with its own advantages and limitations. Some of the most well-known algorithms include Dijkstra’s algorithm, A* algorithm, the breadth-first search algorithm and the depth-first search algorithm. The various algorithms differ in their approach to exploring the graph and their use of heuristic information to guide the search.
In this blog, we provide an overview of the most common pathfinding algorithms in social network analysis. We’ll explore how these algorithms work, their strengths and weaknesses and we’ll provide other examples of their application in real-world scenarios.
By the end of this article, We’ll have a better understanding of how pathfinding algorithms work, and which algorithm might be the best fit for a particular use case.
Finding Shortest Paths in Social network Analysis.
Shortest-path calculations are also the foundation of several important SNA measures, particularly Betweenness Centrality and Closeness Centrality.
Pathfinding algorithms in this space are primarily used to measure influence, find community structures, and map how information or behaviors spread. For example:
- Counts the minimum number of social steps needed to connect any 2 people.
- Which nodes (people ) act as bridges between communities?
- How quickly can information travel between two people?
- Measures how often a specific node falls on the shortest path between all other nodes.
How do we find out whether there’s a path between two nodes?
If there’s a path, how do we find out what the shortest path is?
One way we can do so is by using one or more of finding the shorts path algorithms e.g., Breadth First Search (BFS), Depth First Search (DFS) algorithms .
Breadth-first search (BFS)
In its essence, BFS algorithm was first developed in the 1950s as a way of finding the shortest path out of a maze.
BFS is one of the fundamental graph traversal algorithms used in SNA. It provides a systematic way to explore a network starting from a particular node and visiting neighboring nodes level by level.
In social networks, this can be interpreted naturally as exploring relationships according to the number of connections separating individuals. For example, starting from a particular node:
How does this algorithm work? Suppose we have the network above, comprised of 11 nodes, and we want to find the shortest path between the yellow and red nodes.
The algorithm essentially works as such.
- If we start at the yellow node,
- We first ask for the yellow node’s neighbors.
- then ask if the destination node is present in the set of yellow node’s neighbors.
- If not, we continue on.
Going out a 2nd degree of separation, we ask for the neighbors of our neighbors. The destination node is still not present, so we continue on.
On our 3rd degree of separation out, we see that the destination node is present. At this point, we can stop and ignore the next degree of separation. Note that there was one other path possible, but it was longer. As such, with the BFS algorithm, we have achieved our goal of finding the “shortest” path between the pair of nodes.
Each level represents the number of edges separating the nodes from the starting node. Therefore:
- Level 0 → the starting user
- Level 1 → direct connections
- Level 2 → friends-of-friends
- Level 3 → connections three steps away
- and so on.
This makes BFS particularly suitable for unweighted social networks, where every relationship is treated as having the same cost.
The important property is that BFS discovers nodes in nondecreasing order of their distance from the source.
Consequently, when BFS first reaches a node, it has found a shortest path to that node.
This makes BFS a fundamental building block for shortest-path analysis in unweighted social networks.
The Queue-Based Nature of BFS
The implementation of BFS relies on a queue, which follows the First-In, First-Out (FIFO) principle.
Start
↓
Add starting node to queue
↓
Remove first node
↓
Visit its unvisited neighbors
↓
Add those neighbors to queue
↓
RepeatConceptually: BFS adds the starting node to the queue, next it removes the 1st node from the queue but keep it in the BF array. Then add its unvisited neighbors and add those neighbors to the queue. If the destination node is present in the set of node’s neighbors, end the loop. If it is not, continue till find it.
This queue structure is what forces BFS to finish exploring one distance level before moving to the next.
A typical implementation maintains two important pieces of information:
- Visited nodes — prevents repeatedly exploring the same node.
- Queue — stores the frontier of nodes waiting to be explored.
For shortest-path applications, BFS can additionally maintain the distance and predecessor/parent of each node.
BFS in Real Social Networks
The usefulness of BFS becomes clearer when we translate graph traversal into social-network questions.
Imagine a social network where: Node is a Person and Edge is the Friendship.
Starting from Alice, BFS can identify:
Alice
│
├── Direct friends
│
├── Friends of friends
│
├── Friends 3 relationships away
│
└── ...This allows us to investigate the social neighborhood surrounding Alice.
I.e., we could determine: How many people are within two degrees of Alice?, How many relationships separate Alice from Bob? or Which users can be reached from Alice?
BFS therefore provides a natural mechanism for exploring the local structure surrounding a node.
BFS and Degrees of Separation
BFS is particularly well suited to analyzing the concept of degrees of separation.
Suppose:
Alice → Bob → Carol → DavidBFS starting from Alice would assign:
Alice = 0
Bob = 1
Carol = 2
David = 3The number assigned to each node represents its shortest-path distance from Alice.
For a large social network, this allows us to construct a distance distribution such as:
Distance Number of users
0 1
1 25
2 340
3 2,100
4 5,800
...This provides a useful description of how quickly the network expands outward from a particular individual.
BFS for Reachability Analysis
BFS can also determine whether one node is reachable from another.
Consider a network containing 2 disconnected components:
Component 1 Component 2
A ─ B ─ C X ─ Y
│
DIf BFS starts at A, it will visit: A → B → D → C. But it will never reach X or Y.
Therefore, BFS can help determine whether 2 users belong to the same connected component.
This is useful in networks where disconnected groups may represent:
- isolated communities
- separate organizations
- disconnected communication groups
- fragmented online networks
BFS and Network Exploration
Another useful interpretation is to think of BFS as a network exploration mechanism. Starting from a node, it progressively expands the explored region:
│ Network │
└──────┬──────┘
│
Start
│
▼
Distance 1
│
▼
Distance 2
│
▼
Distance 3
│
▼
Distance 4This is useful when researchers are interested in a specific user’s local neighborhood rather than the entire network.
I.e., researchers might analyze the network within k=1, k=2 or k=3, hops from a particular node.
The parameter k effectively defines the radius of the neighborhood being explored.
BFS and Centrality Analysis
BFS also plays an important computational role in several SNA measures.
For an unweighted network, BFS can efficiently calculate shortest-path distances from a source node to other reachable nodes.
Those distances can subsequently be used in measures based on shortest paths, including:
- Closeness Centrality
- Betweenness Centrality
- Average Shortest Path Length
- Network Diameter
- Network Efficiency
For example:
BFS
│
▼
Shortest distances
│
┌──────┼──────┐
▼ ▼ ▼
Closeness Path Network
Centrality Length MeasuresThus, BFS is not necessarily the final SNA analysis itself. It is often a fundamental computational component used to obtain the structural information required by higher-level analyses.
BFS for Finding All Shortest Paths from One Source
An important distinction is that BFS can determine shortest-path distances, but a social network may contain multiple shortest paths between 2 nodes.
B
/ \
A ─── ─── D
\ /
CThere are two shortest paths from A to D:
A → B → D
A → C → DBoth have length 2. BFS can discover the shortest-path distance: d(A,D)=2
and, with appropriate additional bookkeeping, can also track multiple predecessors associated with shortest paths.
This becomes particularly important for algorithms that need to consider the number of shortest paths passing through nodes, such as Betweenness Centrality.
Time and Space Complexity
For a graph represented using an adjacency list, BFS has a time complexity time complexity O(∣V∣+∣E∣) and Its space complexity is O(∣V∣)
because BFS may need to maintain information about the visited nodes and the queue.
Get AI & Data Science 604’s stories in your inbox
Join Medium for free to get updates from this writer.
This makes BFS computationally attractive for large sparse social networks, where the number of edges is considerably smaller than the theoretical maximum number of edges.
Limitations of BFS in Social Networks
Despite its usefulness, BFS has several limitations.
- It assumes an unweighted graph: Standard BFS treats every edge as having equal cost.
If relationships have different weights, such as:
Friendship strength
Interaction frequency
Communication cost
Geographical distancethen algorithms such as Dijkstra’s algorithm may be more appropriate.
2. Large networks can still be expensive: Although O(V+E) is efficient, exploring millions or billions of edges can still require substantial computational resources.
3. Social relationships are not always equivalent: A friendship edge and a weak interaction edge may both count as one edge, even though their social meanings are very different.
4. Shortest structural distance isn’t necessarily actual social distance
If BFS finds A → B → C → D. This does not mean information will actually travel from A to D through B and C.
BFS describes the structure encoded in the graph, not necessarily the real-world behavior occurring on that graph.
BFS as a Building Block for SNA
The most useful way to understand BFS is not simply as a graph traversal algorithm, but as a building block for network analysis.
Social Network
│
▼
Graph G=(V,E)
│
▼
BFS
│
┌──────────┼──────────┐
│ │ │
▼ ▼ ▼
Distance Reachability Neighborhood
│
▼
Shortest-path information
│
┌────┴───────────┐
│ │
▼ ▼
Centrality Network
Measures StructureThe central idea is simple:
BFS systematically expands through an unweighted network one layer at a time, making it an efficient way to determine reachability and shortest-path distances from a source node.
In Social Network Analysis, this seemingly simple traversal process becomes the foundation for analyzing degrees of separation, local neighborhoods, shortest-path distances, connectivity, and several higher-level network measures.
Depth-First Search (DFS).
DFS is a fundamental graph traversal algorithm that explores a network by following one path as deeply as possible before backtracking and exploring alternative paths.
In SNA, DFS can be used to systematically explore the structure of a social network, investigate connectivity, identify structural relationships, and serve as a building block for more advanced graph algorithms.
If nodes represent people and edges represent relationships, DFS starts from a particular person and repeatedly follows an unvisited connection until it reaches a node where no further unvisited connections are available. It then backtracks to the previous node and continues exploring another branch.
Consider the following network:
B
/ \
A D
\ /
C
|
EStarting from A, DFS might explore the network as: A → B → D → C → E
The exact traversal order can depend on the order in which neighboring nodes are stored, but the fundamental principle remains the same: DFS follows a branch deeply before moving to another branch.
How DFS Explores a Social Network
The easiest way to understand DFS in SNA is to think of the network as a set of interconnected relationships. Suppose we start with user A:
A
│
B
│
C
│
DDFS will continue following the available path A → B → C → D, rather than first exploring every node directly connected to A.
If the network branches:
B
/ \
C D
/ \
E FDFS may explore A → B → C → E, before returning to C, then B, and subsequently exploring: B → D → F
This deep exploration followed by backtracking is the defining characteristic of DFS.
The Role of Backtracking
Backtracking is particularly important to understanding DFS.
A ─ B ─ C
│
D ─ EStarting at A, DFS could proceed A → B → C. At C, there are no more unvisited neighbors. DFS therefore goes back to B: A → B ← C
It then explores B’s other branch: A → B → D → E
The algorithm therefore combines two ideas:
Deep exploration
↓
Reach a dead end
↓
Backtrack
↓
Explore another branchThis makes DFS particularly useful for discovering the structural organization of a graph.
DFS and the Structure of Social Networks
Social networks are rarely simple linear structures. They typically contain cycles, highly connected nodes, multiple communities, bridges between groups, disconnected components, and dense clusters of relationships.
DFS can traverse these structures while keeping track of which nodes have already been visited.
For example:
A
/ \
B───C
│ │
D───EThe network contains several cycles. A naïve traversal could repeatedly revisit the same users. DFS avoids this by maintaining a visited set: Visited = {A, B, C, ...}
Whenever DFS encounters a node that has already been visited, it does not recursively explore that node again.
This is essential for safely traversing real-world networks containing cycles.
DFS and Connected Components
One important application of DFS in SNA is identifying connected components.
Consider a network:
A ─ B ─ C X ─ Y
│
DStarting DFS from A will visit: {A, B, C, D}. It will not reach X or Y because there is no path connecting the two groups. The network therefore contains two connected components:
Component 1 = {A, B, C, D}
Component 2 = {X, Y}A common strategy for finding all connected components is:
- Select an unvisited node.
- Run DFS from that node.
- Mark every reachable node as visited.
- Select another unvisited node.
- Repeat until every node has been explored.
Conceptually:
Graph
│
▼
Select unvisited node
│
▼
DFS
│
▼
Discover all reachable
nodes
│
▼
One connected component
│
▼
Repeat for remaining
nodesThis makes DFS useful for analyzing network fragmentation and connectivity.
DFS and Cycle Detection
Social networks naturally contain cycles. I.e., If there are multiple routes connecting these users. DFS can be used to detect such cycles by tracking the traversal relationships and determining whether an already visited node can be reached through an appropriate alternative path.
Cycle detection can be useful when analyzing graph structure, validating network representations, or identifying recurring relationship patterns.
In an undirected network, for example, encountering a previously visited neighbor that is not simply the node from which the current node was reached can indicate the presence of a cycle.
DFS and Bridges.
DFS has an important connection with the identification of bridges in a network.
A bridge is an edge whose removal increases the number of connected components.
Consider:
Community A Community B
A ─ B ─ C ──────────── D ─ E ─ F
↑
bridgeThe edge connecting C and D acts as a bridge between two portions of the network. If that relationship disappears:
A ─ B ─ C D ─ E ─ Fthe network becomes disconnected. DFS-based algorithms can identify such structurally critical edges by analyzing the traversal tree and the ability of nodes to reach previously discovered parts of the graph through alternative paths.
This is particularly relevant when studying network vulnerability and structural dependencies.
DFS and Articulation Points
A related concept is the articulation point, also called a cut vertex. An articulation point is a node whose removal can disconnect part of the network.
For example:
Community A
A ─ B ─ C
│
D
│
X
│
E ─ F ─ GIf X is the only node connecting the two regions, removing X separates them. DFS provides the foundation for efficient algorithms that identify articulation points by maintaining information about:
- discovery order,
- DFS tree relationships,
- and whether descendants have alternative paths back to earlier nodes.
This allows DFS to move beyond simple traversal and become a tool for analyzing structural vulnerabilities in networks.
DFS and Graph Traversal Trees
During execution, DFS naturally produces a DFS tree. Suppose the original network is:
A
/ \
B C
/ \ \
D E FA possible DFS tree could be:
A
│
B
├── D
└── E
│
C
└── FThe DFS tree records the relationships through which nodes were discovered.
This representation is useful because many graph algorithms can analyze the DFS tree to derive additional structural information.
In SNA, this can help researchers reason about connectivity, cycles, bridges, articulation points, hierarchical traversal structure, and other graph properties.
DFS and Shortest Paths
Unlike BFS, standard DFS does not generally find shortest paths in an unweighted graph. Consider this network:
A ─ B ─ C
\ /
─ DThere are 2 possible routes from A to C: A → B → C and: A → D → C. But, both have length 2. More generally, DFS may encounter a longer route before discovering a shorter one. Therefore: DFS is primarily a graph traversal strategy, not a shortest-path algorithm.
For unweighted shortest-path problems, BFS is usually the appropriate fundamental algorithm.
DFS can still be useful when the objective is to understand reachability and graph structure rather than minimize path length.
DFS and Large Social Networks
For a graph represented using adjacency lists, DFS has a time complexity of: O(∣V∣+∣E∣)
where: ∣V∣ = number of nodes and |E| = number of edges.
DFS algorithm may need O(∣V∣) additional space for information such as: visited nodes, the DFS stack, recursion state, or traversal metadata.
This makes DFS computationally efficient for many sparse social networks.
However, efficiency does not eliminate the challenges of scale. Very large social networks may contain millions or billions of nodes and edges, requiring distributed graph-processing systems or specialized graph algorithms.
DFS in the Broader SNA Algorithm Landscape
DFS belongs to the foundational layer of graph algorithms:
Graph Algorithms
│
┌────────────────┴────────────────┐
│ │
Traversal Shortest Path
│ │
┌───┴───┐ ┌───┴────┐
│ │ │ │
BFS DFS Dijkstra ...
│ │
│ ├── Connectivity
│ ├── Cycle Detection
│ ├── Bridges
│ └── Articulation Points
│
└── Shortest Paths
in unweighted graphsUnderstanding DFS therefore provides an important foundation for moving from basic graph traversal toward more advanced topics such as connectivity analysis, community structure, network vulnerability, and graph-based machine learning.
The key idea is:
BFS explores a network outward in layers, while DFS explores a network inward along branches. In SNA, this depth-oriented traversal makes DFS particularly useful for understanding connectivity and structural properties of complex networks.
BFS vs. DFS in Social Network Analysis
Both Breadth-First Search (BFS) and Depth-First Search (DFS) are fundamental graph traversal algorithms used to explore social networks. The main difference is how they explore the network.
In SNA.
The choice depends on the question you are asking:
- BFS is particularly useful when you care about distance and reachability, such as determining how many relationships separate users.
- DFS is particularly useful when you care about network structure and connectivity, such as finding connected components, bridges, or articulation points.
A simple way to remember the difference is: BFS explores outward; DFS explores inward.
Both have the same asymptotic time and space complexity for adjacency-list graph traversal, but they expose different aspects of the network’s structure.
