3.15 Adjacency matrices and walks
Studying this course? Keep your progress in one place.
Key facts
- The adjacency matrix of a graph with vertices is ; entry counts edges from to .
- An undirected graph gives a symmetric matrix; a simple graph has zeros on the leading diagonal.
- The entry of is the number of walks of length from to .
- For walks of length at most , add .
- In a transition matrix each column sums to 1; a steady state satisfies .
Adjacency matrices
A graph is stored as a square matrix whose entry counts the edges joining vertex to vertex .
The adjacency matrix of a graph with vertices is . 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 to , 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 with links , , , give
What is the row sum of row R in the matrix above?
Walks and powers
The entry of is the number of walks of length from vertex to vertex .
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 has entry 1, the single walk , and has entry 4.
For a directed graph, read the entry as walks from the row vertex to the column vertex.
- Entry of walks of length from to
Worked example
In the router example, how many walks of length 2 start and end at ?
- 1
Length 2 means the matrix power .
- 2
Read row , column of : the entry is 3.
- 3
Check by listing: , and .
What is the entry of for the router network?
Walks of at most k
To count walks of length at most , add the powers and read the entry you need.
Take a road network with villages . The entries of , and are , and . So there are walks of length at most 3 from to .
Walks of length 0 are not counted unless the question says so.
- 1
Find each power
on the GDC
- 2
Pick the entry
the same in every power
- 3
Add them up
the total is the number of walks
In the router network, how many walks of length at most 2 go from to ?
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 , column is the weight of the edge from to . Where there is no direct edge write a dash, or sometimes 0, as the question states. A two-way road gives a symmetric table.
Roads , , , , give rows , , and .
Powers of a weighted table do not count walks. For walks use the 0/1 matrix.
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 of a transition matrix is the probability of moving from to , so each column sums to 1. Build it by dividing each column of links by its sum.
If is the start, . A steady state satisfies with entries summing to 1 (see Markov chains, 4.19).
Pages to with ; ; ; give
Worked example
Start at page , so . Find the probabilities after 2 clicks.
- 1
is the first column of : .
- 2
. Row : . Row : .
- 3
Row : . Row : .
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 gives , so and rank highest.
A new link shares a column's probability among more pages. If linked to both and , column would become .
Which pages have the highest page rank in the four-page example?
Try an exam question
A network has vertices with edges , , and and adjacency matrix . Write down , and find the number of walks of length 2 from to , justifying your answer.
[4 marks]
- [1]Correct symmetric matrix with rows , , , .
- [1]Uses the entry of .
- [1]Obtains 3.
- [1]Justifies by listing , , .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which of these is the row of that belongs to router ?
1 mark, marked against the mark scheme
Which of these is the row of that belongs to router ?
1 mark, marked against the mark scheme