Instructor: Amin Saberi
Huang Engineering Center, #309
(650) 704-7857
Time: Tuesday-Thursday 3-4:20PM
Location: Building 380-Room 380F
AminÕs Office hours: Tuesdays/Thursdays 10:30 Ð 11:30
Course Assistants:
Olivier Pham (mdopham@stanford.edu) and Ben Zhou (benzhou@stanford.edu)
Office hours: Monday 3-4:30, Wednesday 9-10:30, or by appointment
We will cover a few chapters from Networks,
Crowds, and Markets by Easley and Kleinberg as well as Mining
Massive Datasets by Jure Leskovec, Anand Rajaraman, and Jeff Ullman.
The former has a stronger emphasis on modeling and the latter on data. This
course will try to cover both.
Chapters 7-10 of Mining Massive Datasets by Jure Leskovec, Anand Rajaraman, and Jeff Ullman will also be covered. But our treatment of the material will be more mathematical. We will cover chapters 19-21 as well as 9-12.
Both books are available online.
á
Lecture 1: Overview of the
class
(slides)
á Lecture 2: Erdos-Renyi graphs
o
Optional reading: connectivity and diameter
á
Lecture 3: Power-laws,
preferential attachment (slides)
o Text
book: Chapter 18 of EK.
á Lecture 4: Small world networks (slides)
o
Text book: Chapter 20 of EK
o Optional
reading: KleinbergÕs papers Navigation in a Small
World.(Nature 2000) and The small-world
phenomenon: An algorithmic perspective. (STOC 2000.)
á Lecture 5: Spread of innovations in social networks (slides)
o
Text book: Chapters 19 &
21 of EK
o Optional
reading: Montanari-SaberiÕs The Spread of
Innovations in Social Networks, in (Proc. of the National Academy of
Sciences 2009).
á
Lectures 6 & 7: Mining
social network data (slides)
o Text
book: Chapter 10 of LRU
o
Optional reading: SaberiÕs PhD course on Spectral Graph Theory
á
Lecture 9: Recommendation
systems (slides)
o Text
book: Chapter 11 of LRU
á
Midterm on February 8th
(covering chapters 18-21 of EK and 9 and 10 of LRU)
á Lectures 10-13: Auction design (slides)
and online advertising (slides 1,
2,
3)
o Chapters
9 and 15 of EK and chapter 10 of LRU
o Optional
Reading: A. Mehta, A. Saberi, U. Vazirani,
V. Vazirani, Adwords
and Generalized On-line Matching , Journal of the ACM (2007) as
well as A. Mehta, Online
Matching and Ad Allocation, 2012.
o
Industry speaker (Feb 27): Aranyak Mehta (Google)
á Lectures 14-15: Two sided markets and the
sharing economy (slides)
o Chapters
10-12 of EK
o
Industry speaker (March 6):
Hamid Nazerzadeh (Uber)
á Midterm on March 13th
á
Student presentations on
March 15th
o Due Dates: Jan 25, Feb 8, March 1, and March 8)
For your final project, you are expected to form teams of size 2-3. The general theme for the projects is using network data for a novel application.
You are expected to turn in an interim and a final report, and if time allows give a short presentation in the class.