Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

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

CIVL 2123

Networks and Matrix Computations

Homeworks

The third assignment is due November 3rd in class.

The project proposal is due October 16th in class.

The second assignment is due October 7th in class.

The first assignment is due September 20th in class.

The intial survey is due August 25th.

Abstract

This topics class will probe the intersection and relationship between problems stated on a network (a graph) and their solution, or approximation, via a matrix computation.

Selected topics will include

• Spectral graph theory
• Random walks on graphs
• Google’s PageRank and its many relatives (GeneRank, SimRank, IsoRank, ProteinRank, HostRank, TrustRank, BadRank)
• Network alignment
• Local algorithms for community detection/graph partitiong

This class will require familiarity with basic network algorithms (e.g. Dijkstra’s shortest paths) as well as linear algebra (e.g. linear systems, eigenvalues and eigenvectors) and probability (Markov chains).

Books and reading materials

The following book is highly recommended. I’m currently searching for other books that may be useful as well.

• Network Analysis, Methodological Foundations. Ulrik Brandes and Thomas Erlebach (Eds.) This should be available from the following doi: http://dx.doi.org/10.1007/b106453

More details coming soon…

Please email dgleich–a-t–purdue.edu me for details!

This class will most likely involve reading, discussing, and presenting research papers. It will also likely involve a project.</p>