Graphs and Adjacency Matrices

Relationships That Do Not Have to Be Mutual

Adjacency Matrices

An adjacency matrix ( A ) of a graph records who is connected to whom:

[ A_{ij} = \[\begin{cases} 1 & \text{if there is an edge from } i \text{ to } j \\ 0 & \text{otherwise} \end{cases}\]

]

Nothing forces ( A_{ij} = A_{ji} ). A directed edge can exist in one direction only. That is the technical starting point: relationships need not be symmetric.

Directed graph (asymmetric)

g <- graph_from_literal(1 - +2, 1 - +3, 2 - +3, 3 - +4, 4 - +2, 2 - +1)
A <- as_adjacency_matrix(g, sparse = FALSE)

par(mfrow = c(1, 2))
plot(g,
  vertex.color = "lightblue", edge.arrow.size = 0.6,
  main = "Directed graph"
)
image(t(A[nrow(A):1, ]),
  axes = FALSE, col = c("white", "steelblue"),
  main = "Adjacency matrix A"
)
box()

A small directed graph and its (non-symmetric) adjacency matrix

  1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 0 0 0 1
4 0 1 0 0

Undirected graph (forced symmetry)

When every edge is mutual we obtain an undirected graph. Its adjacency matrix satisfies ( A = A^) — the matrix is equal to its own transpose (its “mirror”).

g_und <- as.undirected(g, mode = "collapse")
A_und <- as_adjacency_matrix(g_und, sparse = FALSE)

par(mfrow = c(1, 2))
plot(g_und, vertex.color = "lightgreen", main = "Undirected graph")
image(t(A_und[nrow(A_und):1, ]),
  axes = FALSE, col = c("white", "darkgreen"),
  main = "Symmetric adjacency matrix"
)
box()

The same vertices made undirected: A becomes symmetric

p5.js: draw directed vs. mutual links

Click to add directed edges. Nothing forces the reverse edge to exist.

Why This Matters for Design

In the real world most relations are directed or only partially mutual:
influence, gaze, citation, one-way streets, “follows” on a social network.
The adjacency matrix records that asymmetry without apology.

The next document asks what happens when we idealize the situation and demand that every relationship be perfectly mirrored.