The Internet, 1969.
The Internet, 1969.
Network of Enron Scandal Personnel, 2001.
         Network of Enron
      Scandal Personnel, 2001.
High School Sex, 2004.
  High School
   Sex, 2004. 
Behavioral Graph Coloring, 2005.
   Behaviorial Graph
     Coloring, 2005.

CSE 112
NETWORKED LIFE
Spring 2006
Tuesdays and Thursdays 12-1:30 PM, Levine Hall 101
Prof. Michael Kearns


Notes on Curriculum Requirements:

  • Networked Life is one of the courses satisfying the College of Arts and Sciences' Quantitative Data Analysis Requirement.
  • Networked Life is counted as an official Engineering Elective course in SEAS.


    COURSE DESCRIPTION

    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 connectivity 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 the 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.

    Spring 2006 will be the third offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from Spring 2005 and Spring 2004. This year the course will cover similar topics. And new for the Spring 2006 version, we will also engage in a series of communal experiments in distributed human decision-making on networks, and analyze topics such as how network structure influences individual behavior and collective outcomes.


    INSTRUCTOR

    Prof. Michael Kearns
    mkearns@cis.upenn.edu
    Levine Hall 509
    Office hours: This term I will experiment with "on demand" office hours. If you would like to meet, please send me email with your availability. If you are the first one to request a meeting, I will choose a mutually convenient time (usually but not always on either Tue or Thu). If I've already arranged a time with someone else I will try to schedule you immediately before or after.


    TEACHING ASSISTANTS

    Partha Talukdar
    partha@cis.upenn.edu
    Office hours: Monday 4-5 PM in 481 IRCS (3401 Walnut, elevators in lobby next to Starbucks, left and left again out of the elevators on the 4th floor. 481 is through the kitchen.)

    Jenn Wortman
    wortmanj (at) seas dot upenn dot edu
    Office hours: Friday 2-3 in 371 GRW (Take elevavator to 3rd floor Levine, down ramp to GRW.)


    COURSE LOCATIONS AND TIMES

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


    COURSE PREREQUISITES

    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 course is open to all majors and all levels.


    COURSE FORMAT AND REQUIREMENTS

    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.

    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.


    INFORMATION ON ACCESS TO SEAS COMPUTING FACILITIES

    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.


    REQUIRED TEXTS

    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.


    COURSE SCHEDULE

    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, in-class and out-of-class experiments, 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.

    In the "DATES" column of the table below, our current place in the schedule will be highlighted in red.

    DATES SLIDES READING AND ASSIGNMENTS COMMENTS
    Lecture:
    Tu Jan 10
    Course Introduction and Overview
    To get a sense of a few of the course themes, read pages 37 -- 39 of the article "Economics, Computer Science, and Policy" by Prof. Kearns. (We will return to examine the latter material on interdependent security later in the term.)

    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 12).

    Lectures:
    Th Jan 12
    Tu Jan 17
    Th Jan 19
    The Networked Nature of Society Within the first three weeks of class, you should read Malcolm Gladwell's "The Tipping Point" in its entirety.

    From Field Agent Matt Hartman (NWLife '04), here is an interesting recent NY Times article on some downsides and unexpected uses of thefacebook.com, and a related Chicago Tribune article on the posting of personal material on blogs and social networking services.

    Thanks to current NWLifer Sujay Vennam for gathering this year's first extra credit by pointing out the following Business Week article on the rise of mathematical modeling and algorithms for online social data such as marketing, blogs, and search engine keyword bidding.

    From NWLifer Steve Pelhan, a very cool network visualization for musical artists, movies, etc: liveplasma. Haven't figured out what exactly consitutes a link, but it looks good.

    From NWLifer Meredith Nussbaum, an interesting article on the influence of thefacebook.com on fraternities and sororities.

    Lectures:
    Tu Jan 24
    Th Jan 26
    Contagion and Tipping in Networks

    Part of the Tue Jan 24 lecture will be spent covering background and preparatory material for the required experiments on the evenings of Jan 24 and 25. You must be present for this lecture in order to receive credit.

    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.

    One of the main course themes is the distinction between the dynamics of "transmission" and the dynamics of "rationality" in networks. From NWLifer Raphael Cohn, here is a very interesting article on host maniupulation by the malaria-causing parasite that blurs this distinction: here we have both viral transmission, but also what might be viewed as strategic behavior by the parasite. Apparently this kind of manipulation is common in biology. It might also be interesting to think about this phenomenon as a kind of adaptive "stickiness" in the language of Gladwell.

    Following up on our class discussion of the human cortex and the problem of associative memory, here are some further details about the brain and an intro to artificial neural networks, which are a common and successful statistical modeling method used in many fields. Thanks to NWLifer and Cognitive Science major Ana Gutierrez-Colina for this contribution.

    Many thanks to NWLifer Wesley Rosenblum for this fascinating article on modeling human travel patterns via the web-based tracking of dollar bills. For the more mathematically inclined, here is the original scientific paper. We may well return and discuss this work in more detail a bit later in the course.

    Experiments:
    Evenings of
    Jan 24, 25
    6-8 PM
    (end time approximate)
    Location:
    207 Moore
    Additional Logistics and Compensation Details Prior to the experiments, you should carefully read and understand this background material.

    On the evenings Tue Jan 24 and Wed Jan 25, from 6 PM to approximately 8 PM, we will conduct out-of-class experiments in communal problem-solving over a human network (you will be the humans). Participation at both sessions is mandatory and each will last a couple of hours. (Accomodations will be made for students with legitimate conflicts provided they make arrangements with Prof Kearns in advance.) Course credit will be supplemented by cash compensation for performance. Details will be provided as we approach the dates.

    Lectures:
    Tu Jan 31
    Th Feb 2
    Tu Feb 7
    Th Feb 9
    Social Network Theory During this week (Jan 30) and the next, you should read Duncan Watts' "Six Degrees" in its entirety.

    Here is Problem Set 1, posted Friday Jan 27, and due in hardcopy form at the start of class on Tue, Feb 7.

    Please read the following two short articles: Navigation in a Small World by Jon Kleinberg, and Identity and Search in Social Networks by Watts, Dodds, and Newman.

    From NWLifer Sharon Volotzky, two interesting reports from the field: first, an article on the perpetual monitoring of wireless users' locations at MIT and another on the tipping point in global warming.

    From NWLifer Paul Cosello, the interesting music-finding service Pandora, which is based on a "genomic" metaphor. Music is deemed similar to other music with similar values for a large set of features or "genes" devised by the system's designers. We'll see the concept of defining the distance (whether social, physical, conceptual, etc.) between two objects by projection onto a fixed set of attributes arise elsewhere in class.

    From NWLifer Armenio Keuseyan, here is a nice gallery of network visualizations, and while we're at it here is another, and yet another, this last from NWLifer Sam Bookler. Also from Armenio is this interesting Wikipedia compilation of online social networking services along with user counts and other information.

    From NWLifer Ian Goldstein, the online popularity contest AIMFight. Two AOL IM users duke it out to see who has more users within 3 links. Sick, sick stuff.

    Special office hour announcements: Due to the upcoming problem set, Partha will hold a special additional office hour Thu Feb 2 at 4 PM (see above for location). Jenn will have her usual office hour Fri Feb 3 at 2 PM.

    More reports from the field: From Sujay Vennam, a challenging graph planarity game. Though it's slightly ahead of topic, here's a very recent NY Times article on charging for email and its intended effects on spam, from Richard Lawrence. When the time comes, perhaps we'll examine some of the flaws in the proposed scheme. And from Greg Morillo, here is an interesting article on Yahoo's big bet on social network services.

    Important office hour announcement: Jenn will be unable to hold her office hours Friday Feb 10. She's happy to arrange other times by appointment.

    Lectures:
    Tu Feb 14
    Th Feb 16 (Sid Suri)
    Tu Feb 21
    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.

    Behavioral Graph Coloring Analysis Assignment: For the quantitative data analysis portion of the course this term, you will be asked to write a report and analysis on the graph coloring experiments in which you were a participant. The timeline for this assignment will be as follows. During class on Tue Feb 14, Prof Kearns will take some time to describe the nature of the report you should write and what kinds of analyses and questions it should tackle. In class on Thu Feb 16, CIS doctoral student Sid Suri will give you a tour of the various forms of experimental data we are making available to you. Your report (approximately 10-15 pages in length, including any figures, plots, diagrams, etc.) will be due by midnight Sunday, March 5 via email to Prof Kearns; see update below in entry for Feb 28 for details.

  • Here is a handout describing the assignment (Posted 2/14; please watch for revisions and updates).
  • Here is a description of the experimental design. For related material, you may want to revisit the material posted above earlier on background for experimental subjects.
  • Here is a link to the directory containing all the experimental data.
  • Added 2/21: here is a table summarizing various statistical and topological properties of the six graphs.

    IMPORTANT NOTICE: The data site is password-protected. The login and password will be announced in class, and if you forget you can email the TAs and Prof Kearns. This data is protected because it is proprietary. Please do not distribute it further, and please use it only for the purposes of this assignment.

    Compensation for Experimental Subjects: Apologies for the delay, but we've finally got the procedure in place to compensate those of you who participated in the experiments themselves. All you need to do is fill out this W-9 form and return it to us, and a check will be mailed to you. We'd like to get all these filed as quickly as we can now, so please make every effort to bring your completed forms to class on Thu Feb 16. We have records of which night(s) you participated in, and also what your compensation will be. Just to remind, all participants on Jan 24 will receive $70, while participants on Jan 25 will receive at least $85 and many will receive $95.

    Homework 1 will be returned in class Tue Feb 21. Here are sample solutions in PDF and Postscript. Some statistics: mean score was 85.2, median was 86.5, standard deviation was 9.6, low score was 53, high was 101.

  • MIDTERM DATE: The midterm will be held in class on Thursday, March 2.

    Here is only part of the backlog of interesting reports from the field; more to come shortly. From Sam Bookler, an artificial blog stock market in which valuation depends on the number of incoming links. For the literary-minded, Shakespearean social netorks from Andrew Arvin. From Brian Quimby, an incredibly rich network visualization tool on the elite and powerful. Keep 'em coming!

    Lectures:
    Tu Feb 21
    Th Feb 23
    From Local Incentives to Global Outcomes Read Schelling, Chapters 1, 3 and 4. (The entire book is well worth reading, but not required.)

    From Field Agent Kim Kearns, the social networking service 43things, which matches people with shared aspirations.

    From NWLifer Raffi Cohn, an original work of network art in which a colored vertex lies between others if it is their mixture.

    Lectures:
    Tu Feb 28
    Midterm Q&A .

    TA Jenn has graciously volunteered to hold special office hours Wed Mar 1 from 3:30 to 4:30 in her usual office location.

    IMPORTANT ANNOUNCEMENT: While the "official" deadline for the Behavioral Graph Coloring Analysis Project reports remains Fri Mar 3 at midnight, I have decided to accept "late" reports without penalty through Sun Mar 5 at midnight. Since Levine Hall is likely to be locked over the weekend, the revised submission instructions are that you must email your report to Prof Kearns at mkearns@cis.upenn.edu as an attached document, with the subject line of the message being "BGC Report". Failure to use this subject line may result in your submission being lost.

    Thu Mar 2: MIDTERM EXAM
    .

    .

    The midterm will cover all material through the lecture of Tue Feb 28. For your perusal, here are the 2004 midterm with solutions and the 2005 midterm.

    Week of
    Mar 6:
    SPRING BREAK
    .

    .

    .

    Lectures:
    Tu Mar 14
    Th Mar 16
    A Brief Introduction to Game Theory In the first week of class we read just the introduction to "Economics, Computer Science, and Policy". You should now read the paper in its entirety, which will be discussed in the Mar 21 lecture.

    .

    Lectures:
    Tu Mar 21
    Interdependent Security Games and Networks The midterms have been graded and will be returned at the end of class Th Mar 16. The average score was 69, the high was 91, and the low was 37. Solutions have been posted here.

    This week Prof Kearns will hold office hours on Fri Mar at 11 AM. If you have questions about the grading of your midterm you should first see the TAs (Partha for problems 1-4 and Jenn for problems 5-9), since they did the grading and also established the grading guidelines and standards for consistency. If you have questions about course or midterm content, how you're doing in the class, or other concerns, please stop by.

    OK, here comes a massive Intelligence Report from the Field. Many thanks as always to all of you for your diligence in documenting and deconstructing the modern world.

    From Richard Lawrence, the Censearchip site developed at Indiana University, which allows you to see how Google search results in other regimes, uhmmm I mean countries, differ from those here.

    From Paul Corsello, and again on the Google front, an amusing incident involving the gaming of the Google News press release mechanism.

    On the more serious side from Chris Koenig, a recent Phys Rev article proposing a new network generation model based on the physical movement of particles, and which reconstructs many of the structural properties examined in the course. And thanks once again to Sujay Vennam for this more informal discussion of the same model.

    From serial contributor Brian Quimby, here's an interesting site that includes network analyses of senate and congressional voting behavior.

    More to come soon; still have further backlog to catch up on.

    Lectures:
    Th Mar 23
    Tu Mar 28
    Exchange Economies on Networks In class on March 28, we will hold an informal in-class experiment on networked exchange economies. .
    Tu Apr 4: NO CLASS
    .

    Prof Kearns has a longstanding commitment out of town April 4.

    .
    Lectures:
    Th Apr 6
    Behavioral Graph Coloring

    In this lecture, we will (finally) go over some of the main findings from the behavioral graph coloring experiments. Your BGC reports will also be returned. The class average on these was 78 with a standard deviation around 13; the high was 95 and the low 40.

    I am told by the SEAS business office that about half of the compensation checks for the BGC experiments have come in; I am actively bugging them to do the rest, at which point they will be distributed. Apologies for the delays but you will be paid!

    FINAL EXAM: The final exam will be held Wednesday, May 3 from 12 to 2 PM in DRLB A8.

    .
    Lectures:
    Tu Apr 11
    Th Apr 13
    Economic Models of Network Formation

    The moolah is finally here! Checks for BGC participation will be distributed at the end of class Tue April 11.

    .
    Lectures:
    Th Apr 13
    Tu Apr 18
    Th Apr 20
    Economics and the Internet

    Jenn will not be holding office hours this Friday (April 14), but Prof Kearns will: 9-10 AM Friday April 14. If you have not yet picked up your payment for BGC participation, please come to office hours.

    At the start of class on Thu Apr 20 I will distribute and provide time to fill out course evaluations. I'd likely to strongly encourage all of you participate; past feedback has directly helped me improve the course.

    If time permits, the last portion of the final class meeting on Thu Apr 20 will be used for a quick course review.

    Here is a final round of course-related material submitted from the field. Many thanks to all of you who submitted during the term; it helps keep the course fresh!

    From Brandon Rosenblum, the self-explanatory Six Degrees of Wikipedia and an article about the Brazilian takeover of Google's Orkut.

    From Peter Na, a recent article about tipping points in global warming.

    From Mike Seltzer, an article on modeling the spread of Avian flu along with an associated visualization and simulator.

    From NWLife extra-credit addict Brian Quimby, a very nice and extensive gallery of network visualizations.

    FINAL EXAM: Wed May 3
    12-2 PM
    DRLB A8
    .

    The final exam will be cumulative, with a slight emphasis on material since the midterm. Any and all course material may be relevant.

    Here are the final exams from 2004 and 2005.

    Office hours and reviews during reading period:

    Prof Kearns will hold office hours in 509 Levine from 10-11 AM on Thu Apr 27, and Tue May 2 from 11-12.

    Partha will hold review sessions/office hours on Monday April 24 and Monday May 1 from 4-6 PM. For these sessions, the office hours will be held in the large conference room at IRCS (Room 470 of 3401 Walnut). There is a projector there so Partha can bring up slides and other course material for those that want to review or refer to them.

    Jenn will hold review sessions/office hours Wednesday, April 26, 2-4pm, and Friday, April 28, 2-4pm, both in Levine 307, where there again is a projector.

    To all: Have a great summer! It was a delight to teach you this term.


    ADDITIONAL LINKS AND RESOURCES

    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
  • The forest fire and viral spread demos from class (both developed by Sangkyum Kim for the Spring 2004 course)
  • 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