3.15 Adjacency matrices and walksIB Maths: Applications and Interpretation HL: Revision notes

The adjacency matrix of a graph with $n$ vertices is an $n\times n$ matrix whose entry in row $i$, column $j$ is the number of edges joining vertex $i$ to vertex $j$. For a simple undirected graph the entries are 0 or 1, the leading diagonal is all zeros, and the matrix is symmetric. For a directed graph the entry counts edges from $i$ to $j$, so the matrix need not be symmetric. Example: routers $P,Q,R,S$ with links $PQ$, $PR$, $QR$, $RS$ give $\mathbf{A}=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ Each row sum is the degree of that vertex; for a directed graph a row sum is the out-degree and a column sum is the in-degree.

A walk is a sequence of edges in which each edge starts where the previous one ends; edges and vertices may be repeated. Its length is the number of edges. The key result: the $(i,j)$ entry of $\mathbf{A}^k$ is the number of walks of length $k$ from vertex $i$ to vertex $j$. Use your GDC to find the power. In the router example, $\mathbf{A}^3$ has $(P,S)$ entry 1, the single walk $P\to Q\to R\to S$, and $\mathbf{A}^4$ has $(P,S)$ entry 4. For a directed graph read the entry as walks from the row vertex to the column vertex.

To count walks of length at most $k$ between two vertices, add the matrices: $\mathbf{A}+\mathbf{A}^2+\cdots+\mathbf{A}^k$, and read the $(i,j)$ entry. Example: for the road network with $\mathbf{B}$ (villages $W,X,Y,Z$), the $(W,Z)$ entries of $\mathbf{B}$, $\mathbf{B}^2$ and $\mathbf{B}^3$ are $0$, $2$ and $2$, so there are $4$ walks of length at most 3 from $W$ to $Z$. Walks of length 0 are not counted unless the question says so.

For a weighted graph the table's entry in row $i$, column $j$ is the weight of the edge from $i$ to $j$ (a cost, distance or time). Where there is no direct edge, write a dash, $\infty$ or sometimes 0, as the question states. For two-way roads the table is symmetric. Example: roads $WX=12$, $WY=7$, $XY=5$, $XZ=9$, $YZ=4$ give $\begin{pmatrix} \text{–} & 12 & 7 & \text{–} \\ 12 & \text{–} & 5 & 9 \\ 7 & 5 & \text{–} & 4 \\ \text{–} & 9 & 4 & \text{–} \end{pmatrix}$ Powers of a weighted table do not count walks; to count walks use the unweighted matrix with 0s and 1s.

A transition matrix $\mathbf{T}$ describes moving between states with probabilities. In this course the entry in row $i$, column $j$ is the probability of moving from $j$ to $i$, so every column sums to 1. For a strongly connected graph, build $\mathbf{T}$ so that column $j$ shows the links leaving vertex $j$ (the transpose of a row-from adjacency matrix), then divide each column by its sum, so that each link from a vertex is equally likely. If $\mathbf{s}_0$ is the starting state, then $\mathbf{s}_n=\mathbf{T}^n\mathbf{s}_0$. A steady state satisfies $\mathbf{T}\mathbf{s}=\mathbf{s}$ with entries summing to 1; this links to Markov chains (AHL 4.19). Example: pages $A$ to $D$ with $A\to B,C$; $B\to C$; $C\to A,D$; $D\to A$ give $\mathbf{T}=\begin{pmatrix} 0 & 0 & \frac12 & 1 \\ \frac12 & 0 & 0 & 0 \\ \frac12 & 1 & 0 & 0 \\ 0 & 0 & \frac12 & 0 \end{pmatrix}$ Starting at $A$, after 2 clicks the probabilities are $\left(\frac14,0,\frac12,\frac14\right)$.

The Google PageRank algorithm treats web pages as vertices and links as directed edges. A surfer follows links at random, so the surfer's movement is described by a transition matrix. In the long run the probability of being on each page settles to the steady state, and the page rank is this probability: the larger it is, the more important the page. For the four pages above, solving $\mathbf{T}\mathbf{s}=\mathbf{s}$ gives $\mathbf{s}=\left(\frac13,\frac16,\frac13,\frac16\right)$, so pages $A$ and $C$ rank highest. If a page adds a new link, the probabilities in its column are shared among more pages: if $D$ linked to both $A$ and $B$, column $D$ would become $\left(\frac12,\frac12,0,0\right)^T$.