Matrices For Graphs

A graph is a collection of points, called nodes or vertices, with connections among them, called edges. It has nothing to do with the "graph of a function" that you've used in calculus. Nevertheless, you have seen many examples of graphs in your life. The streets in a city can be thought of as a graph, with a node for each intersection and an edge whenever there is a street connecting one intersection to another. On a larger scale, imagine a system of highways among several cities; this is also a graph. Another popular graph is the Internet, whose nodes are computers and whose edges are network connections among those computers.

Adjacency Matrices

Two nodes in a graph are said to be adjacent if there is an edge between them. An adjacency matrix is a matrix that expresses the adjacency relationships in a graph. The (i, j)th entry is a 1 if there is an edge between node i and node j; otherwise, the entry is 0.

We begin by entering an adjacency matrix for a graph of 5 nodes. Notice that the matrix is symmetric about the diagonal; why must this be?

a = {{0, 1, 1, 1, 0}, {1, 0, 0, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 0, 0, 1, 0}};
MatrixForm[a]
Needs["Combinatorica`"]
ShowGraph[FromAdjacencyMatrix[a]]

Examine the matrix powers below. What does the (i, j)th entry in each power tell you about the graph? Can you find a pattern? Here's a hint: In the original adjacency matrix, the (i, j)th entry told us how many ways there were to go from node i to node j in 1 step.

MatrixForm[a.a]
MatrixForm[a.a.a]
MatrixForm[a.a.a.a]

What does the following sum of matrices tell you?

MatrixForm[a + a.a + a.a.a + a.a.a.a]

Adjacency Matrices For Directed Graphs

In the previous section we assumed that our graph was undirected, meaning that the edges were two-way. In a directed graph, the edges are one-way. This can be used to model a system of one-way streets, for example. If you want to include a two-way street, you can; just add an edge going one direction and another edge going the other direction.

Suppose now that we enter the adjacency matrix of a directed graph with 6 nodes:

b = {{0, 0, 1, 1, 1, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0}};
MatrixForm[b]
Needs["Combinatorica`"]
ShowGraph[FromAdjacencyMatrix[b, Type->Directed]]

Examine the powers of the adjacency matrix. Does the pattern from the previous section still hold?

MatrixForm[b.b]
MatrixForm[b.b.b]
MatrixForm[b.b.b.b]

What does the sum of the powers tell you?

MatrixForm[b + b.b + b.b.b + b.b.b.b]

Deterministic PageRank

You've probably used the web search engine Google. This section presents a simplified, deterministic (non-probabilistic) version of the famous PageRank algorithm that it uses to rate web pages. If we have time later in the term, we'll explore a more sophisticated version.

Here is the basic idea, as described by Google at http://www.google.com/technology/:

'PageRank relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page's value. In essence, Google interprets a link from page A to page B as a vote, by page A, for page B. But, Google looks at more than the sheer volume of votes, or links a page receives; it also analyzes the page that casts the vote. Votes cast by pages that are themselves "important" weigh more heavily and help to make other pages "important".'

So the value of each page is determined by how many pages point to it and how valuable those pages are. The quote leaves out an important detail: If a page is valuable, then it adds value to all of the pages that it points to, but its value gets split among all of those pages.

Let's conceptualize the web as a directed graph, in which the nodes are the web pages and there is an edge between node i and node j if page i has a link to page j. Then we can make an adjacency matrix. For example, here's an adjacency matrix for a web consisting of n = 8 web pages:

c = {{0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 1, 0, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 0, 0, 1, 0}};
MatrixForm[c]
Needs["Combinatorica`"]
ShowGraph[FromAdjacencyMatrix[c, Type->Directed]]

This command builds a list called numLinks, whose jth element is the number of links on page j.

numLinks = Map[Total, c]

The "contribution coefficient" of page j to page i indicates how much of page j's value gets added to page i's value. If there is no link from page j to page i, then the coefficient should be 0. If there is a link from page j to page i, but page j has m links in all, then the contribution coefficient should be 1 / m. The following command builds the matrix of contribution coefficients; don't worry about the complicated Mathematica syntax used.

d = Transpose[c] / (Table[numLinks, {Length[numLinks]}] /. 0 -> 1);
MatrixForm[d]

Now let p_i denote the value of page i. Page 1 contributes d_i1 p_1 to it, page 2 contributes d_i2 p_2 to it, and so on. So p_i = d_i1 p_1 + ... + d_in p_n. This is a linear equation. We get a linear equation like this for each p_i. Taken together, these linear equations amount to a matrix equation p = d p, which is equivalent to (d - I) p = 0.

vec = Array[p, Length[numLinks]]
answer = Solve[d.vec == vec, vec]

The value of p_8 is undetermined, but once we choose it, the values of the other p_i are determined. Let's set p_8 to 1, just to clear things up:

answer /. p[8] -> 1

Why should page 2 have value 0? Do the other value ratings seem reasonable? In particular, p_4 = 27/22 and p_8 = 1; do you believe that page 4 is more valuable than page 8? They both have three incoming links.