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

Week 1: course overview; introduction to networks

10 September 2007 (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:
V. Bush. As We May Think. Atlantic Monthly, July 1945.
Start reading Malcolm Gladwell's The Tipping Point in its entirety. You should finish it by Week #3.

PS0 (the course survey) was distributed in class on Monday. Fill it out and return at the beginning of class on Wednesday. You should also sign up for the course blog (follow the instructions in the syllabus). Also come to class on Wednesday with a list of the movies that you've seen in the theatre in the last year and the number of "friends" you have in Facebook.
12 September 2007 (W): the CS worldview; formal definitions of networks.
Reading:
D. Easley, J. Kleinberg. Course notes on graph theory, 2007.

Sessions with Janara and Anna have been scheduled:
Thursday common time (Anna, Math Skills Center); Thursday 9-10 pm (Janara, location TBA); and Sunday 3-4 pm (Janara, location TBA).

The Tipping Point should now be available in the bookstore.

PS1 was distributed in class today. It's due Friday at the beginning of class.

14 September 2007 (F): more network definitions; the history of graph theory.
Reading:
L. Euler. Solutio Problematis ad Geometriam Situs Pertinentis. Scientific American 189:66-70, July 1953. (Translated from the 1736 paper, in Latin.)
Wikipedia entries on the seven bridges of Königsberg and Eulerian paths.

Week 2: connectivity in graphs

17 September 2007 (M): finding Eulerian paths; representations of graphs; algorithms for finding paths in graphs.
Reading:
Notes on graph representation and connectivity.
By Monday, you should have read at least through Chapter 4 of The Tipping Point.

PS2 was distributed in class today. Question #1 is due on Wednesday at the beginning of class; question #2 is due on Monday at the beginning of class.
19 September 2007 (W): (joint meeting with POSC 170, still in Olin 149.) structural balance.
Reading:
D. Easley, J. Kleinberg. Course notes on structural balance, 2007.
21 September 2007 (F): more on representing graphs and searching for paths.
The "is the new" network from class is available here.

Reading:
The Tipping Point, through at least Chapter 4.
Notes on graph representation and connectivity from Monday are now posted here.

Week 3: the spread of disease and innovation

24 September 2007 (M): (Nathan Grawe.) network externalities.
Reading:
Matthew Jackson, Leeat Yariv. Social Networks and the Diffusion of Behavior. Yale Economic Review, 3(2):42--47, 2006.
Keep reading The Tipping Point; you should finish it this week.
26 September 2007 (W): network effects, viral marketing, and a little epidemiology.
Reading:
D. Easley, J. Kleinberg. Course notes on network effects, 2007.

PS3 was distributed today. (There's a copy available in our Courses folder if you didn't get one.) It's due on Friday at the beginning of class.
28 September 2007 (F): more on the spread of innovation, information, and disease
Reading:
D. Easley, J. Kleinberg. Course notes on information cascades, 2007.
F. Liljeros, C. Edling, L. A. N. Amaral, H. E. Stanley, Y. Åberg. The Web of Human Sexual Contacts. Nature 411:907-908, 21 June 2001.

For Monday, think about explanations of the men–women contrast in the data contained in the Nature paper (beyond those mentioned in the paper itself).

Week 4: network effects; communities and clustering

1 October 2007 (M): conditional probability; the truth/plausibility of sex surveys.
Reading:
F. Liljeros, C. Edling, L. A. N. Amaral, H. E. Stanley, Y. Åberg. The Web of Human Sexual Contacts (alternate link).
G. Kolata. The Myth, The Math, the Sex. New York Times, 12 August 2007.

PS4 was distributed today. (There's a copy available in our Courses folder if you didn't get one.) It's due on Monday at the beginning of class.
3 October 2007 (W): prediction markets and power laws.
The Iowa Electronic Markets are here.

Reading:
J. Wolfers, E. Zitzewitz. Prediction Markets. Journal of Economic Perspectives 18(2):107-126, Spring 2004.
(Optional—added 5 October.) J. Surowiecki. Decisions, Decisions. The New Yorker, 24 March 2003.
Wikipedia entry on logarithms, if necessary.
5 October 2007 (F): power laws and rich-get-richer models.
The preferential attachment demo from class is available here.

Reading:
D. Easley, J. Kleinberg. Course notes on power laws, 2007.

Week 5: shortest paths; midterm!

8 October 2007 (M): Schelling segregation model; weighted graphs and shortest paths in weighted graphs.
The Schelling segregation model demo is available here.

PS5 was distributed today. (There's a copy available in our Courses folder if you didn't get one.) It's due on Wednesday at the beginning of class.

Reading:
T. Schelling. Models of segregation. American Economic Review 59(2):488-493, May 1969.
Reread the BFS notes with an eye towards weighted graphs.
10 October 2007 (W): midterm evaluations; review of logs and power laws.
12 October 2007 (F): midterm exam!

Week 6: neural networks and shortest paths

15 October 2007 (M): midterm break!
17 October 2007 (W): (Dave Musicant.) neural networks.
Reading: (for background; don't let yourself get too bogged down in the details.)
O. Sporns, C. Honey. Small worlds inside big brains. PNAS 103(51):19219-19220, 19 December 2006.
D. Bassett, A. Meyer-Lindenberg, S. Achard, T. Duke, E. Bullmore. Adaptive reconfiguration of fractal small-world human brain functional networks. PNAS 103(51):19518-19523, 19 December 2006.
R. O'Reilly. Biologically Based Computational Models of High-Level Cognition Science 314(5796):91--94, 6 October 2006.

Problem Set #6 was distributed today (by Dave). It's due on Monday.
19 October 2007 (F): weighted graphs and shortest paths.
An animation of Dijkstra's algorithm is available here.

Reading:
Notes on Dijkstra's algorithm (posted as dijkstra.pdf in our Courses folder, in Course Materials).

Week 7: small worlds

22 October 2007 (M): the small-world phenomenon.
Reading:
D. Easley, J. Kleinberg. Course notes on small worlds, 2007.

PS7 was distributed today. (There's a copy available in our Courses folder if you didn't get one.) It's due on Monday at the beginning of class.
24 October 2007 (W): small worlds: Watts–Strogatz, Kleinberg.
26 October 2007 (F): small worlds: Kleinberg, LiveJournal.

Week 8: the internet, small worlds, and web search

29 October 2007 (M): (Amy Csizmar Dalal.) the internet.
PS8 was distributed today. (There's a copy available in our Courses folder if you didn't get one.) It's due next Wednesday at the beginning of class.

Reminder: your final project proposal (brief! about half a page) is due on Friday.
31 October 2007 (W): recap of internet routing, rank-based friendship, and the Beatles.
2 November 2007 (F): ranking nodes in networks.
Reading:
J. Kleinberg, S. Lawrence. The Structure of the Web, Science 294:1849, 2001.
S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Hypersearching the Web. Scientific Amer., 1999.
P. Craven. Google's PageRank Explained.

Week 9: assorted applications: PageRank, network exchange theory, organ donation

5 November 2007 (M): random walks and PageRank.
7 November 2007 (W): PageRank and network exchange theory (countdown timer).
Reading:
D. Easley, J. Kleinberg. Course notes on network exchange theory, 2007.
Optional:
L. Story, Facebook Is Marketing Your Brand Preferences (With Your Permission). New York Times, 7 November 2007.
9 November 2007 (F): matchings and perfect matchings; kidney-exchange markets.
Reading:
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: assorted applications; course wrapup

12 November 2007 (M): (with guest star Steve Parker.) kidney exchange wrapup; selfish routing, Braess's paradox.
Reading:
Portions of Algorithmic Game Theory, Nisan, Roughgarden, Tardos, Vazirani, Eds. See the instructions here for access.
¶ T. Roughgarden, E. Tardos. Introduction to the Inefficiency of Equilibria (Chapter 17), through p. 448.
¶ T. Roughgarden. Routing Games (Chapter 18), §18.1, §18.2 (skimming mathematical details), §18.6.
14 November 2007 (W): course wrapup (obesity animation).

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

[Jump to current week]

Basic information:

Announcements:

Course Materials: