Difference between revisions of "Class meeting for 10-605 Subsampling a Graph"
From Cohen Courses
Jump to navigationJump to search (→Slides) |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 3: | Line 3: | ||
=== Slides === | === Slides === | ||
− | * [http://www.cs.cmu.edu/~wcohen/10-605/sampling-a-graph.pptx Powerpoint] | + | * [http://www.cs.cmu.edu/~wcohen/10-605/2016/sampling-a-graph.pptx Powerpoint], [http://www.cs.cmu.edu/~wcohen/10-605/2016/sampling-a-graph.pdf PDF] |
+ | |||
+ | === Quiz === | ||
+ | |||
+ | * [https://qna.cs.cmu.edu/#/pages/view/69 Today's quiz] | ||
=== Readings === | === Readings === |
Latest revision as of 16:44, 1 August 2017
This 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.