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

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 proposal. Due October 20th in class.
- Project in-class presentation (15 minutes). Last week of classes (December 6th and 8th)
- Project writeup. Due December 3rd, with an optional 1-week writing extension due December 10th.

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.