3.15 Adjacency matrices and walks

3.15 Adjacency matrices and walks

IB Maths: Applications and Interpretation HL: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The adjacency matrix of a graph with nn vertices is n×nn\times n; entry (i,j)(i,j) counts edges from ii to jj.
  • An undirected graph gives a symmetric matrix; a simple graph has zeros on the leading diagonal.
  • The (i,j)(i,j) entry of Ak\mathbf{A}^k is the number of walks of length kk from ii to jj.
  • For walks of length at most kk, add A+A2+⋯+Ak\mathbf{A}+\mathbf{A}^2+\cdots+\mathbf{A}^k.
  • In a transition matrix each column sums to 1; a steady state satisfies Ts=s\mathbf{T}\mathbf{s}=\mathbf{s}.

Adjacency matrices

A graph is stored as a square matrix whose entry (i,j)(i,j) counts the edges joining vertex ii to vertex jj.

The adjacency matrix of a graph with nn vertices is n×nn\times n. For a simple undirected graph the entries are 0 or 1, the leading diagonal is zero and the matrix is symmetric.

For a directed graph the entry counts edges from ii to jj, so it need not be symmetric. A row sum is the degree of a vertex (out-degree if directed) and a column sum is the in-degree.

Routers P,Q,R,SP,Q,R,S with links PQPQ, PRPR, QRQR, RSRS give

A=(0110101011010010)\mathbf{A}=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}

PQRS
The router network. Each link appears twice in the matrix: row P column Q and row Q column P.

What is the row sum of row R in the matrix above?

Walks and powers

The (i,j)(i,j) entry of Ak\mathbf{A}^k is the number of walks of length kk from vertex ii to vertex jj.

A walk is a sequence of edges in which each edge starts where the previous one ends. Edges and vertices may repeat. Its length is the number of edges.

Use your GDC to find the matrix power. In the router example A3\mathbf{A}^3 has (P,S)(P,S) entry 1, the single walk P→Q→R→SP\to Q\to R\to S, and A4\mathbf{A}^4 has (P,S)(P,S) entry 4.

For a directed graph, read the entry as walks from the row vertex to the column vertex.

PQRS
The router network: links PQ, PR, QR and RS
  • Entry (i,j)(i,j) of Ak\mathbf{A}^kwalks of length kk from ii to jj

Worked example

In the router example, how many walks of length 2 start and end at RR?

What is the (P,S)(P,S) entry of A4\mathbf{A}^4 for the router network?

Walks of at most k

To count walks of length at most kk, add the powers A+A2+⋯+Ak\mathbf{A}+\mathbf{A}^2+\cdots+\mathbf{A}^k and read the entry you need.

Take a road network with villages W,X,Y,ZW,X,Y,Z. The (W,Z)(W,Z) entries of B\mathbf{B}, B2\mathbf{B}^2 and B3\mathbf{B}^3 are 00, 22 and 22. So there are 0+2+2=40+2+2=4 walks of length at most 3 from WW to ZZ.

Walks of length 0 are not counted unless the question says so.

  1. 1

    Find each power

    A,A2,…,Ak\mathbf{A},\mathbf{A}^2,\dots,\mathbf{A}^k on the GDC

  2. 2

    Pick the entry

    the same (i,j)(i,j) in every power

  3. 3

    Add them up

    the total is the number of walks

Counting walks of at most length k

In the router network, how many walks of length at most 2 go from PP to RR?

Weighted adjacency tables

In a weighted table the entry is the weight of the edge (a cost, distance or time), not a count.

For a weighted graph the entry in row ii, column jj is the weight of the edge from ii to jj. Where there is no direct edge write a dash, ∞\infty or sometimes 0, as the question states. A two-way road gives a symmetric table.

Roads WX=12WX=12, WY=7WY=7, XY=5XY=5, XZ=9XZ=9, YZ=4YZ=4 give rows W:(−,12,7,−)W:(-,12,7,-), X:(12,−,5,9)X:(12,-,5,9), Y:(7,5,−,4)Y:(7,5,-,4) and Z:(−,9,4,−)Z:(-,9,4,-).

Powers of a weighted table do not count walks. For walks use the 0/1 matrix.

weight 12weight 7weight 5weight 9weight 4WXYZ
The road network. Its weighted table is symmetric.

Can you square a weighted table to count walks of length 2?

Transition matrices

A transition matrix holds the probabilities of moving between states, and each column sums to 1.

In this course entry (i,j)(i,j) of a transition matrix T\mathbf{T} is the probability of moving from jj to ii, so each column sums to 1. Build it by dividing each column of links by its sum.

If s0\mathbf{s}_0 is the start, sn=Tns0\mathbf{s}_n=\mathbf{T}^n\mathbf{s}_0. A steady state satisfies Ts=s\mathbf{T}\mathbf{s}=\mathbf{s} with entries summing to 1 (see Markov chains, 4.19).

Pages AA to DD with A→B,CA\to B,C; B→CB\to C; C→A,DC\to A,D; D→AD\to A give

T=(00121120001210000120)\mathbf{T}=\begin{pmatrix} 0 & 0 & \tfrac12 & 1 \\ \tfrac12 & 0 & 0 & 0 \\ \tfrac12 & 1 & 0 & 0 \\ 0 & 0 & \tfrac12 & 0 \end{pmatrix}

ABCD
Four web pages. An arrow shows a link from one page to another.

Worked example

Start at page AA, so s0=(1,0,0,0)T\mathbf{s}_0=(1,0,0,0)^T. Find the probabilities after 2 clicks.

In this convention, which sum to 1?

PageRank

PageRank ranks a page by the long-run chance that a random surfer is on it: its steady-state probability.

The PageRank algorithm treats pages as vertices and links as directed edges. A surfer follows links at random, so the movement is a transition matrix.

For the four pages above, solving Ts=s\mathbf{T}\mathbf{s}=\mathbf{s} gives s=(13,16,13,16)\mathbf{s}=\left(\tfrac13,\tfrac16,\tfrac13,\tfrac16\right), so AA and CC rank highest.

A new link shares a column's probability among more pages. If DD linked to both AA and BB, column DD would become (12,12,0,0)T\left(\tfrac12,\tfrac12,0,0\right)^T.

00.050.10.150.20.250.30.35ABCDPageProbability
Steady-state probability of each page. A and C rank highest.

Which pages have the highest page rank in the four-page example?

Try an exam question

A network has vertices P,Q,R,SP,Q,R,S with edges PQPQ, PRPR, QRQR and RSRS and adjacency matrix A\mathbf{A}. Write down A\mathbf{A}, and find the number of walks of length 2 from RR to RR, justifying your answer.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which of these is the row of A\mathbf{A} that belongs to router RR?

1 mark, marked against the mark scheme

Revision notes