Class meeting for 10-605 Subsampling a Graph

From Cohen Courses
Jump to navigationJump to search

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

Slides

Quiz

Readings

Optional:

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.