Class meeting for 10-605 Scalable PageRank

This is one of the class meetings on the schedule for the course Machine Learning with Large Datasets 10-605 in Fall_2016.

Slides

• Randomized Algorithms wrap-up, Randomized Algorithms PDF version.
• Tips on Debugging for the SGD Assignment,PDF version
• PageRank and Scalability, PDF version
• Sampling from a Graph, PDF version

Quiz

• [https://qna-app.appspot.com/view.html?aglzfnFuYS1hcHByGQsSDFF1ZXN0aW9uTGlzdBiAgICgjtDJCAw]

Readings

• Samping from Large Graphs, Jure Leskovec and Christos Faloutsos, KDD 2006.
• Local Graph Partitioning using PageRank Vectors, Andersen, Chung, Lang, FOCS 2006
• Andersen, Reid, Fan Chung, and Kevin Lang. "Local partitioning for directed graphs using PageRank." Algorithms and Models for the Web-Graph. Springer Berlin Heidelberg, 2007. 166-178.

Key things to remember

• How to implement graph algorithms like PageRank by streaming through a graph, under various conditions:
  • Vertex weights fit in memory
  • Vertex weights do not fit in memory
• The meaning of various graph statistics: degree distribution, clustering coefficient, ...
• Why sampling from a graph is non-trivial if you want to preserve properties of the graph like
  • Degree distribution
  • Homophily as measured by clustering coefficient,
• What local graph partitioning is and how the PageRank-Nibble algorithm, together with sweeps to optimize conductance, can be used to approximately solve it.
• The implications of the analysis of PageRank-Nibble.