MS&E 235: Network Analytics

 

Instructor: Amin Saberi
Huang Engineering Center, #309

saberi@stanford.edu

(650) 704-7857

Time: Tuesday-Thursday 3-4:20PM

Location: Building 380-Room 380F

Amins 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

 

Course Description

The course explores the underlying network structure of our social, economic, and technological worlds and uses techniques from graph theory, probability, and economics to examine phenomena such as social contagion, social power and popularity, and information cascades.

Textbook  

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.

 

 

Course Outline

      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: Kleinbergs 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-Saberis  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: Saberis 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. VaziraniAdwords 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

 

 

Course load and Grading

o   Due Dates: Jan 25, Feb 8, March 1, and March 8)

 

Team projects

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.