Schedule of the class:

Welcome to the class:

Part I - Structure:


First topic: Connect

How the friendship we form connect us?
Why we are within a few clicks on Facebook?

Tuesday, Sep. 6th
Connect (1/4): The small world effect and experiment

Thursday, Sep. 8th
Connect (2/4):
Milgram's experiment, and its combinatorial analysis

Tuesday, Sep. 13th
Connect (3/4): Proof completion of Random graph, Complex networks

Thursday, Sep. 15th
Connect (4/4): Small world Navigation

Tuesday, Sep. 20th
Connect (bonus): Proof of small world navigation


Additional documents:
Handouts: complete proof of small world navigation (to use as a companion to the assignment)


=> Homework 1: random graphs, connectivity and small world (due on Sep.27th immediately BEFORE the class)


Second topic: Scale

Thursday, Sep. 22nd
Structure - Scale (1/2): skewness, power law, long tail

Tuesday, Sep. 27th
Structure - Scale (2/2): generative models


=> Handouts 2: proof of power law emergence from reinforcement (to use as a companion to the assignment)

=> Homework 2: reinforcement and elementary statistics (due on Oct 6th, immediately before the class)



Third topic: Join and Time-Space


Thursday, Sep. 29th
Structure - Time (Evolution of networks)

Tuesday, Oct. 4th
Structure - Final words on Scale + Time

Thursday, Oct. 6th
Structure - Revisions

Tuesday, Oct. 11th
Join (Groups in social networks)


=> Homework 3: Evolution (due on Oct. 13th, just before class)


Thursday, Oct. 13th - Midterm


Part II - Dynamics



Tuesday, Oct. 18th
Cascade - Infect (continuous model)

Thursday, Oct. 20th
Cascade - Infect (Adjacency Matrix, SI, SIR)

Tuesday, Oct. 25th
Cascade - Infect (the SIS model)

Thursday, Oct. 27nd
Cascade - Infect (end of epidemic algorithms


=> Homework 4: Infect (due on Nov. 1st, just before class)

Tuesday, Nov. 1st
Cascade - Influence (threshold model, deterministic)

Thursday, Nov. 10th
Cascade - Influence (threshold model on graph)

Tuesday, Nov. 15th*
Cascade - Influence (controlling)

Thursday, Nov. 17nd
Cascade - Influence (controlling)


=> Homework 5: Influence (due on Nov. 29th, just before class)

Part III - Applications


Tuesday, Nov. 22nd Applications - importance ranking and Crawling


Tuesday, Nov. 29th Applications - Classify (collaborative filtering)

Thursday, Dec. 1st Applications - Classify (proof + more on recommendations)



Tuesday, Dec. 6th - Applications - Introduction to Security (Sybil attacks)


Thursday, Dec. 8th 1:30 - 2:30pm - Seminar from Giorgos Zervas on:
Daily Deals: Prediction, Social Diffusion, and Reputational Ramiļ¬cations [arXiv]
John Byers, Michael Mitzenmacher, Georgios Zervas
To appear in Proceedings of the 5th ACM International Conference on Web Search and Data Mining (WSDM) 2012
Slides:


Final exam: Monday, Dec. 19th (9am - 12pm) Room to be announced.

*: class with an asterisk indicates the ones that will be either rescheduled or recorded and available through a video link posted at this date.