# Network & Matrix Computations

### 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 $\alpha$:

It is known that $\lim_{\alpha \to 1} \vx(\alpha)$ exists, but there is not an efficient algorithm to compute it. (Except when $\mP$ 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 $\mA$ be the adjacency matrix of a connected undirected graph, and $\mP$ be the uniform random walk on the graph.
Consider

In this case, we know that $\vx(1) = \mA \ve/(\ve^T \mA \ve)$. However, I’ve never seen a simple expression for $\vx(\alpha)$ for $\alpha < 1$. 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

• 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.