Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

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

CIVL 2123

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

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$:

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

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

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

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.