Today we’ll finish our kickoff exploration of graphs and move on to one or the other of the fun notes on the most “influential” node in a directed graph (AKA the Google Guide to How to Win at Search), and how to cluster nodes in an undirected graph (if an edge’s weight denotes similarity)?
- Here are the very brief “influential node” notes.
- Here are the clustering notes. (In case you’re wondering why you’re reading Chapter 4 and we’re still talking about graphs… these are also greedy algorithm notes! Graphs make an awesome domain for just about any algorithm.)
- Assignment #2 will be posted at 5PM and due Fri 3 Feb at 10PM on GradeScope. Be sure to indicate your whole group using GradeScope’s interface (not just by including the GradeScope login in your submission).
- For next time, please read Sections 4.1-4.2. (No pre-class quiz; the next one is due on Thursday 2 Feb.)
- Just for fun: Our algorithm isn’t Google’s, but it computes the same PageRank quantity.
- Just for fun: UBC CS’s most cited paper (last we checked!), by David Lowe, looks at how to find similar features between images using the SIFT algorithm.