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

Week 1:course overview; introduction to networks

14 September 2009 (M): 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.

PS01 was handed out in class. It's due on Wednesday, 16 September, at the beginning of class.
16 September 2009 (W): questions about networks; the CS worldview; algorithms; making change.
Reading: Easley–Kleinberg, §2.1, 3.1, 4.1–4.2.

PS02 was handed out in class. It's due on ~~Friday, 18 September~~ Monday, 21 September, at the beginning of class.
18 September 2009 (F): network definitions; triangles and homophily in social networks.
Reading: Easley–Kleinberg, §2.2, 2.4.

Peter's prefecting, planned perpetually! Place: Leighton 305. Period: Tuesdays and Thursdays, 9:00pm. Per Peter's post, prefecting's premiere performance: September 22, Tuesday, 9:00p. Please participate!

PS03 was handed out in class. It's due on Wednesday, 23 September, at the beginning of class.

Week 2: history of graph theory; algorithms; connectivity

21 September 2009 (M): definitional review, more network definitions, and Eulerian cycles.
Reading:
Leonhard Euler, Solutio Problematis ad Geometriam Situs Pertinentis, 1736. (English translation in Scientific American, July 1953.)

PS04 was handed out in class. It's due on Friday, 25 September, at the beginning of class.
23 September 2009 (W): history of graph theory, Eulerian cycles, and algorithms to find them.
Reading: Wikipedia entry on the seven bridges of Königsberg.

PS05 was handed out in class. It's due on Monday, 28 September, at the beginning of class.
25 September 2009 (F): Greg Marfleet & DLN: structural balance and networks of states.
Reading: Easley—Kleinberg, §5.1–5.3.

PS06 was handed out in class. It's due on Wednesday, 30 September, at the beginning of class.

Week 3: the structure of networks; game theory; the spread of innovation

28 September 2009 (M): catch up: old problem sets, challenges, and questions.
Reading: catch up.

PS07 was handed out in class. It's due on Friday, 2 October, at the beginning of class.
30 September 2009 (W): representing graphs and algorithms in a computer; breadth-first search.
Reading: Easley—Kleinberg, §2.3.
DLN's notes on graph representation and search.

PS08 was handed out in class. It's due on Monday, 5 October, at the beginning of class.
2 October 2009 (F): Nathan Grawe: network externalities and an economic perspective on networks.
Reading: Easley–Kleinberg, §6.1–6.5 and §17.0–17.3. Optionally, read the rest of Chapters 6 and 17.

PS09 was handed out in class. It's due Wednesday.

Week 4: the structure of the web, degree distributions

5 October 2009 (M): connectivity in directed graphs; the web; the structure of the web.
Reading: Vannevar Bush, As We May Think, Atlantic Monthly, July 1945.
Easley—Kleinberg, Chapter 13.

PS10 was handed out in class. It's due Friday.
7 October 2009 (W): the bowtie structure of the web; degree distribution, the JK Wedding Video.
Here is the animation of a giant component forming in a random graph.

Reading: Easley–Kleinberg, §18.1–18.2.

PS11 was handed out in class. It's due Monday.
9 October 2009 (F): prediction markets: birthdays, social security numbers, and Carleton admits.
Reading: Easley–Kleinberg, §22.0–22.5.

PS12 was handed out in class. It's due Wednesday.

Week 5: propagation through networks

12 October 2009 (M): Michael Oakes: epidemiology and public health
Reading: Easley–Kleinberg, §21.1–21.2.

PS13 was handed out in class. It's due Friday.
14 October 2009 (W): degree distributions, power laws, sex surveys, preferential attachment models.
Reading: Easley–Kleinberg, Chapter 18.
G. Kolata. The Myth, The Math, the Sex. New York Times, 12 August 2007.
16 October 2009 (F): wisdom (?) of crowds
Here's the "rich get richer" preferential attachment model that shows a power-law degree-distribution forming.

DLN will hold a review session for the midterm on Monday, in CMC 206. We'll start at 7:00p and go until either midnight or whenever you run out of questions to ask, whichever happens first.

Reading: Easley–Kleinberg §16.1, 16.2, 16.7, 18.4, 19.6
James Surowiecki, "Francis Galton’s Ox" (an excerpt from The Wisdom of Crowds, 2004.)

Week 6: midterm; weighted graphs

19 October 2009 (M): midterm break!
21 October 2009 (W): midterm!
23 October 2009 (F): weighted graphs and Dijkstra's algorithm
Reading: DLN's notes on Dijkstra's algorithm.

PS14 was handed out in class today. It's due on Wednesday.
PS15 was handed out in class today (attached to PS14). It's due on Friday.

Week 7: the internet; more on propagation through networks

26 October 2009 (M): Jeff Ondich: how the internet works
28 October 2009 (W): Dijkstra's algorithm, more on the internet, and Milgram's small world experiment.
Reading: Easley–Kleinberg, Chapter 20.

The final project announcement was handed out today. A topic proposal is due on Friday, 6 November 2009.
The project itself is due on the last day of classes.
30 October 2009 (F): Debby Walser-Kuntz & DLN (joint meeting with Biol 370): viruses and their spread
The simulations from LiveJournal are posted in our courses directory.

PS16 was handed out in class today. It's due on Wednesday.

Week 8: search and power in networks

2 November 2009 (M): Milgram; G_n,p random graphs; the Watts—Strogatz model.
Reading: Easley–Kleinberg, Chapter 20 (except actually read it this time).

Complete the "vote for a class representative" form by 8:00a Tuesday.
4 November 2009 (W): Kleinberg's small-world model; power in networks.
Reading: Easley–Kleinberg, §3.2—3.4.

Reminder: your project proposal is due on Friday.
6 November 2009 (F): measures of betweenness (degree, closeness, betweenness, Katz); random walks.
PS17 was handed out today. It's due Wednesday.

Week 9: power in networks; how web search works; kidney transplants

9 November 2009 (M): a brief Yiddish lesson (abi gezunt, genug shoyn, bupkis), random walks, and PageRank.
Reading: Easley—Kleinberg, Chapter 14.
11 November 2009 (W): Lauren Feiler & DLN (joint meeting with Econ 266): network exchange theory (countdown timer)
Reading: Easley—Kleinberg, Chapter 12.
13 November 2009 (F): wrapup of power in networks (PageRank, network exchange); kidney transplants.
Reading: handout on stationary distributions in random walks.
D. Abraham, A. Blum, T. Sandholm. Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. EC'07. (Abstract, §1,7,8.)
A. Roth, T. Sönmez, M. Ünver. Kidney Exchange. Quarterly J. of Economics, May 2004. (§I,IIa,V only.)

Week 10: road networks and selfishness; course wrapup

16 November 2009 (M): routing, selfish routing, and Braess's Paradox.
Reading:Easley—Kleinberg Chapter 8.

DLN will hold a review session for the final on Friday, in CMC 206. We'll start at 9:00a and go until either a little before noon or whenever you run out of questions to ask, whichever happens first.
18 November 2009 (W): course wrapup; ask me anything.