9.03 Degree and adjacency

The degree of the vertex is the number of edges that either go into or out of a vertex, where loops are counted twice. This number tells us how many ways we can move from that vertex to another (or back to the same) vertex within the network.

A useful trick is to make a small ring around the vertex then count up the number of times that edges cross the ring at a vertex, and you’ll have the degree:

The degree of a vertex tells you how well-connected that particular vertex is to the rest of the network - the higher the degree, the more ways it is linked to the vertices in the network.

 

Adjacency matrices (undirected networks)

It is sometimes useful to use an adjacency matrix to represent a network. An adjacency matrix is a table with a square array of numbers, one row and column for each vertex, that records how many connections there are between the vertices. For an undirected network, the entry for a particular row and column represents the number of edges connecting the matching vertices.

Here’s a simple network with five vertices:

Now we can create a table, with one row and column for each vertex:

Then we write the number edges connecting two vertices as the corresponding table entry. Let’s start by filling out the first row with a $1$1 if it is connected to $A$A, and a $0$0 if it isn’t.

$0$0 comes first, because $A$A isn’t connected to itself (there’s no loop at $A$A), and $A$A is connected to $B$B, $C$C, $D$D, and $E$E, so we write a $1$1 for each other entry in the table.

These edges are undirected, we can fill out the first column with the same numbers - if $A$A is connected to $B$B, then $B$B is connected to $A$A, and so on:

Now to fill out the second row, we notice that $B$B is connected to $A$A (already recorded), not itself (no loop), and it is connected to $C$C, $D$D, and $E$E:

We then record the remaining connections between $C$C, $D$D, and $E$E in the same way:

This is our completed matrix! Notice that:

• The diagonal running top-left to bottom-right (called the main diagonal) has only $0$0's.
  This shows that no edge is connected to itself in the network - there are no loops.
• The numbers not on the main diagonal are only $0$0s and $1$1s.
  This shows that no vertex is connected to any other by more than one edge.

All adjacency matrices representing simple networks will have these features.

As an added bonus the sum of all the entries in a row (or column) gives us the degree of the corresponding vertex - we can tell from the table that $E$E has degree $2$2, $C$C and $D$D have degree $3$3, and $A$A and $B$B have degree $4$4. This trick doesn't work if the network has loops, though - in this case, numbers on the main diagonal need to be doubled, to make sure they're counted twice.

 

Adjacency matrices (directed networks)

Now for a directed network, the entry in a particular row and column indicates the number of edges going from the corresponding row vertex to the corresponding column vertex. Here’s a directed, non-simple network with $5$5 vertices and its corresponding table:

This table looks a little different from the last one! Notice that:

• the table is not symmetrical across the main diagonal (an edge from $A$A to $B$B can exist without an edge from $B$B to $A$A),
• there is a $1$1 on the main diagonal (there is a loop at $C$C)
• there is a $2$2 in the table (there are two edges from $D$D to $E$E).

An asymmetrical table means the network is directed, but be careful - some directed networks produce symmetrical tables.

 

Creating networks from adjacency matrices

Up until now we have used networks to make adjacency matrices. But we can go back the other way. To create the network, all we need is the information in these tables, and knowing whether the network is directed or undirected!

Here’s a table with $6$6 rows and columns (so there are $6$6 vertices in the network), and we are also told that the network is undirected.

This is a representation of the network that we get when we draw it out:

We start with the first row, and the vertex on the left. We draw in the edges connected to that vertex. Then we move on to the next row and move to the next vertex clockwise, ignoring the numbers below the main diagonal - they get drawn into the network when we do earlier rows for undirected networks. If the graph is directed, all the numbers need to be turned into edges.

Practice questions

Question 1

Question 2

Question 3