CSE 112

Prof. Michael Kearns

The URL for this page is: http://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife

  • Slides for Penn Reading Project

    There is a newsgroup for the course at upenn.cis.cse112


    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? How does the stock market actually work? What do game theory and the Paris subway have to do with Internet routing?

    This course 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 ranging from computer science to physics to psychology to economics. 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 appropriate for an educated audience with or without a strong technical background.


    Prof. Michael Kearns
    Levine Hall 507
    Office hours: Thursday 10:30 - 12 in Levine 507 or by appointment


    Nick Montfort
    Office hours: Monday 3-4 in the Levine Cybercafe, or by appointment

    Kilian Weinberger
    Office hours: Friday 1-2 in the Levine Cybercafe, or by appointment

    To send mail to Prof. Kearns, Nick and Kilian, mail to cse112@seas.upenn.edu


    Attendance at the main lectures should be considered required. They are held Tuesdays and Thursdays 9-10:30, Levine Hall 101.

    There are two recitation sessions each week, Tuesday 6-7 in Towne 311, and Wednesday 5-6 in Towne 315 (note room change for Wednesday). These are optional but highly recommended.


    No formal prerequisites. A course in programming is not required, but students should be comfortable using computers and accessing resources on the Internet.


    The course will be run in a fairly traditional format consisting of the regular weekly lectures, regular problem sets mixing essay questions, computer and web exercises, and simple quantitative exercises. There will be a midterm and final exam. There will be roughly 6 problem sets counting for about 25% of the grade. Collaboration on the problem sets is not permitted. The midterm will count for another 25% and the final for 50%.


    All students must get Eniac accounts if they do not have them already. Your Eniac accounts will be used for all communications regarding the course and you will be asked to provide your Eniac username on all assignments and tests. 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.


    In addition to numerous papers, programs, and other material available on the web and linked to at the appropriate spot in the schedule below, we will examine large parts of the following books, which should be considered 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. Hardback. W.W. Norton, 2003.
  • Micromotives and Macrobehavior, by Thomas C. Schelling. Paperback. W.W. Norton, 1978.

    Here are links to some other relevant general resources for the course:

  • 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
  • Link to a related course of Prof. Christos Papadimitriou of UC Berkeley
  • 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


    The schedule given below is approximate, and will change depending on our pace. As we finish each topic, its font color will be changed from yellow to red, so the first yellow topic is where we are currently. Also, readings will be added to the required reading list as we proceed, so please monitor these entries regularly. Assigned readings should be completed by the time we finish with a topic in the lectures (at the latest). If a topic turns from yellow to red before you've finished the assigned readings, you're behind.

    Course Overview (1 lecture)

  • Slides

    The Networked Nature of Society (2 lectures)

  • Slides

    Contagion, Tipping and Networks (2 lectures)

  • Slides

    ASSIGNED READING AND HOMEWORK (note that two articles have been added below):

  • Here is Homework 1 , distributed Jan 23 and due at the start of class on Feb 5. Homework should be turned in as hardcopies in class on that day.
  • Here are the Solutions to Homework 1 , posted Feb 10. Here is a histogram of scores , which also gives basics statistics at the top.
  • Gladwell: Introduction; Chapter 1 (Three Rules of Epidemics); Chapter 2 (Law of the Few); Chapters 4 and 5 (Power of Context)
  • ``An Experimental Study of the Small World Problem'', by J. Travers and S. Milgram.
  • ``An Experimental Study of Search in Global Social Networks'', by P. Dodds, R. Muhamad, and D. Watts.

    Related readings and material:

  • Sangkyum Kim's Forest Fire Simulation
  • Sangkyum Kim's Epidemic Simulation

    Quantifying Networks: A Brief Introduction to Graph Theory (1 lecture)

  • Slides


    Social Network Theory (4 lectures)

  • Slides


  • Watts, Chapter 2 (Random Graphs), Chapter 3 (Small Worlds), Chapter 4 (Power Laws, Preferential Attachment, Rich Get Richer), Chapter 5 (Search in Networks)
  • ``The Structure of Scientific Collaboration Networks'', by M. Newman.
  • ``Marvel Universe Looks Almost Like a Real Social Network'', by R. Alberich, J. Miro-Julia, F. Rossello.
  • ``Identity and Search in Social Networks'', by D. Watts, P. Dodds, M. Newman.
  • ``Navigation in a Small World'', by J. Kleinberg.

    Related readings and material:

  • ``Mean-field Theory for Scale-free Random Networks'', by A. Barabasi, R. Albert, H. Jeong.
  • ``Hierarchical Organization in Complex Networks'', by E. Revasz and A. Barabasi.
  • ``On Power-Law Relationships of the Internet Topology'', by M. Faloutsos, P. Faloutsos, C. Faloutsos.
  • ``A Survey of Models of Network Formation: Stability and Efficiency'', by M. Jackson.

    The Web as Network (2 lectures)

  • Slides


  • Here is Homework 2 , distributed Feb 17 and due at the start of class on Feb 26. Homework should be turned in as hardcopies in class on that day.
  • Here are the Solutions to Homework 2 , posted Mar 1.
  • ``Graph Structure in the Web'', by A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopolan, R. Stata, A. Tomkins, J. Weiner.
  • ``Inferring Web Communities from Link Topology'', by D. Gibson, J. Kleinberg, P. Raghavan.
  • ``The PageRank Citation Ranking: Bringing Order to the Web'', by L. Page, S. Brin, R. Motwani, T. Winograd.

    Related readings and material:

  • ``The Structure of the Web'', by J. Kleinberg and S. Lawrence.
  • ``Authoritative Sources in a Hyperlinked Environment'', J. Kleinberg.
  • Phil Craven's high-level explanation of the PageRank algorithm.
  • The Page Rank Calculator on the web.

    Context, Motivation, and Influence: Emergence of the Global from the Local (2 lectures)

  • Slides


  • Schelling, Chapters 1 (Micro and Macro, overview), 3 (Thermostats and Lemons) and 4 (Sorting and Mixing).
  • Watts, Chapter 7 (Madness of Crowds) and Chapter 8 (Thresholds and Cascades)

    Note: the midterm will cover the material up to and including "The Web as Network".

  • Here are the solutions to the midterm. The average score on the exam was 85.


    Social Equilibrum: An Introduction to Game Theory (2 lectures)

  • Slides


  • An introductory article on game theory by Roger McCain; you should read the material that appears in the right-hand panel, continuing to ready by clicking "Next!" to read up through "Games with Multiple Nash Equilibria".
  • A brief article on a practical application of game theory

    Related readings and material:

  • Luce and Raiffa
  • Game Theory.net

    Interdependent Security Games (1 lecture)

  • Slides


  • Interdependent Security: the Case of Identical Agents H. Kunreuther and G. Heal.
  • Algorithms for Interdependent Security Games, M. Kearns and L. Ortiz. Read Sections 1, 2 and 4.

    Related readings and material:

  • Watts, Chapter 6 (Epidemics and Failures)
  • Vaccination papers

    How Do People Really Act?: Behavioral Game Theory (2 lectures)

  • Slides


  • Here is Homework 3 , distributed Mar 30 due at the start of class on APRIL 13. This is yet another change, this time to allow a little more time due to this week's Passover holidays.
  • Here are the Solutions to Homework 3 , posted Apr 16.
  • Here is an assigned article on behavioral game theory. You don't need to read the appendix, though it contains a basic intro to game theory for those who might find it useful.

    Market Economies and Networks (3 lectures)

  • Slides
  • Here is a description of a mandatory in-class participatory experiment on Thursday April 1.

    Related readings and material:

  • Info on the very cool and class-related work of artist Mark Lombardi
  • Here is a brand-new paper by Prof. Kearns and colleagues on economics in social networks that was directly inspired by class topics.

    Optimize or Mimic? Evolutionary Game Theory (2 lectures)

  • Slides


  • Here is Homework 4 , distributed April 13 and due at the start of class on APRIL 22.
  • Here are the Solutions to Homework 4 , posted Apr 30.

    Related readings and material:

  • Here is a link to the EGT applet

  • Here is are some interesting examples for the EGT applet

  • Classic book on EGT: Evolution and the Theory of Games, by John Maynard Smith. Cambridge University Press, 1982. Chapter 1 (Intro), Chapter 2 (The Basic Model, Hawks and Doves), Chapter 13 (Evolution of Cooperation)

    Internet Economics (1 lecture)

  • Slides

    Related readings and material:

    Course Review (1 lecture)

  • Slides

    Note: the final exam is cumulative, and covers the material of the entire course.