How to Represent a Directed Graph as an Adjacency Matrix
With examples in R
Graphs are an excellent way of showing high-dimensional data in an intuitive way. But when it comes to representing graphs as matrices, it can be a little less intuitive. Earlier, we looked at how to represent an undirected graph as an adjacency matrix. In this tutorial, we’ll be looking at representing directed graphs as adjacency matrices.
Unlike an undirected graph, directed graphs have directionality. This is generally represented by an arrow from one node to another, signifying the direction of the relationship. Twitter and Instagram are excellent examples of directed graphs since you can follow a person without them following you back. Now, let’s get started on looking at how to represent directed graphs as adjacency matrices. For this tutorial, we’ll be using the visNetwork package and we’ll begin by looking at a directed graph with no loops, or self-edges.
Example 1: small directed graph with no loops
To start, we’ll create a nodes data frame for visNetwork to initialize our network nodes. Our network will consist of 6 nodes, labeled 1 through 6. Then, we’ll create an edges data frame to add relationships between our nodes. To make sure the network is directed, the edges data frame will have an arrows column signifying the direction of the relationship. In this example, all relationships will flow from the from column ‘to’ the to column. Finally, we’ll plot our network using visNetwork().
library(visNetwork) # Create nodes dataframe for visNetwork.
nodes <- data.frame (id = 1:6, label = 1:6,
color = rep('#8BB1AB', 6)) # Create edges dataframe for visNetwork.
edges <- data.frame(from = c(1, 2, 3, 3, 4, 5),
to = c(2, 3, 4, 5, 5, 6), arrows = 'to') # Plot network using visNetwork.
visNetwork(nodes, edges) %>% visOptions(highlightNearest = TRUE,
nodesIdSelection = TRUE)
Similar to what we did for undirected graphs, we’ll let the rows and columns of our adjacency matrix represent nodes, or vertices. This will result in a square matrix. However, unlike undirected graphs, a 1 indicates an arrow running from column j to row i. NOTE: You may see this the other way around, with an arrow running from column i to row j. Make sure you know which version is in use.
For the graph above, the adjacency matrix looks like this:
Since there’s an edge going from node 1 to 2, we see a 1 in
(row 2, column 1). This directionality often results in an asymmetric matrix. Furthermore, we can see the diagonal consists entirely of zeros since there are no edges from any node to itself. Now, let’s look at an example where we have loops and multi-edges.
Example 2: small directed graph with loops and multi-edges
In this example, we’ll keep our nodes data frame from above, but specify a new data frame of edges. Since we want loops, we’ll have a relationship going from 2 to 3 and from 3 to 2, giving us a loop. The second sort of loop we’ll create is a self-edge, where a relationship loops back on itself. We’ll establish a self-edge with node 1 by having a relationship go from 1 to 1. Finally, we’ll store all our new relationships in a data frame named edgesMessy.
# Create new edges dataframe for visNetwork.
edgesMessy <- data.frame(from = c(1, 2, 3, 3, 4, 5, 1, 3, 5, 5),
to = c(2, 3, 4, 5, 5, 6, 1, 2, 6, 6),
arrows = 'to') # Plot network using visNetwork.
visNetwork(nodes, edgesMessy) %>%
visOptions(highlightNearest = TRUE, nodesIdSelection = TRUE)
Here, the adjacency matrix looks as follows:
Notice that a loop is represented as a 1. For directed graphs, each directed relationship is counted and the loop is only one directed relationship. (If there were two loops for node 1, the entry would be 2.) We can also see that there are three edges between nodes 5 and 6. Therefore,
is now represented by a 3.
To recap:
- adjacency matrices are always square
- adjacency matrices for directed graphs are not always symmetric
- a directed graph with no loops will have zeros along the diagonal
- each loop in an undirected graph is represented by a 1
- adjacency matrices can account for multi-edges
Originally published at https://thatdarndata.com on February 16, 2022.
