Difference between revisions of "Class meeting for 10-605 Scalable PageRank"
From Cohen Courses
Jump to navigationJump to search (→Slides) |
|||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | This is one of the class meetings on the [[Syllabus for Machine Learning with Large Datasets 10-605 in Fall | + | This is one of the class meetings on the [[Syllabus for Machine Learning with Large Datasets 10-605 in Fall 2016|schedule]] for the course [[Machine Learning with Large Datasets 10-605 in Fall_2016]]. |
=== Slides === | === Slides === | ||
| Line 7: | Line 7: | ||
* [http://www.cs.cmu.edu/~wcohen/10-605/pagerank.pptx PageRank and Scalability], [http://www.cs.cmu.edu/~wcohen/10-605/pagerank.pdf PDF version] | * [http://www.cs.cmu.edu/~wcohen/10-605/pagerank.pptx PageRank and Scalability], [http://www.cs.cmu.edu/~wcohen/10-605/pagerank.pdf PDF version] | ||
* [http://www.cs.cmu.edu/~wcohen/10-605/rwr-sampling.pptx Sampling from a Graph], [http://www.cs.cmu.edu/~wcohen/10-605/rwr-sampling.pdf PDF version] | * [http://www.cs.cmu.edu/~wcohen/10-605/rwr-sampling.pptx Sampling from a Graph], [http://www.cs.cmu.edu/~wcohen/10-605/rwr-sampling.pdf PDF version] | ||
| − | |||
| − | |||
=== Quiz === | === Quiz === | ||
| − | * | + | * [https://qna-app.appspot.com/view.html?aglzfnFuYS1hcHByGQsSDFF1ZXN0aW9uTGlzdBiAgICgjtDJCAw [https://qna-app.appspot.com/view.html?aglzfnFuYS1hcHByGQsSDFF1ZXN0aW9uTGlzdBiAgICgjtDJCAw]] |
=== Readings === | === Readings === | ||
| Line 18: | Line 16: | ||
* [http://dl.acm.org/citation.cfm?id=1150479 Samping from Large Graphs], Jure Leskovec and Christos Faloutsos, KDD 2006. | * [http://dl.acm.org/citation.cfm?id=1150479 Samping from Large Graphs], Jure Leskovec and Christos Faloutsos, KDD 2006. | ||
* [http://www.math.ucsd.edu/~fan/wp/localpartition.pdf Local Graph Partitioning using PageRank Vectors], Andersen, Chung, Lang, FOCS 2006 | * [http://www.math.ucsd.edu/~fan/wp/localpartition.pdf Local Graph Partitioning using PageRank Vectors], Andersen, Chung, Lang, FOCS 2006 | ||
| + | * [http://link.springer.com/chapter/10.1007/978-3-540-77004-6_13#page-1 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. | ||
Latest revision as of 13:31, 10 August 2016
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
- 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
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.
