Missing Image
            HOW 
  Missing Image
            ARE 
  Missing Image
                THESE 
  Missing Image
           PEOPLE 
  Missing Image
              CONNECTED? 

NETWORKED LIFE
Market and Social Systems Engineering (MKSE) 112 (formerly CIS 112)
Fall 2012
Tuesdays and Thursdays 10:30-12, Towne Hall 100 (Heilmeier Hall)
Prof. Michael Kearns

Jump to the course schedule.


COURSE DESCRIPTION

  • 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 2012 is the ninth offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from past years:
    [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 2010 and earlier 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. 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 new Market and Social Systems Engineering (MKSE) program. Throughout the course we will foreshadow material that is covered in greater depth in later MKSE courses.


    REQUIRED TEXTS

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


    INSTRUCTOR

    Prof. Michael Kearns
    mkearns@cis.upenn.edu
    Levine Hall 509
    Office hours: Tuesdays 12-1 PM (right after lecture), or by appointment


    COURSE PERSONNEL

    Hoda Heidari, teaching assistant
    hoda@seas.upenn.edu
    Office hours: Thursdays 12-1:30, Levine Hall 465, or by appointment

    Sneha Jha, teaching assistant
    jhasneha@seas.upenn.edu
    Office hours: Wednesdays 12-1:30, student lounge on sixth floor Levine, or by appointment


    LECTURE LOCATIONS AND TIMES

    Attendance at the main lectures is considered mandatory for all enrolled students. They are held Tuesdays and Thursdays 10:30-12, Towne Hall 100 (Heilmeier Hall). There are no recitations for the course.


    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.


    CURRICULUM REQUIREMENTS FULFILLED BY MKSE 112

  • 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. In past years some upperclass SEAS students have succesfully petitioned to have the course counted for non-100 level credit; please see Prof Kearns if you are interested in this option.
  • 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.


    COURSE FORMAT AND REQUIREMENTS

    The main lectures for Networked Life will be in fairly traditional format, including class participation, discussion, and communal experiments. Powerpoint 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.

    It is anticipated that the homeworks, 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).


    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. More information on the labs is online.


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

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

    DATES SLIDES ASSIGNMENTS AND ANNOUNCEMENTS THE FOURTH COLUMN
    Lectures:        
    Th Sep 6
    Course Introduction and Overview
    (revised 9/6)

    As mentioned in the first lecture, there is a greatly condensed version of this class available to the general public, launching on Coursera on Monday Sep 10. Although I will not require Penn students to take the online version, many of you may find the materials there --- video lectures, quizzes, and discussion forums --- extremely valuable for the Penn course (for instance, for review purposes before exams). I will also post direct links to Coursera video lectures that correspond to content in the Penn course as we come to it. If you want access to the Coursera materials, you should create an account (which is free) as soon as possible, since registration for it will close in a couple of weeks. Note that the Coursera version moves at a 6-week pace with quizzes etc., but you will have access to all materials after the 6 weeks, and can ignore the quizzes or not as you prefer.

    Here is the Coursera course overview video.

    Within the first week 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 first 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 (Tu Sep 11), as we will analyze the results of the social experiment on the fly in class.

    And we already have a winner! First-to-Field-Agent status goes to Linda Lipski, who sent along this TED talk by Harvard's Nicholas Christakis. Christakis and his colleague James Fowler are famous for their claims that things like obesity and happiness are contagious.

    Here's a link to a DP article about Penn's foray into online education with Coursera, which includes a condensed version of this very class.

    Lectures:        
    Tu Sep 11
    Th Sep 13
    Tu Sep 18
    Th Sep 20
    Contagion, Tipping and Navigation in Networks
    (revised 9/20)

    These lectures are the ones most closely tied to "The Tipping Point". We'll also discuss the following two articles:

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

    You don't need to read these articles in great detail, but at least up to the resolution we discuss them in class.

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

    What is a Network?

    The Erdos Number Project

    Contagion in Networks

    Navigation in (Social) Networks

    IMPORTANT: The course midterm will be held in class on Thursday, October 18. The final exam will be held on Friday, December 14 from 9 to 11AM.

    From Field Agent Tony Xie, viral marketing: means or end?

    From F.A. Benjamin Altman, the Erdos number calculator. Of course, this app is cheating because it has a bird's-eye view of the network and "simply" computes shortest paths.

    An Oldie But Goodie: probably my favorite Fourth Column submission of all time, presented without comment.

    From F.A.s Jane Reznik, Yash Malvi, Jason Merrin, Chad Edwards-Kuhn, and Tommy Pan Fang, Google's Bacon number calculator.

    From F.A. Steve Miller, tipping with the Coen brothers.

    From F.A. Claire Lee, the University of Indiana's Truthy project.

    Lectures:        
    Tu Sep 25
    Th Sep 27
    How Do Real Networks Look?
    (Rev. 9/25)

    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

    From F.A.s Ethan Abramson, Amanda Pacheco, Michael Ramirez, Wolfram Alpha's Personal Analytics for FB. You have to let it access your FB data and sign up for a free Alpha account, but it's worth it.

    From F.A. Adriana Gonzalez, an interesting article on FB, the Magic Number 150, and other class topics.

    First-to-Repeat-Offender status goes to Sudarshan Muralidhar, who skipped F.A. altogether via two relevant submissions. First, he found the crumpled paper network analysis article. It's amazing how much free time these physicists always seem to have. Anyway, Department of Full Disclosure Item 1: It turns out the degree distribution is NOT heavy-tailed as I (mis)remembered --- it is actually well-fit by a Normal distribution --- but the distribution of the lengths of the resulting edges is heavy-tailed. Note that for us, the length of the edges are an artifact of some particular layout of the network and are thus irrelevant. But that didn't stop these guys.

    Sudarshan, who also seems to have free time on his hands, then went the extra mile and took me up on my challenge to plot the distribution of file sizes on your laptops on a log-log scale. This brings us to Department of Full Disclosure Item 2, because while his data definitely shows evidence of files much larger than the average, it would be quite a stretch to claim the distribution of file sizes is well-approximated by a power law; I'll show some interactive analysis in class. This is a "teachable moment" (i.e. the theory seems wrong in this case), and it illustrates my points about how real data is messy, and one really needs to apply goodness-of-fit methodology.

    I should note that Sudarshan did this in a specific directory, not the entire filesystem. So it's still possible that if one indexed the entire machine, the operating system files would dominate and yield heavy tails. Sudarshan? Anyone?

    Another Oldie But Goodie: From R.O. Claire Lee, a gallery of network visualizations.

    MySpace back from the grave? From F.A. Eric Szeto, a slick promotional video, and from R.O. Jane Reznik, a VentureBeat review.

    Lectures:
    Tu Oct 2
    (no mtg 10/4)
    Tu Oct 9
    Models of Network Formation
    (Rev. 10/11)
    Here is Homework 1, which is due as hardcopy in class on October 16. (Apologies for the Word document, but the URLs were not being properly translated to PDF.) As per course policy, collaboration on homeworks is not permitted.

    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

    Here is a link to the NPR piece on Coursera, Penn and Networked Life, as well as a nice DP story on Coursera, co-authored by our own F.A. Tony Xie.

    From F.A. Chloe Bower, the Wiki Game.

    Lectures:
    Th Oct 11
    Navigation Revisited
    (Rev. 10/11)

    The following three articles will be mentioned during this lecture; you do not have to read them in detail but should be familiar with their main findings as discussed in lecture.

    Navigation in a Small World, Kleinberg.

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

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

    Coursera video associated with this lecture:

    Navigation in Networks, Revisited

    From F.A. Corey Loman, an article about social influence measures and Klout. From F.A. Gabriel Duemichen, an interesting visualization of reblogging and amplification.

    Lectures:
    Tu Oct 16
    The Web Graph and PageRank (Rev. 10/16)

    Homework 1 is due at the start of class today.

    To help you prepare for the midterm, here are past midterm examinations (some but not all with solutions) from 2011,   2010,   2009,   2008,   2007, and 2006. Please bear in mind that course content and pace shift slightly from year to year, so it's possible that not all past midterm questions are relevant for this year. But it's a good test for you to even be able to recognize which problems are out of scope:).

    Coursera video associated with this lecture:

    Important Vertices and the PageRank Algorithm

    .
    Lectures:
    Th Oct 18
    MIDTERM EXAM The midterm exam will be held in class on this date. It will be a closed-book exam; only a writing implement is allowed. The exam is inclusive of all course materials to date, through the lecture of October 16. You are responsible for anything in the lectures, including but not limited to the slides, as well as all demos and readings. .
    Lecture:
    Th Oct 25
    Incentives and Collective Behavior
    (Rev. 10/23)

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

    Coursera video associated with this lecture:

    Towards Rational Dynamics in Networks

    .
    Lecture:
    Tu Oct 30
    NO CLASS Lecture cancelled due to Hurricane Sandy. .
    Lecture:
    Th Nov 1
    Tu Nov 6
    Introduction to Game Theory and Strategic Behavior
    (Rev. 11/1)
    Coursera videos associated with this lecture:

    Basics of Game Theory

    Games on Networks: Preview

    Here are solutions and grading guidelines for the midterm. The average score was 77 and the standard deviation was 15. If you have questions or concerns regarding the grading of a midterm problem, please first see the TA who graded the problem in question. For Problems 1 through 4, see Sneha Jha; for Problems 5 through 7, see Hoda Heidari.

    OK, time for a little post-Sandy Fourth Column catch-up. First of all, highly apropos of our upcoming topics (and also noted by F.A. Jeremy Hurewitz), quite recently the Nobel prize in Economics was awarded to Lloyd Shapley and Al Roth, who have made major contributions to game theory. Furthermore, Roth's work on kidney exchange can be viewed as an instance of game theory in a networked setting; if time permits, I will try to soon briefly describe some of his major contributions.

    From R.O. Steve Miller, PageRank for the World Cup. From F.A. Kaycee Anderson, more desperation from Bing. When I tried it, Google won. From F.A. Will Reeves, here is a very interesting article on "dark social" on the web.

    Lecture:
    Tu Nov 6
    Thu Nov 8
    Tu Nov 13
    Networked Games: Coloring, Consensus and Voting
    (Rev. 11/4)

    Read the following article associated with these lectures and upcoming ones:

    Experiments in Social Computation, MK.

    Coursera videos associated with these lectures:

    Games on Networks: Coloring and Consensus

    Games on Networks: Biased Voting

    Here are Homework 1 solutions and grading guidelines. The average score was 84 and the standard deviation was 13. If you have questions or concerns regarding the grading of a homework problem, please first see the TA who graded the problem in question. For Problems 1 and 3, see Hoda Heidari; for Problem 2, see Sneha Jha.

    From F.A. Ethan Abramson, six degrees of Black Sabbath. From R.O. Will Reeves, breaking news on the Ultimatum Game. From R.O. Yash Malvi, Split or Steal. This must be why Nash equilibrium forbids pre-play communication.

    Lecture:
    Thu Nov 15
    Tu Nov 20
    Trading in Networks
    (Rev. 11/12)

    IMPORTANT MIDTERM NOTICE: The correct answers to midterm problems 1f and 1g were both "FALSE" rather than "TRUE" as graded. If you gave an answer of false for 1f, you can get an additional point. If you ALSO gave an answer of false for 1g, you can get another point. But if you gave an answer of true for 1f, you cannot get any additional points for either part. Please see TA Sneha Jha for this issue.

    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

    Here is Homework 2, which is due at the start of class on December 4 in hardcopy format.

    .
    Lecture:
    Tu Nov 27
    Th Nov 29
    Tu Dec 4
    Internet Economics
    (Rev. 12/4)

    Coursera video associated with these lectures:

    Internet Games: I. Packet Routing

    Internet Games: II. Sponsored Search

    Internet Games: III. Other Economic Problems

    From F.A. Aaron Cohen, the extremely cool Xefer Wikipedia Radial Graph. From F.A. Ray Lei, looks like GE is getting into outsourcing its analytics via competitions, along the lines of Kaggle. From F.A.s Kathy Zhou and Patrick Ford-Matz, the excellent if generically named Internet map. From F.A. Daniel Trujillo, the shortage of IP addresses and checking whether you are ready. From R.O. Jane Reznik, How Big is the Internet? Actually, turns out not very. From R.O. Amanda Pacheo, Nash equilibria of the NBA.

    Lecture:
    Th Dec 6
    Q&A with the TAs I will be out of town for the last lecture, but TAs Hoda Heidari and Sneha Jha will be in class to answer any questions regarding course material for the final exam. .
    Lecture:
    Mon Dec 10, 4PM
    REVIEW SESSION I will hold a review session for the final exam in our usual room at this date and time.

    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.

    [2004]   [2005]   [2006]   [2007]   [2008]   [2009]  

    Lecture:
    Fri Dec 14
    FINAL EXAM The final exam for the course is Friday, December 14 from 9 to 11AM in our usual lecture hall. It will be a cumulative, closed-book, closed-note exam. .