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


For the course project, you will have to utilize the tools of the coures to study a problem on networks using matrix computations.

Project ideas

Look at Inderjit Dhillon’s low-“parameter” work with overlap among the partitions. http://www.cs.utexas.edu/users/inderjit/public_papers/clustered_low_rank_sdm11.pdf

Take a stab at a matrix formulation of William Cohen’s “path ranking algorithm” (ECML) http://www.cs.cmu.edu/~wcohen/postscript/emnlp-2011.pdf.

Open Investigate how to compute the limiting PageRank vector efficiently. That is, consider the PageRank function of :

(\mI - \alpha \mP) \vx(\alpha) = (1-\alpha) \vv

It is known that exists, but there is not an efficient algorithm to compute it. (Except when comes from an undirected graph, see below.) Investigate this problem.

Open Look into fast way of computing the PageRank vector of an undirected graph. (Fast here means faster than using a PageRank algorithm.) Let be the adjacency matrix of a connected undirected graph, and be the uniform random walk on the graph.
Consider

(\mI - \alpha \mP) \vx(\alpha) = (1-\alpha) \vv

In this case, we know that . However, I’ve never seen a simple expression for for . Study this problem.

Look into the asymmetric Laplacian matrices and commute times of directed networks: http://www-users.cs.umn.edu/~granjan/Reports/LAA_2011_AsymLap.pdf

If not solved in class Look into the semi-ring algorithms for Boruvka’s minimum spanning tree algorithm and for checking if a graph is aperiodic.

Project work

Let me clarify the writing extension. Writing is one of the most important skills to cultivate. Consequently, you may – at your discresion – take an extra week to improve the writing. In this case, you’ll be expected to turn in a “complete” draft on December 3rd, and improve the writing over the following week.