HOW |
 
          ARE |
 
              THESE |
 
          PEOPLE |
 
            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
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:
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
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.
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: 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:
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: 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. | . |