CS108 (Life in the Age of Networks) Fall 2011, Carleton College

Week 1: course overview; introduction to networks

13 September 2011 (T): introduction to networks; course logistics.
The images from class are from here, here, here, here, here, here, here, here, here, here, and here.

Reading: Easley–Kleinberg, Chapter 1, §2.1, §3.1.

PS01 was handed out in class. It's due on Thursday, 15 September, at the beginning of class.
15 September 2011 (R): constructed personal identity in social media, graph definitions, homophily, friend wheels.
Reading: Easley–Kleinberg, §2.2, §2.4, §4.1–4.2.

PS02 is now available on Moodle. It's due, on paper, on Tuesday, 20 September, at the beginning of class.

Week 2: history of graph theory; algorithms

20 September 2011 (T): paths, connectivity, and a brief history of graph theory.
Reading: Leonhard Euler, Solutio Problematis ad Geometriam Situs Pertinentis, 1736.
(English translation from Scientific American, July 1953, posted in Moodle.)

PS03 is now available on Moodle. It's due, on paper, on Thursday, 22 September, at the beginning of class.
22 September 2011 (R): (with Greg Marfleet) Eulerian paths, algorithms, & applications; structural balance, networks of states.
Reading: Easley–Kleinberg, §5.1–5.4; Wikipedia entry on the seven bridges of Königsberg.
You can find Greg's Prezi here.

PS04 is now available on Moodle. It's due, on paper, on Tuesday, 27 September, at the beginning of class.

Week 3: the structure of networks

27 September 2011 (T): definitional challenges, structural balance; pop quiz on graph definitions
Reading: Easley–Kleinberg, §2.3; DLN's notes on graph representation and search, posted in Moodle.

PS05 is now available on Moodle. It's due on Thursday, 29 September, at the beginning of class.
29 September 2011 (R): PS05 debrief: average distance and diameters; breadth-first search.
Reading: Nothing new.

PS06 is now available on Moodle. It's due on Tuesday, 4 October, at the beginning of class.

I will accept revisions of PS05 until Tuesday, 4 October, at the beginning of class.

Week 4: the spread of innovation; prelim #1

4 October 2011 (T): Nathan Grawe: network externalities. DLN: representating graphs and algorithms; breadth-first search.
Reading: Vannevar Bush, As We May Think, Atlantic Monthly, July 1945.
You can find Nathan's powerpoint on Moodle.
6 October 2011 (R): prelim #1
PS07 is now available on Moodle. It's due on Tuesday, 11 October, at the beginning of class.

Week 5: structure of the web

Week 6: information aggregation; weighted graphs

18 October 2011 (T): prediction markets and the wisdom of crowds.
Reading: Easley–Kleinberg, §16.1, 16.2, 16.6, 16.7; §22.0, 22.1, 22.4

PS10 is now available on Moodle. It's due on Thursday, 22 October, at the beginning of class.
20 October 2011 (R): logarithms, power laws, rich-get-richer, and aggregation of opinion.
Reading: Easley–Kleinberg, Chapter 18 (review).
M. Salganik, P. Dodds, D. Watts. Experimental Study of Inequality and Unpredictability in an Artificial Cultural Market, Science, 2006.

PS11 is now available on Moodle. It's due on Tuesday, 27 October, at the beginning of class.

Week 7: searching networks

25 October 2011 (T): rich get richer, power laws, Yule's law; weighted graphs.
Reading: DLN's notes on Dijkstra's algorithm (in Moodle)
Start reading Easley–Kleinberg, Chapter 20.
Optionally: R. Albert, H. Jeong, A-L. Barabasi. Error and attack tolerance of complex networks, Nature, 2000.

PS12 is now available on Moodle. It's due on Thursday, ~~29 October~~ 27 October (sorry for the typo), at the beginning of class.

The final project announcement is now available on Moodle. A topic proposal is due on Tuesday, 1 November 2011.
The project itself is due on the last day of classes.
27 October 2011 (R): Dijkstra's algorithm; small-world phenomenon.
Reading: Easley–Kleinberg, Chapter 20.

Week 8: diffusion in networks; prelim #2

1 November 2011 (T): Amy Saupe and Glenise Johnson (MN Department of Health): epidemiology.
Reading: Easley–Kleinberg, §21.0–21.3; skim the rest of Chapter 21 (particularly §21.6).
You can find Amy and Glenice's powerpoints on Moodle.
3 November 2011 (R): prelim #2

Week 9: power in networks; the internet

8 November 2011 (T): small worlds wrapup; measures of centrality in networks.
PS13 is now available on Moodle. It's due on Thursday, 10 November at the beginning of class.

Reading: Easley–Kleinberg, §3.2–3.5; §12.1–12.3; start §14.1–14.5.
One-page random walks reading posted to Moodle.
10 November 2011 (R): Jeff Ondich: how the internet works; DLN: random walks and pagerank.
Reading: finish Easley–Kleinberg, §14.1–14.5, and the one-page random walks reading posted to Moodle.

Week 10: course wrapup

15 November 2011 (T): Melissa Eblen-Zayas and selfish routing; ask me anything.

Reading: If you're interested in learning more about selfish routing, see Chapter 8 of Easley–Kleinberg.