COURSE DESCRIPTION

What kind of science is appropriate for understanding the Facebook?
How does Google find what you're looking for... and exactly how do they make money doing so?
What properties might we expect any social network to reliably have, and are there simple explanations for them?
How does your position in an economic network (dis)advantage you?
How are individual and collective behavior related in complex networks?
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 our world is connected -- socially, economically, 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, 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.

Spring 2008 will be the fifth offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from Spring 2007,   Spring 2006,   Spring 2005, and Spring 2004. This year the course will cover many of the same topics, updated in light of new research since the 2007 offering. As has become standard in the course, we plan to include communal experiments in distributed human decision-making on networks.

REQUIRED TEXTS

The following three books, all in paperback and 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: This term I will hold "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.

COURSE PERSONNEL

Jinsong Tan, teaching assistant
jinsong@seas.upenn.edu
Office hours: Thursday 3:30-4:30 in GRW 571 (take the elevator to the 5th floor of Levine, go down the ramp and turn right)

Ted Sandler, teaching assistant
tsandler@seas.upenn.edu
Office hours: Monday 5-6 PM in 513 Levine

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 may also be 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.

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 Jan 17	Course Introduction and Overview	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 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 next lecture (Tu Jan 22), as we will analyze the results of the social experiment on the fly in class.	Here is an interesting recent NYT article on uses of the Facebook in academic research. And from Field Agent Dan Baker, here is a nice compilation of research articles on social networks.
Tu Jan 22 Th Jan 24	The Networked Nature of Society	.	As mentioned in the first lecture, it is the increasing "instrumentation" of human activity via technologies like the Internet, wireless devices, etc. that makes possible the measurement of many of the networks we will study this term. While this is inarguably a goldmine for scientific research (see link to NYT article in the entry above), it inevitably raises privacy issues as well. From Field Agent Caleb Rosenberg-Szubski, here's a recent article from Wired magazine that speaks to this topic. On a related note, here is an article from the DP on corporate trolling of the Facebook for profiles of potential employees. Believe it. From Field Agent Bradley Eisemann, here is the academic article on teen sexual liasons that provides considerably more detail and modeling than our brief discussion in class. There has apparently been a spate of suicides in a small town in Wales, and concern that social networking sites may be contributing to it. Chapter 7 of Gladwell seems directly relevant.
Tu Jan 29 Th Jan 31	Contagion, Tipping and Navigation in Networks	These lectures are the ones most closely tied to "The Tipping Point". We'll also discuss the following three assigned readings: ``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. Every once in a while, a Fourth Column submission is so timely and relevant it makes it into the Third Column. From Field Agent Stephanie Kirby, here is an article in Discover magazine discussing the two articles above. It mentions a number of drawbacks of the Travers and Milgram study that we will discuss and some others that we won't, and describes the efforts of Dodds et al. to provide a "multi-dimensional" personality model for social navigation.	Yet Another Facebook Article (YAFA): This time, on the Facebook's move to open up third-party apps to other platforms. Speaking of multidimensional personalities (see left), Field Agent Amy Yu forwards this report of the new social networking site Moli, which permits one to maintain multiple profiles, so ideally one can stop maintaining separate Facebook and LinkedIn accounts. DJW Extravaganza: First, about a half-dozen of you pointed out this critique of The Tipping Point by Duncan Watts. First to Find credit goes to Field Agent Ariel Allon. In the interests of equal time, a special bonus is available to anyone who finds an article in which Gladwell criticizes "Six Degrees". Second, from Field Agent Juhi Heda, a blog entry on an interesting marketing experiment by Watts. Finally, all of this Wattsmedia made me ask The Man Himself whether he actually ever did any real work anymore, or simply gave interviews; not sure it counts as real work, but he responded with a new Facebook app. Go crazy. Field Agent Jue Pue checks in with this article on social navigation, which discusses several of the works we will touch on in class. Caleb Rosenberg-Szubski has been promoted from Field Agent to Repeat Offender with this WSJ article on the Magic Number 150 and social networking services.
Tu Feb 5 Th Feb 7 Tu Feb 12	Network Science: "Universal" Structure and Models of Formation	You should start reading Duncan Watts' "Six Degrees" in its entirety. Exam dates: the midterm exam will be held in class Thursday, March 6. The final exam will be held on Wednesday, May 7 at noon. Here is Homework 1, due as a hardcopy at the start of class, Thursday Feb 21.	Many reports from our active army of Field Agents: from Geoffrey Kiderman, an article on how to make money on Facebook; from Huanwu, a new social networking service from the WSJ; from R.O. Dan Baker, Google's Social Graph API; from Andrew Berg and Kristin Ying, Internet vulnerability in Dubai. My fave du jour: from Andrew Berg, Enemybook. It had to happen. A personal Fourth Column entry: As Facebook apps add more and more "actions" or "verbs" you can invoke on your freinds --- "poking" them, flipping them off, sending them a hug, etc. --- it reminds me more and more of certain longstanding and still-extant text chat environments known as MUDs and MOOs, where such rich interaction has been around forever. Back during The Bubble, some colleagues and I implemented an interesting chatbot that lived in LambdaMOO, the most revered of these environments; you can find the hopefully-easy-to-read paper here. From F.A. Amy Yu, social networking for zebras. From F.A. Feng Hong, social networking for Neilsen ratings. From F.A. Marnee Klein, social networking for charity, which reminds me to mention microloans. And, as requested, from F.A. Jeremy Kreitman for Double Extra Credit, Malcom Gladwell's very reasonable response to Watts' critique of the Hush Puppy Influentials.
Th Feb 14 Tu Feb 19	Long Tails and Navigation	Three assigned readings: Please read this article on the migration patterns of dollar bills. Don't worry about understanding the math of the paper, some of which is advanced; the goal is simply to understand the purpose of the study, its methodology, and its relevance to course topics. Please also 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. Extra TA office hours this week: Ted is available 4:30-5:30 Tuesday 2/19; Jinsong is available 2-3 Wednesday 2/20.	Directly relevant to these lectures, and bad news for Google and Microhoo!, is this article from Field Agent Yuval Masory on the heavy tail generated by natural born clickers. From F.A. Allison Karic, an interesting article on fragmentation of social networks, and "permission marketing".
Th Feb 21 Tu Feb 26 Th Feb 28	Network Science and the Web	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.	Here's a first: An excellent and original Fourth Column submission by two class members who prefer to remain anonymous. I guess we will simply name them Field Agents 86 and 99. Anyway, 86 and 99 seem to somehow be in possession of, ahem, a rather large amount of Facebook data. They plotted the degree (#friends) distribution/histogram for a sample of about 8700 Ivy League Facebook users ( raw ) and for about 37000 general population users ( raw ). Gosh, those sure look like heavy-tailed distributions to me! But how would we be sure? Well, I guess 86 and 99 must have been too busy talking into their proverbial shoe phones to take the next step, so The Chief did it for them by taking these log-log   plots. As with many real-world data sets, it looks like the tail is well-approximated by a power law --- I would eyeball it at a slope of about -2, so a quadratic power law --- but something more Poisson-like is happening at small degrees. More precisely, there is a large mass of users who appear to have no friends --- probably people who created a FB account but never used it. Kudos to our agents, and watch your noses on the way out.
Tu Mar 4	Local Incentives, Global Outcomes and Equilibrium	Read Schelling, "Micromotives and Macrobehavior", Chapters 1, 3 and 4. (The entire book is well worth reading, but not required.) Homework 1 will be returned in class today. The average score was a very healthy 91, with a standard deviation of 7.3. Here are solutions and grading standards written and used by the TAs. Office hours before the midterm: Ted will hold office hours Monday 3/3 from 5 to 7 PM; Jinsong will hold office hours Tuesday afternoon 3/4 from 3:30 to 5:30; Prof Kearns will hold office hours Wednesday 3/5 from 4 to 6 PM.	From F.A. Josh Wais: Hal Varian, Google's "Chief Economist", on why Google's search engine is better. Varian was actually at the "Collective Intelligence Foo Camp" I mentioned, and made similar comments there.
Th Mar 6	MIDTERM EXAM	The midterm exam will cover all the lectures through March 4, and all readings to date except the chapters in Schelling. However, you are responsible for the Schelling material discussed in the lectures.	.
Week of March 10	SPRING BREAK	Have fun! And remember, there's no better conversation-starter than a dog-eared copy of "Micromotives and Macrobehavior".	.
Tu Mar 18 Th Mar 20 Tu Mar 25 Th Mar 27	Introduction to Game Theory, Behavior and Networks	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. The midterm exams have been graded; the average score was 76.0, and the standard deviation was 14.6. There were no statistically meaningful differences in average scores between SEAS, SAS and Wharton students. Solutions and grading guidelines created by the TAs are posted here. For questions regarding grading, see Ted for problems 2, 3 and 7, and Jinsong for problems 4, 5 and 6.	Our operatives were suspiciously active over the break. From F.A. Lloyd Ho, here is a just-published network analysis of Microsoft instant messaging. One of the findings is that the average path length is 6.6 --- seems we're moving further apart since Travers and Milgram. From R.O. Andrew Berg, yet another suicide epidemic. I am starting to wonder whether the epidemics are caused by the suicides or the epidemic of articles about them. F.A. Abhinav Rampuria checks in with an article estimating $13M of British productivity wasted annually due to social networking. Not as bad as I thought! And remember, one person's "waste of time" is another's tenuous grip on civilized society. From F.A. and NW Life alum Greg Smithies, a very nice collection of network visualization tools. Finally, another Fourth Column challenge from yours truly. Since August, the gradual collapse of worldwide credit markets has wreaked havoc, culminating most recently (but probably not finally) in the sale of investment bank Bear Stearns to JP Morgan for $2 a share. There are obvious network effects at work here, as investment banks with subprime loan risk are threatened, in turn endangering the hedge funds to whom they provide financing and brokerage services, etc. Somewhere out there must be a network diagram documenting these interlocking vulnerabilities... Update: F.A. Alexander Chernyak partially meets the challenge above with network diagrams here and here. I am still saving the Grand Prize for one that names names, though. F.A. Erica Chalmers checks in with this report on an interesting variant of Prisoner's Dilemma. From F.A. John Tran and R.O. Caleb Rosenberg-Szubski articles on the application of game theory to the current democratic race and by Abraham Lincoln. Not to nitpick, I would call these more exercises in strategic thinking generally than game theory per se; in particular there are no equilibrium analyses. But hey, whatever brings the clicks. Some behavioral game theory links: from F.A. Jonathan Kuo, more on the Ultimatum Game and other topics here,   here, and here. From F.A. Adam Feldman, an interesting report on global risk, interdependence and network effects from the World Economic Forum. On the topic of computing optimal strategies for complex games: checkers is solved.
Th Mar 27 Tu Apr 1 Th Apr 3	Behavioral Experiments in Networked Games	Read "An Experimental Study of the Coloring Problem on Human Subject Networks by M.K., S. Suri, N. Montfort. Since the midterm, a number of you have asked me about grading curves, remaining assignments, etc. For starters, here is the histogram of midterm scores; recall that the mean was about 76. I will say a little bit about historical grading standards for the course in lecture. In terms of remaining assignments, I expect there to be another problem set, covering material mainly since the midterm, and a short term paper in which you will be asked to find relevant articles and apply course concepts to them; students especially concerned about low grades will have the opportunity to distinguish themselves on this paper. More details will be provided as they develop. And of course there will be a final exam. Speaking of remaining assignments... here is Homework 2, due in hardcopy form at the start of lecture on Thursday, April 17.	From F.A. Ariana Ireland, and relevant to our IDS transportation network study, a spectacular visualization of flight patterns. From F.A. Liz Friedman, a nice article on inherent fairness and the Ultimatum Game. From the NWLife Seals team of Allon, Boghosian, Pickel: network science humor. A highly recommended article on a Facebook meltdown at Horace Mann.
Tu Apr 8 Th Apr 10	Network Economics	.	Here's an entry from yours truly on social networking opportunities at San Francisco Airport. Best viewed in slideshow mode.
Tu Apr 15	NO CLASS	Due to a longstanding commitment of Prof Kearns, there will be no class on this day.	.
Th Apr 17	(Behavioral) Network Economics	Remember Homework 2 is due in hardcopy form at the start of lecture April 17. Please read the paper Behavioral Experiments in Networked Trade, by S. Judd and MK.	.
Tu Apr 22 Th Apr 24	Economic Models of Network Formation	As discussed previously, there will be an optional final assignment By "optional" I mean that if you decide to do the additional assignment, it will be averaged into your final grade along with your homeworks and exams; and if you opt not to do it, your grade will be determined by your homeworks and exams alone. The optional assignment will take one of two forms: Participation in behavioral experiments on "The Democratic Primary Game", which will be discussed in class next week. There will only be one experimental session, to be held either May 8 or May 9 (you should have all received email polling your availability). We can accomodate only 36 participants and will pay for performance. If you pursue this option, you must also write a short essay (about 5 pages) on your experiences and observations. An essay applying course themes to papers and articles of your choosing. For this option you should find 2 or 3 articles from the scientific literature or popular media (other than those assigned for class) and apply course concepts to them. Fourth Column material is allowed, but creativity in choosing your sources will be rewarded. For this option your essay should be about 7 pages. More details as they emerge; for either option, your accompanying essay will be due in hardcopy form on Tuesday, May 13 (the last day of final exams).	Finally, a little Fourth Column catch-up. From F.A. Jing Jin, an article on Schelling, SUVs and the NHL. From F.A. and squash player extraordinaire Ryan Rayfield, two challenges to conventional wisdom --- first, an article questioning the business model of social networking, and second, one questioning common wisdom about information dissemination on the web. From F.A. Anthony Okoro, game theory and eligible bachelors. From F.A. Calvin Lee, a recent NYT article on corporate uses of prediction markets. From F.A. Catherine Gao, bad news for parents: game-theoretic child-rearing.
Th Apr 24 Tu April 29	Internet Economics: A Survey	In our final lecture, we will also briefly discuss the behavioral experiments on "The Democratic Primary Game" to be held May 9 (see below). All students wishing to do an optional assignment must reply to the email Prof Kearns sent on the topic. Those of you who have been selected to participate in the behavioral experiments should have received a separate email indicating so. On the topic of voting --- I highly recommend Ron Rivest's talk on electronic voting this Thursday at 3 PM. It's a great topic and he's a great speaker and thinker. Here are solutions to Homework 2. The average score was about 90 and the standard deviation about 8.	This is either a high point or a low point: from R.O. Jonathan Kuo, game theory of the toilet seat.
Mon May 5, 4:30 PM	Course Review	Prof Kearns will hold a course review session in preparation for the final exam in our usual auditorium. Also, the TAs will hold the following extended office hour sessions: Ted on Fri May 2 from 2 to 4 PM; Jinsong on Tue May 6 from 1 to 5 PM. And for your reviewing pleasure, here are the final exams from 2004,   2005,   2006, and 2007 (this last one with solutions! ).	.
Wed May 7	FINAL EXAM, 12-2 PM, 100 Towne	The final exam will cover material from the entire course.	.
Fri May 9	Behavioral Experiments: "The Democratic Primary Game", 6 PM, 207 Moore	.	.
Tue May 13	Optional assignment write-ups due	.	.