The aim of this project is to analyze the structure of a large existing web graph such as Wikipedia with roughly $N = 6$ million nodes and $E = 200$ million edges. Spectral algorithms exist for such tasks, but their runtime $O(N^3)$ is prohibitive for the above application. Various methods have been developed for tackling this issue. We aim at studying and implementing some of these.
Prerequisites for this project
good programming skills!
olivier.leveque#epfl.ch (LTHI), pierre.vandergheynst#epfl.ch (LTS2