image of a large network

Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

Tuesdays and Thursday, 10:30am-11:45am

CIVL 2123

Homework 3

These problems are due in-class on November 3rd.

Problem 1 (5 pts)

For a simple, undirected graph, show that the sum of the eigenvalues of its adjacency matrix must be equal to 0.
(This is a quick problem.)

Solution The trace of the matrix is 0 because there are no self-loops, so the sum of the eigenvalues is too.

Problem 2 (10 pts)

You’ve recently been hired as a senior researcher at Bingle!, a new scrappy search startup. They want to test out some algorithms for weakly preferential PageRank because they don’t think that resetting “everywhere” from a dangling node is a realistic model. However, they only have a routine to compute a strongly preferential PageRank vector. That is, they have a program pagerank(alpha,v) that solves the system

(\eye - \alpha \mPbar - \alpha \vv \vd^T) \vx = (1-\alpha)\vv

on their distributed MapReduce cluster for their current crawl of the web. The matrix is a column sub-stochastic matrix from a hand-tuned random walk process on their web graph, and is the dangling node vector
It’s very time-consuming and expensive to change that code (and so, for this problem, you cannot). They’ve asked you to determine if there is another way to compute weakly preferential PageRank.

Thankfully, you’ve taken CS-59000 NMC at Purdue, and this is your chance to shine and earn your yearly bonus early. Show how to compute a weakly preferential PageRank vector by using their pagerank(alpha,v) routine and one additional routine mult(x) which computes . Psst, the weakly preferential PageRank system is:

(\eye -\alpha \mPbar - \alpha \vu \vd^T) \vy = (1-\alpha) \vv.

Solution The simplest way to solve the problem is to notice that we can convert into the solution of a PseudoRank system by computing: , which involves a multiplication, a difference, and a summation. Thus, we find satisfies

(\eye - \mPbar) \hat{\vx} = \vv.

We can do the same thing with the solution of as well. This means we have all the ingredients to apply the Sherman-Morrison formula. However, we can do better. (In fact, this is usually true when you apply the Sherman-Morrison formula – there is almost always a better way, so use it for intuition and not algorithms.)

Notice that

(\eye - \alpha \mPbar - \alpha \vu \vd^T ) \vx + \alpha \gamma \vu - \alpha \gamma \vv = (1-\alpha) \vv.

Also, we have Consequently,

(\eye - \alpha \mPbar - \alpha \vu \vd^T ) (\vx + \frac{\alpha \gamma}{1-\alpha} \vw) = (1-\alpha + \alpha \gamma) \vv.

At this point, we are basically done, because we have a linear combination of and that is equal to a multiple of Because the solution must sum to one, we just have to normalize this vector and we are done.

Hence, the algorithm is:

  1. Compute x = pagerank(alpha,v)
  2. Compute w = pagerank(alpha,w)
  3. Compute gamma = sum(x - mult(x))
  4. Set y = x + alpha*gamma/(1-\alpha)*w
  5. Update y = y/sum(y)

Problem 3 (10 pts)

Google recently announced a change in how they process rel=nofollow links on the web. Please read about it here: Mathematically describe how this change affects how Google constructs the matrix for PageRank.


Let be the graph of links without no-follow and be the graph of links with no-follow, and let and be the respective degree matrices. . Then the original PageRank formulation used as the web-graph and normalized it as to get a random walk. The new formulation uses to normalize the walk.

Problem 4 (10 pts)

Bingle! is back with another problem. One of their interns implemented a super-duper fast routine to compute a PseudoRank vector:

(\eye - \alpha \mPbar) \vy = \vv.

This intern claimed that they could replace all their PageRank computations using this routine if they just normalized , i.e. . Unfortunately, the intern was hired by the White House to help manage the government’s data efforts and left without justifying this result. There is apparently no time left to handle Bingle!’s email’s marked URGENT!

And so, they come to you. Can you solve the mystery of the normalization? To be precise, show exactly that is the correct adjustment to .

Solution This is implicit in the first problem. The key is to show that by using and . Then show that solves .

Problem 5 (5 pts)

Tell me your preferred ranking of the following days for the in-class presentations:

Rank each day from 1-4. There is no guarantee I’ll be able to assign you to the day you’d like, but we’ll see what we can do.

Due to scheduling details at the end of class, we will have to adjust the length of the presentations. We need two people to volunteer to split their presentation over two days (so we can do 2.5 presentations a day). If you’d be willing to split your presentation, please let me know.