Missing Image   Missing Image   Missing Image   Missing Image   Missing Image

Networked and Social Systems Engineering (NETS) 112
Fall 2014
Tuesdays and Thursdays 10:30-12, Berger Auditorium, Skirkanich Hall
Prof. Michael Kearns

Jump to the course schedule.


  • What science underlies companies like Facebook, Google, and Twitter?
  • What are the economics of email spam?
  • Why do some social networking services take off, and others die?
  • What do game theory and the Paris subway have to do with Internet routing?
  • How does Google find what you're looking for... and exactly how do they make money doing so?
  • What structural properties might we expect any social network to have?
  • How might a social network influence election outcomes?
  • What problems can be solved by crowdsourcing?
  • How does your position in a social network (dis)advantage you?

    Networked Life looks at how our world is connected -- socially, strategically 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, sociology, mathematics, 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, and is taught accordingly. There will be ample opportunities for those of a quantitative bent to dig deeper into the topics we examine. The majority of the course is grounded in scientific and mathematical findings of the past two decades or less (often much less).

    Fall 2014 is the eleventh offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from past years:
    [Fall 2013]   [Fall 2012]   [Fall 2011]   [Spring 2010]   [Spring 2009]   [Spring 2008]   [Spring 2007]   [Spring 2006]   [Spring 2005]   [Spring 2004]
    (Note: the Fall 2011 version used a different course management platform than the simple HTML site we'll be using this year, so it might be easiest to peruse the 2013 and pre-2011 sites to get a sense of how the course unfolds.)

    There is also a greatly condensed version of this class offered to the general public as part of the online education platform Coursera. All Penn students should create a (free) Coursera account, and sign up for the session of Networked Life there that begins on Monday, September 1, 2014. See the course schedule for information on how we will make use of the online material and how to sign up.

    Networked Life is the flagship course for Penn Engineering's recently launched Networked and Social Systems Engineering (NETS) program. Throughout the course we will foreshadow material that is covered in greater depth in later NETS program courses.


    The following three books 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.

    NOTE: The books are not yet in the Penn bookstore, but "The Tipping Point" should be in stock there by Friday September 5.

    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.


    Prof. Michael Kearns, Course Instructor
    Levine Hall 509
    Office hours: Tuesdays 12-1 PM (right after lecture), or by appointment

    Shahin Jabbari, Teaching Assistant
    Office hours: Mondays 12-1:30 in GRW 571 or by appointment. Take the elevator to the fifth floor of Levine Hall, go down the ramp and then turn right.

    Ryan Rogers, Teaching Assistant
    Office hours: Thursdays 12-1:20 in GRW 565 or by appointment. Take the elevator to the fifth floor of Levine Hall, go down the ramp and then turn right.


    Attendance at the main lectures is considered mandatory for all enrolled students. They are held Tuesdays and Thursdays 10:30-12 in Berger Auditorium of Skirkanich Hall. There are no recitations for the course.


    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.


  • 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 CIS and SEAS.
  • Networked Life can be counted for credit in the Philosophy, Politics and Economics (PPE) and Science, Technology and Society (STSC) programs. Check with your academic advisor in these programs to confirm exactly how you can count the course.


    The main lectures for Networked Life will be in fairly traditional format, including class participation, discussion, and communal experiments. PDF slides for all lectures will be provided, usually at least slightly in advance of the lecture itself.

    There will be two or three homework assignments. These will include simple quantitative exercises, as well as essay questions, computer and web exercises. Collaboration on the homeworks is not permitted.

    There will be a midterm, and a final exam.

    As an added bonus, this year there will also be online experiments on solving challenging problems in networks.

    It is anticipated that the homeworks, experiments, midterm and final will each count for approximately a quarter to a third 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 (see the "Fourth Column" below).


    Except for occasional hard-copy handouts distributed in lectures, all of the material for the course will be posted in the table below. Lecture slides, reading and homework assignments, in-class and out-of-class experiments, due dates, exam information, etc. will all be provided below. The materials posted are initially those from the last offering of the class, and will be gradually updated and possibly altered as we progress through the course. New materials and topics may be added as well. Reading and working ahead are encouraged, just be aware that things may change a bit as we proceed. 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 PDF format, but they may often contain links to documents in other formats, including Postscript, JPEG, video, etc. In order to view all of the linked content you may need to be using a computer with viewers installed for these formats. Note that since slides are revised shortly in advance of each lecture date, links to future decks may not yet be active.

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

    "THE FOURTH COLUMN" will be used to put links to class-related materials from the popular media, the web, etc. Extra credit will be provided to those who send me such material if it is used.

    Tu Sep 2
    Course Introduction and Overview
    [PDF] [PPT]
    (Rev. 8/21)

    There is a greatly condensed version of this class available to the general public, launching on Coursera on Monday, September 1. All Penn students are required to register for the Coursera version, and to watch the videos corresponding to class content as we encounter them, as per the scheduled links given below. Penn students are not required to take the Coursera quizzes, but are strongly encouraged to do so to test understanding. You should create a Coursera account (which is free) and register as soon as possible, since registration will close in a couple of weeks. Note that the Coursera version moves at a 7-week pace with quizzes etc., but you will have access to all materials after the 7 weeks.

    Here is the Coursera course overview video.

    Within the first two weeks of class, you should read Malcolm Gladwell's "The Tipping Point" in its entirety. While we will not spend a lot of time in lectures directly on the book, it remains a highly readable introduction to some central course themes.

    Here is a document containing a brief background survey and our second communal social experiment. Please print them out, complete them (which should only take a few minutes), and return them at the start of the second lecture (Th Sep 4), as we will analyze the results of the social experiment on the fly in class.

    As sample Fourth Column material, A contagion oldie but goodie.

    Th Sep 4
    Th Sep 11
    Structural Properties of Networks: Introduction
    [PDF] [PPT]
    (Rev. 9/9)

    Here are two Coursera videos that are related to this set of lectures:

    What is a Network?

    The Erdos Number Project

    During the first few weeks of class, you should read Malcolm Gladwell's "The Tipping Point" in its entirety. While we shall directly refer to this book in lecture only occasionally, you are responsible for the material in it.

    First-to-Field-Agent honors go to Yoni Nachmany, for this blog post and interview about the dating site OkCupid's experiments on its users.

    From Field Agents Nathan Tien and Jeff Grimes, mapping the spread of the Ice Bucket Challenge on Facebook, and a related TechCrunch article. From F.A. Shaurya Dogra, a critique of the Facebook emotional contagion study. From F.A. Rohan Bhide, compute your own Erdos Number.

    From F.A. Parker Stakoff, Six Degrees of Separation --- the song, "CLEAN VERSION". Warning: it's awful. Maybe I need to hear the explicit version.

    Tu Sep 9
    Graph Coloring: Background and Assignment
    [PDF] [PPT]
    (Rev. 9/9)

    In this assignment, described in lecture and in the accompanying slide deck, you are asked to find solutions (proper colorings) for a set of 30 graphs. This assignment will be done entirely via this web application which will be available as of noon on September 9. You should complete the assignment by midnight on Tuesday, September 16, at which point we will close the app. No collaboration is permitted, and you should use only the email address for which you are registered in this class to log into the app. The scoring for the assignment is described in the app.


    Th Sep 11
    Contagion in Networks
    [PDF] [PPT]
    (Rev. 9/11)

    Here is a Coursera video related to this topic:

    Contagion in Networks


    Tu Sep 16
    Th Sep 18
    Navigation in Networks
    [PDF] [PPT]
    (Rev. 9/18)

    During this set of lectures, we will discuss the following five articles. You do not not have to read them in full detail, but you should certainly understand the main themes that we touch on in class.

    ``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.

    Navigation in a Small World, Kleinberg.

    Identity and Search in Social Networks, Watts, Dodds, Newman.

    The Scaling Laws of Human Travel, Brockmann, Hufnagel, Geisel.

    There are two Coursera videos associated with this lecture:

    Navigation in (Social) Networks

    Navigation in Networks, Revisited

    The midterm will be held in class on Tuesday, October 21.

    The final exam for the course will be held at 9AM on Thursday, December 18, location TBD.

    Here is Homework 1, (revised 9/22 to include point totals) due in hardcopy form at the start of class on Tuesday, September 30.

    From F.A. Deepan Saravanan and R.O. Shaurya Dogra, overliking and underliking on Facebook. From F.A. Arhamul Amin, the Rise and Fall of Flappy Bird. From F.A. Chris Cahill, contagion in the housing market. From F.A. Allison Schwartz, graph coloring in social networks and minesweeper on graphs. Next someone will tell me that Pong is NP-Complete.

    Tu Sep 23
    Th Sep 25
    How Do Real Networks Look?
    [PDF] [PPT]
    (Rev 9/23)

    For these lectures and the next set, you should read Chapters 2, 3 and 4 in "Six Degrees". (I recommend simply reading the book in its entirety, but will not require it.)

    We will also be discussing the following paper, which you should read as best you can (some of the math is beyond our scope, but you should at least understand the parts discussed in lecture):

    Four Degrees of Separation. Backstrom et al, 2012.

    Here are Coursera videos associated with this set of lectures:

    How Do Real Networks Look? I. Heavy Tails

    How Do Real Networks Look? II. Small Diameter

    How Do Real Networks Look? III. Clustering of Connectivity

    Tu Sep 30
    Th Oct 2
    Models of Network Formation
    [PDF]   [PPT]
    (Rev. 9/28)

    Coursera videos associated with these lectures:

    Models of Network Formation I. The Erdos-Renyi Model

    Models of Network Formation II. Clustering Models

    Models of Network Formation III. Preferential Attachment


    Tu Oct 7
    Web Search and the PageRank Algorithm
    [PDF]   [PPT]
    (Rev. 10/7)

    Coursera video associated with this lecture:

    Important Vertices and the PageRank Algorithm

    Here are solutions for Homework 1. The average was 86.8 and the standard deviation was 9.8. The solution set indicates which TA graded each problem; if you have questions about grading you should see the appropriate TA.

    Tu Oct 14
    Incentives and Collective Behavior
    [PDF]   [PPT]
    (Rev. 10/6)

    Read Schelling, "Micromotives and Macrobehavior", Chapters 1, 3 and 4.

    Coursera video associated with this lecture:

    Towards Rational Dynamics in Networks

    From F.A. Erin Lambroza, the network of Ebola spread. Let's hope this one doesn't get any bigger. From F.A. Julia Cohen, contagion and Facebook invitations from our friend Jon Kleinberg. The interesting finding here is the importance of diversity in invitations. From F.A. and R.O. Karinna Loo, game theory in everyday life and network analysis in soccer. From F.A. John Mallock, the network of ISIS. From R.O. Rohan Bhide, power users on Facebook.
    Th Oct 16
    Th Oct 23
    Introduction to (Networked) Game Theory
    [PDF]   [PPT]
    (Rev. 10/23)
    Coursera videos associated with this lecture:

    Basics of Game Theory

    Games on Networks: Preview

    Tu Oct 21
    The midterm will be held in class on Tuesday, October 21. It will a closed-book, closed-note exam covering all material in the course to date.

    To help you prepare for the midterm, here are past midterm examinations (some but not all with solutions) from 2013,   2012,   2011,   2010,   2009,   2008,   2007, and 2006.

    Tu Oct 28
    Coloring Experiments Analysis; Competitive Contagion Experiment
    [PDF]   [PPT]
    (Rev. 10/30)

    During today's class, we will examine some analyses of the graph coloring assignment/experiments, and will also describe the next assignments, which are experiments in competitive contagion. The app for this assignment can be found here, and it will become live at noon after today's lecture.

    Midterms will be returned at the end of class today. The average was 74.3, and the standard deviation was 11.5. Here is the histogram of scores, and here are solutions and grading guidelines. If you have questions about how a problem was graded, please first see the TA who graded it.

    Thu Oct 30
    Tu Nov 4
    Tu Nov 11
    Networked Games: Coloring, Consensus and Voting
    [PDF]   [PPT]
    (Rev. 11/4)

    Read the following articles associated with these lectures:

    Experiments in Social Computation, MK.

    Behavioral Experiments on a Network Formation Game, MK, S. Judd, Y. Vorobeychik.

    Coursera videos associated with these lectures:

    Games on Networks: Coloring and Consensus

    Games on Networks: Biased Voting

    Tu Nov 4
    Competitive Contagion: Discussion and Preliminary Analysis
    [PDF]   [PPT]
    (Rev. 11/4)
    Reminder: As part of the Competitive Contagion assignment, you are also required to complete the survey that is linked to on the app. .
    Th Nov 6

    Due to an out-of-town commitment of Prof Kearns, there will be no lecture on November 6.

    Tu Nov 11
    Th Nov 13
    Tu Nov 18
    Th Nov 20
    Trading in Networks
    [PDF]   [PPT]
    (Rev. 11/18)

    To introduce the topic of trading in networks, we'll have an in-class experiment on Tuesday, November 11.

    Coursera videos associated with these lectures:

    Trading in Networks: I. Model

    Trading in Networks: II. Network Structure and Equilibrium

    Trading in Networks: III. Behavioral Experiments

    Tu Nov 25
    Tu Dec 2
    Internet Economics [PDF] [PPT]
    (Rev. 11/24)

    Coursera video associated with these lectures:

    Internet Games: I. Packet Routing

    Internet Games: II. Sponsored Search

    Internet Games: III. Other Economic Problems

    As always, you are responsible for all the material in all videos even if I didn't cover it in lecture (as for the last two videos above).

    Here is Homework 2, (updated 12/4 to clarify Problem 9a) which is due in hardcopy form at the start of class on Tuesday, December 9.

    OK... at long last, and just in time for your Thanksgiving reading list --- a bulk Fourth Column update. Thanks to all for these excellent contributions.

    From F.A. India Yaffe, Firechat and Occupy Hong Kong. From F.A. Samantha Markowitz, Nash equilibrium and dating. From F.A. Omar Pena Jimenez, centrality measures and Facebook. From F.A.s Michael Sha and Dhriti Kishore, game theory, networks, and military alliances. From F.A. Pranay Sharma, game theory and marriage. From F.A. Joseph Martin, game theory and Ebola. From F.A.s Gabrielle Skladman and Phoebe Deards, the game theory of Airbnb reviewing. From R.O. Karinna Loo, Prisoner's Dilemma for actual prisoners. From F.A. Ankit Das, critical phenomena and the Tracy-Widom distribution and Facebook and elections. From R.O. Shaurya Dogra, a related article. From F.A. Andrew Wang, spreading Ebola (panic) on Facebook.

    From F.A. Joshua Bodner, inequality aversion in monkeys. From R.O. John Mallock, contagion and suicide. From F.A. Dan Haroun, contagion modeling with Wolfram Alpha. From R.O. Michael Sha, game theory and quant trading. From F.A. Don Yu, are you important? Again from R.O. Shaurya Dogra, the rise of Yik Yak. From R.O. Dhiti Kishore, an insider trading network.


    Th Dec 4 Community Detection in Networks
    This lecture will be devoted to a discussion of community detection or clustering in networks, which is the focus of our final online experimental assignment. The link for the web app for this assignment is here, and will be made live right after lecture. As is described on the app, the assignment will be graded and counted for course credit. It must be completed by 11:59PM on Thursday December 11. You also required to complete the survey on the app.

    Tu Dec 9 Review Session Ryan and Shahin will run a review session in preparation for the final exam. If there are particular topics you'd like them to cover, please send them email and they will do their best to accomodate. .
    Th Dec 18, 9AM FINAL EXAM The final exam for the course will be held 9-11AM in DRLB A1. The exam will be cumulative of the entire course. It is closed-book and closed-note.

    Here are the slides from the review session held by Ryan and Shahin.

    To help you prepare for the final, we will hold office hours next week as follows: Monday Dec 15: Shahin 12-2PM; Tuesday Dec 16: Ryan 1-3PM; Wednesday Dec 17: Ryan 11-1PM, Shahin 3-5PM.

    Prof. Kearns will be holding office hours on Tuesday Dec 16 from 3-5PM.

    Here are solutions to Homework 2. . The average was 82.6, and the standard deviation was 22.1. As usual, if you have concerns or questions about grading, please first see the TA that graded the problem in question, which is specified in the solution set.

    Here are some past final exams, some with solutions, to help you study. Please note that some of the questions are on topics we did not cover this year, and that we covered topics this year that are not represented on the exams.

    [2004]   [2005]   [2006]   [2007]   [2008]   [2009]   [2011]   [2012]   [2013]