# Class meeting for 10-605 Subsampling a Graph

From Cohen Courses

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

## Contents

### Slides

### Quiz

### Readings

- Samping from Large Graphs, Jure Leskovec and Christos Faloutsos, KDD 2006.
- Local Graph Partitioning using PageRank Vectors, Andersen, Chung, Lang, FOCS 2006

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.