CSE 112
Networked Life
Spring 2005
Tuesdays and Thursdays 12-1:30 PM, Levine Hall 101

Prof. Michael Kearns

NOTICE: Networked Life has just been approved to be added to the list of courses satisfying the College of Arts and Sciences' Quantitative Data Analysis Requirement, effective this term.


How does Google find what you're looking for? Why do real estate values rise or plummet in certain neighborhoods? Do people act rationally in economic and financial settings? Are you really only six friends away from Kevin Bacon? (And do you want to be?) How does the stock market actually work? What might we mean by the economics of spam? What do game theory and the Paris subway have to do with Internet routing?

Networked Life looks at how is our world is connected -- socially, economically, and technologically -- and why it matters.

The answers to the questions above are related. They have been the subject of a fascinating intersection of disciplines including computer science, physics, psychology, economics and finance. Researchers from these areas all strive to quantify and explain the growing complexity and connections of the world around us, and they have begun to develop a rich new science along the way.

Networked Life will explore recent scientific efforts to explain social, economic and technological structures -- and the way these structures interact -- on many different scales, from the behavior of individuals or small groups to that of complex networks such as the Internet and global economy.

This course covers computer science topics and other material that is mathematical, but all material will be presented in a way that is accessible to an educated audience with or without a strong technical background. The course is open to all majors and all levels.

Networked Life was first offered in Spring 2004. You can visit the extensive web page from Spring 2004. This year the course will cover similar topics, but we'll do more in-class exercises and social experiments, and will cover more finance and Internet material toward the end.


Prof. Michael Kearns
Levine Hall 509
Office hours: Wednesdays 10-12


Nikhil Dinesh
Office hours: Fridays 12-2, in Levine 506

Elliot Feng
Office hours: Tuesdays and Thursdays, 1:30-2:30, in Room 401A of IRCS (3401 Walnut; elevator bank through doors next to Starbucks)


Attendance at the main lectures is considered mandatory for enrolled students. They are held Tuesdays and Thursdays 12-1:30, Levine Hall 101.

This year there will be no recitations for Networked Life. The teaching assistants will hold special out-of-class review sessions before exams, and will hold extended office hours before major assignments are due.


Networked Life has no formal prerequisites, and is meant to be accessible to a broad range of students across SEAS, the College, and Wharton. No computer programming background is required, but students should be comfortable using computers and the Web, and accessing resources on the Internet.


The main lectures for Networked Life will be in fairly traditional format, projected in Powerpoint that will always be made available following the lecture (but not necessarily before).

There will be a number of participatory social experiments and exercises. These seemed quite popular last year and will increase this year.

There will also be a number of homework and research assignments. These will include a fair amount of basic quantitative analysis of data, as well as essay questions, computer and web exercises, and other quantitative exercises. Collaboration on the homeworks is not permitted.

There will be a midterm, and a final exam.

It is anticipated that the participatory experiments, homeworks, midterm and final will each count for approximately a quarter of the overall grade.

Students are encouraged to bring articles, demos, web pages, news events, etc. that are relevant to course topics to the attention of Prof. Kearns. Extra credit will be given if the suggested material is used in the course.


All students must have reliable access to web and Internet resources, as well as be reachable via email in a timely fashion. For these purposes, any student in the course may obtain an account on the server Eniac if they so desire, if they do not already have one. Sign up for an Eniac account here.

All students enrolled in CSE 112 have access to the School of Engineering and Applied Sciences computer labs. We will test all the software that you are required to use on Windows computers using Internet Explorer. This software is generally written in Java and may work on other platforms, but we cannot guarantee it.

PC Labs can be found in:
Towne M62   Towne M70   Towne 142   Towne 143   Towne 144
More information on the labs is online.

You will need to print and turn in materials, and you may not be able to your all your printing in the SEAS labs. For a fee, you can print longer documents at the SEAS library on the 2nd floor of Towne. Of course, you can also print on your own printer or elsewhere where you have access to a printer.


The following three books, all in paperback and on order at the Penn Book Store, are required texts for the course:

  • The Tipping Point, by Malcolm Gladwell. Paperback. Little Brown & Company, 2000.
  • Six Degrees: The Science of a Connected Age, by Duncan J. Watts. Paperback. W.W. Norton, 2003.
  • Micromotives and Macrobehavior, by Thomas C. Schelling. Paperback. W.W. Norton, 1978.

    In addition to readings from these texts, there will be frequent articles from the recent scientific and popular literature that will be provided directly on this web page at the appropriate points in the syllabus.


    We have created our own online social network Lifester, which will be used for a variety of participatory course experiments. See the course schedule below for more details.

    Also, Prof. Kearns has accounts on a number of commercial social network services, and welcomes anyone who is interested to send him mail to add links to him on those services. We may also use these services to periodically demonstrate principles from the course.

  • On thefacebook Prof. Kearns' username is mkearns@cis.upenn.edu.
  • On Friendster Prof. Kearns' username is kearnsmichael@hotmail.com.
  • On Orkut Prof. Kearns' username is mkearns.


    Except for occasional hard-copy handouts distributed in lectures, all of the material for the course will be posted in the table below, which will be gradually filled in as we progress through the students. Lecture slides, reading and homework assignments, due dates, exam information, etc. will all be provided below. It is every student's responsibility to monitor this schedule closely and regularly.

    In the assigned readings below, "Gladwell", "Watts" and "Schelling" refer to the three required texts cited above. Other readings will be directly provided as links to PDF documents. Unless specified otherwise, you should generally try to complete the assigned reading during roughly the period spanned by the dates given in the same row of the table.

    The lecture slides are all in PowerPoint format, but they may often contain links to documents in other formats, including PDF, Postscript, JPEG, etc. In order to view all of the linked content you may need to be using a computer with viewers installed for these formats.

    Tu Jan 11 Course Introduction and Overview To get an early sense of just a few of the course themes, read pages 37 -- 39 of the recent article "Economics, Computer Science, and Policy" by Prof. Kearns. We will return to examine the latter material on interdependent security in the middle of the term. At the start of the first lecture, Prof. Kearns will ask for two volunteers from the class. Together the two will split 20 dollars in cash, awarded on the spot.

    Also in the first lecture, Prof. Kearns will distribute a hard-copy document containing a brief background survey and our first communal social experiment. These should be returned at the start of the next lecture (Th Jan 13).

    Th Jan 13; Tu Jan 18; Th Jan 20 The Networked Nature of Society Read Gladwell, Introduction and Chapters 1 and 2.

    A due date of the start of lecture, Thu Jan 27, has been set for turning in a write-up for Task 1 of the Network Construction and Analysis Project. Please see that page for details; Prof. Kearns will also elaborate in class on Thu Jan 20. Note added 1/24: Towards the bottom of Task 1, some tips on finding and extracting data sources have been added.

    Also on Thu Jan 20, Prof. Kearns will introduce our course social networking service Lifester. As described, you must complete Lifester Task 1 online by 6 PM on Tue, Jan 25.

    Turn in your background survey and last-name experiment as you enter lecture on Jan 13. We will analyze the results of the latter on the fly in class.

    Prof. Kearns will discuss the Network Construction and Analysis Project at some point during these lectures.

    Thanks to course participant Will Frank for proposing this Networked Life course theme song, for which you can read the lyrics here. Apparently we may conclude that Roger Daltrey is not a connector. Historical Note: Archaeological evidence indicates that "The Who" were a popular rock band that was prominent in the approximate period between the Second Great War and the first term of American president William Jefferson Clinton. During a previous lifetime, Prof. Kearns attended not just one but two "farewell concerts" held by this band in ancient coliseums.

    Tu Jan 25; Th Jan 27; Tu Feb 1 Contagion, Tipping and Networks Read Gladwell, Chapters 4 and 5.

    Read ``An Experimental Study of the Small World Problem'', by J. Travers and S. Milgram.

    Read ``An Experimental Study of Search in Global Social Networks'', by P. Dodds, R. Muhamad, and D. Watts.

    Remember that you should print out, review, and bring to class Tue Feb 1 the profiles of all of your Lifester neighbors. You will need them for an in-class experiment.

    These lectures will be largely but loosely based on topics raised in The Tipping Point, as well as some related writings.

    Here are two interesting but unassigned readings: A quite recent New York Times Magazine article on word-of-mouth advertising, and an Internet Retailer article on the use of social networks for online marketing. Thanks to course participant Katy Keenan for pointing out the latter. Keep 'em coming!

    Th Feb 3 The Language of Networks: A Painless Introduction to Graph Theory The date of the midterm will be Thursday, March 3. I recently became aware of this diagram detailing the network of Wall Street scandals. Though the definition of the vertices and especially edges is a bit less formal than we'd like, it's still pretty interesting.
    Tu Feb 8; Th Feb 10; Tu Feb 15; Th Feb 17; Social Network Theory Read Watts, Chapters 2 through 5.

    As described in class on Feb 8, revisions to Task 1 of the Network Construction Project will be accepted on Thursday, Feb 10.

    On Tue Feb 15, class will be devoted to mandatory collective experiments using the Lifester network. Everyone should print out the profiles of the Lifester neighbors and bring them to class that day. Also, please read and make sure you understand the description of all three experiments below before coming to class.
    The Rules
    Lifester Coloring Experiment
    Lifester Matching Experiment
    Lifester Independent Set Experiment
    The results and analysis of these experiments can be found in the Powerpoint deck to the left. Overall the results were quite interesting, as the class did an excellent job at the collective optimizations.

    New assignment (posted Feb 17): At the start of class on Tue Feb 22, you should turn in a brief (1-2 page) description of the kinds of discussions and interactions you had with your Lifester neighbors during the Feb 15 in-class experiments. Please divide the document into the three experiments (coloring, matching, and independent set), and feel free to also make observations on the behavior of your neighbors and the class as a whole.

    Network Construction Project Task 2, in which you actually execute the precise methodology you described in Task 1, will be due by email by midnight, Tuesday, March 1. See the project page for more details.

    Reminder: the midterm will be Thu Mar 3. A good way of preparing for the exam is to work through Homeworks One and Two, and the midterm, from last year's course.

    On Friday Feb 11 there is a talk by Duncan Watts (3620 Walnut, Room 110, Annenberg School) that I strongly recommend. Extra credit will be given to anyone who attends this talk and turns in a brief (1 page) analysis of how Watts' talk relates to themes discussed in Gladwell.

    Here are some incredibly cool visualizations of blog networks discovered by Field Agent Priscilla Spencer. They are a bit slow to download, but worth the wait.
    [One] [Two] [Three] [Four]

    On Friday Feb at noon there will be another great outside speaker --- Colin Camerer of Caltech will speak on behavioral game theory, a topic we will be studying later in the term. Details about the talk can be found here . As with the Watts talk, extra credit will be given to anyone who attends the talk and writes a brief (1 page) report on it.

    Tu Mar 15; Th Mar 17 The Web as Network Read ``Graph Structure in the Web'', by A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopolan, R. Stata, A. Tomkins, J. Weiner.

    Read ``The PageRank Citation Ranking: Bringing Order to the Web'', by L. Page, S. Brin, R. Motwani, T. Winograd.

    The midterms will be returned in class on March 15. The average was 71, the standard deviation was 13, the high score was 94, and the low score was 32. A histogram of the scores can be found here.
    Th Mar 17; Tu Mar 22 Local Incentives and Global Outcomes

    Strategic Dynamics: Introduction to Game Theory

    Read Schelling, Chapters 1, 3 and 4.

    The main assignment for the remainder of the term will be a final report (probably around 10 pages long) for the Network Construction Project, in which you analyze your network in light of the themes of the class. More detail will be provided shortly. In the meantime, here is a directory containing visualizations of your networks. It is organized by last name. In the immediate term, you should make sure there are visualizations of your network there; if not, contact Prof. Kearns by email immediately.

    Here is an amusing site on PigeonRank from Field Agent Brian Hertler.

    On Monday Mar 28 at 4:30 PM in the Levine Auditorium, Prof. Kearns will give this talk, which is designed for a general audience and is directly related to course themes. No extra credit this time, as this would be just too self-serving. But you can get a head start on some of the topics we'll be covering soon by attending. Plus, free food afterwards!

    Tu Mar 29 Networks and Interdependent Security Games Read "Economics, Computer Science, and Policy" in its entirety.
    Th Mar 31; Tu Apr 5 Exchange Economies and Networks Further details about your final reports for the Network Construction project can be found here. This material will be updated as more details are settled.

    A number of you have expressed interest in being able to generate and manipulate visualizations of your networks directly. Here is a link to page for graphviz, the software we have been using to generate network images. It is extensively documented there and available for download for a variety of operating systems. The graphviz program is also installed on the SEAS server minus.seas.upenn.edu; in addition to the documentation at the link above, you can type "man dot" and "man neato" on minus to learn how to use it.

    IMPORTANT NOTICE: The final exam will be held on Friday, May 6, from 11-1 in Moore 216 (NOTE UNUSUAL ROOM!).

    The following talk on Thursday, April 7 is only peripherally related to course themes, but looks like it should be interesting.
    Th Apr 7 NO CLASS

    Tu Apr 12 In-class experiments During this class session, we will run experiments in exchange markets on networks. Participation is mandatory and for course credit. Detailed instructions are available here.
    Th Apr 14 How Do People Really Act?: Behavioral Game Theory As discussed briefly last week in class, the final reports for the Network Construction Project will be due in hardcopy form at the final exam on Friday May 6 at 11 AM. We seem to be blessed with course-relevant lectures on campus this term. "Micromotives and Macrobehavior" author Thomas Schelling speaks on Thursday, April 14 at 4 PM in Logan 17, followed by a reception. The title of his talk is "Rational Choice and Some of its Alternatives" and is described here. As usual, extra credit will be given to any student who attends and writes a brief report.
    Tu Apr 19; Th Apr 21 The Economics of the Internet At the end of class on Tu Apr 19 (and for missing parties, on Th Apr 21), time will be allowed for the completion of course review forms. Please take the time to fill one out and provide feedback, which is taken seriously.

    REMINDER: The final exam will be held on Friday, May 6, from 11-1 in Moore 216.

    There will be a review session for the final exam led by Prof. Kearns on Friday, April 29 at noon in the Levine Auditorium.

    We close with a couple of links to items of local interest: The very cool buzztracker, the senior design project of Penn DMD student Craig Modzelesky; and a DP article about NW Life student Michael Highland's acclaimed autobiographical film on video-game addiction. Good Luck on the exam to all of you, and have a terrific summer!


    This area contains links to web pages, demos, articles, etc. that are related to course topics. Suggestions for additions are welcome.

  • The extensive and fascinating Erdos Number Project, one of the earliest organized social network studies
  • The Complex Human Networks Reading Group at the MIT Media Lab
  • The home page of Prof. Jon Kleinberg at Cornell and a link to a related course that he teaches
  • Link to a related course of Prof. Duncan Watts of Columbia
  • Papers by Andrew Odlyzko
  • Small World Project at Columbia
  • Sangkyum Kim's very useful collection of readings in social network theory
  • The very cool Atlas of Cyberspaces by Martin Dodge and Rob Kitchin
  • The TouchGraph browsers for visualizing content networks
  • The Dartmouth Segregation Simulator
  • The Social Explorer