COURSE DESCRIPTION

How might a social network influence election outcomes?
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 2009 will be the sixth offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from Spring 2008,   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

Bill Kandylas, teaching assistant
kandylas@seas.upenn.edu
Office hours: Mon 10:30-12, 513 Levine

Emily Pitler, teaching assistant
epitler@seas.upenn.edu
Office hours: Tue 1:30-3, 512 Levine

Ted Sandler, teaching assistant
tsandler@seas.upenn.edu
Office hours: Wed 5-6:30, Levine 5th floor area by the elevators

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 15	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 second lecture (Tu Jan 20), as we will analyze the results of the social experiment on the fly in class.	Congrats to this semester's first designated Field Agent, Clayton Gardner, for the latest in the endless onslaught of articles about how tech-savvy our incoming administration will be. Apparently Americans think Barack should favor Facebook over MySpace. Good to see that the Washington think tanks are keeping on top of this stuff.
Lectures:         Tu Jan 20 Th Jan 22 Tu Jan 27 Th Jan 29	Contagion, Tipping and Navigation in Networks (Rev. 1/27/09)	Please remember to bring completed hardcopy background surveys (see above) to class Jan 20. Also, we will start off class on Jan 20 with some informal, and hopefully fun, in-class experiments on navigation in social networks. These lectures are the ones most closely tied to "The Tipping Point". We'll also discuss the following two 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.	Freshly minted Field Agent Tom Prior checks in with this techcrunch article on the Whopper Sacrifice Episode on Facebook. While not an assigned reading, here is an article in Discover magazine discussing the two assigned articles to the left. 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. Here is a network visualization of the Madoff scandal. Network fragments such as this are sometimes called "ego networks" since they focus exclusively on the network neighborhood of a single individual (though they usually would also include connections between that individual's neighbors). A slew of new Field Agents: From Matt Berger, a NYT article from back in November on the Obama campaign's early adoption of social networking. From Joseph Lee, a report card on social network performance during the inauguration. From Thomas Brandt, gender differences in social networks. From Parijat Sarkar, the Facebook Mafia. From F.A. Jordan Zarrilli, a WSJ article on corporate usage of social network analysis. From F.A. Melissa Ross, an interesting discussion of Facebook and social change in young Egyptians. And from F.A. Mohammad Murtaza, an older but fascinating and highly relevant article on the contagiousness of obesity. This is a fine example of research enabled by careful measurement over time --- in this case, a set of human subjects, their health data and social relationships in a geographically contained area. Some of the same authors have also used this data set to examine contagion effects in smoking cessation. It is also worth noting that despite the complexities that must be involved in smoking and eating decisions, it remains a powerful metaphor and method to summarize behaviors as simple contagion. RESEARCH PROJECTS WITH PROF KEARNS: A number of you have sent emails asking about doing independent study, senior designs or research projects with me. I appreciate your interest and will do my best to try to respond in the coming weeks. Meanwhile, however, there are two project areas that I am particularly interested in finding students for. Both of them require strong programming abilities. The first would involve programming automated trading strategies on the very interesting Facebook and web application called kaChing, which can be thought of as an open-source, Web 2.0 social experiment in financial market trading (typically one of the most secretive of all activities and communities). Here is the API-in-progress for automated trading strategies. The second project would involve participation in a team participating in an upcoming competition in automated bidding in sponsored search auctions. If you are interested in either project, please read/browse the material posted above and then contact Prof Kearns; be sure to indicate your programming/math/statistics/quant background.
Lectures: Tu Feb 3 Th Feb 5 Tu Feb 10 Th Feb 12	Network Science (Rev. 2/10/09)	You should start reading Duncan Watts' "Six Degrees" in its entirety. Here is Homework 1 (Rev. 2/5/09) It is due in hardcopy format at the start of class on Tuesday, Feb 17. Prof Kearns will hold office hours Friday Feb 13 from 2-4 PM in 509 Levine.	Despite my best efforts to portray "contagion" models as vast simplifications of more complex dynamics, T.A. Ted Sandler checks in with this article discussing evidence that obesity may indeed be literally a virus. Very irritating, Ted. And while we are flirting with biology, an article from F.A. Ned Shell discussing links between genes and social network formation. Here is a course-relevant talk taking place Friday Jan 30. This just in from F.A. Jason Chou: Natalie Portman has an Erdos-Bacon number of 6! Your research dollars at work. From F.A. Aditi Jain, Facebook vs. Porn. From F.A. Erin Murphy, a discussion between Laszlo Barabasi and James Fowler, two researchers whose work we discuss in NW Life. From F.A. Christian Barreiro, another entry in the never-ending debate about monetizing social networking; maybe the answer is company-specific social networks a la Nike, from F.A. Andrew Pak.
Th Feb 12 Tu Feb 17 Th Feb 19	Long Tails and Navigation (Rev. 2/19/09)	Three assigned readings for these lectures: 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. The midterm for the course will be held in class on Thursday, March 5.	A double-header from Repeat Offender Matt Berger. First, another article from the people who brought you contagious obestity, this time on the heritability of egocentric network attributes. And second (will it never end?), Erdos-Bacon-Black Sabbath numbers. From F.A. Josh Carroll, a Watts critique of Gladwell. From F.A. and T.A. Emily Pitler, origins and viral spread of the 25 Random Things About You.
Tu Feb 24	Network Science and the Web: A Case Study (Rev. 2/24/09)	Read The PageRank Citation Ranking: Bringing Order to the Web by L. Page, S. Brin, R. Motwani, T. Winograd. Parts of the following paper will be discussed in class, but it is not an assigned reading. I include it for those that might be interested in the details of the study. Graph Structure in the Web by A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopolan, R. Stata, A. Tomkins, J. Weiner. Homework 1 has been graded and will be returned in class on Feb 24; here are the solutions. The average score was 95 with a standard deviation of about 8.4, which means that people seem to have a good grasp of basic course concepts so far. The homeworks were graded by the TAs, so if you have questions or concerns about grading please see them first (Emily for problems 1-3; Bill for 4-6; Ted for 7-8). If you still have issues then you can contact me. Midterm news (remember, date is Mar 5): While there will be no formal review session for the midterm, the TAs have plenty of office hours before the exam. Please make use of them and please do not procrastinate. To help you prepare, here are the exam and solutions for 2008 and 2007.	From F.A. Frank Diebold, here is a nice Facebook app for visualizing your local network. Among other features, it appears to color densely connected subnetworks of your friends, which may often be associated with certain activities or groups. Breaking news from F.A. Matt Evans (via Facebook): Penn has lined up Google CEO Eric Schmidt as commencement speaker.
Th Feb 26	Local Incentives, Global Outcomes and Collective Behavior (Rev. 2/25/09)	Read Schelling, "Micromotives and Macrobehavior", Chapters 1, 3 and 4. (The entire book is well worth reading, but not required.)	There are two talks on campus Fri Feb 27 of direct relevance to the class. I am happy to provide extra credit for anyone who attends them and then sends me a brief (1-2 page) write-up on your thoughts and observations on the talk topics and results. Both of the talks will be pretty mathematical, but that should not prevent any of you from attending; your write-ups can simply focus on those parts you found most interesting and understood best. (As a life strategy I strongly recommend reading things and attending talks outside your comfort zones.) The first talk is at 11AM and is about models for flocking behavior in birds, which is relevant to our discussions about local behavior vs. global outcomes. The second talk is at 2PM, and is about the mathematics of the PageRank algorithm. Although the page doesn't say it, this talk is in Towne 337.
Tu Mar 3	Introduction to Game Theory and Behavior (Rev. 3/3/09)	Remember: the midterm is Thursday, March 5.	.
Th Mar 5	MIDTERM EXAM	.	.
Wk of Mar 9	SPRING BREAK	.	.
Th Mar 19 Tu Mar 24 Th Mar 26	Behavioral Network Science (Rev. 3/26/09)	There are two assigned readings associated with these lectures: An Experimental Study of the Coloring Problem on Human Subject Networks, MK, S. Suri, N. Montfort. Behavioral Experiments on Biased Voting in Networks, MK, S. Judd, J. Tan, J. Wortman. The midterms have been graded and will be returned at the end of class March 19; the mean was 76 and the standard deviation was 16. The solution and grading guidelines are here. For grading queries, please approach the TA who graded the question first: Q1 Ted, Q2 Bill, Q3 Bill, Q4 Emily, Q5 Emily, Q6 a+b Ted, Q6 c Emily, Q7 Bill, Q8 Ted. There is an interesting talk March 19; extra credit for attending and submitting a brief (1-2 pages) write-up relating the talk to course themes. More extra credit opportunities: an interesting and course-relevant talk by David Pennock of Yahoo! Research Tue Mar 24 at 3 PM. You know the drill: attend the talk, and relate it to course themes in a short (1-2 page) write-up, sent via attachment to Prof Kearns. More generally, extra credit will be provided for doing the same for any of the upcoming talks in this series. I will try to remind of the individual events, but in case I forget now you know.	The midterm seemed to elicit a mysterious slew of Fourth Column contributions, and some dedicated NWLifers were even active over the break; will try to catch up a bit here. First, in what surely is an indication that Network Science has broken through to the big time, we have a brilliant Daily Show clip from F.A. Andrew Kantrovitz. In a similar vein, F.A. Roman Pedan offers Colbert on the viral spread of... everything. From F.A. Robyn Choo, an interesting article on importing your Facebook contacts into Hulu. From F.A. Justin Charlap, one of several web sites offering to whup you at Rock-Paper Scissors. Just remember, Force Field beats God. From F.A. Adam Magee, finally, a decent use for SAT scores. And the eagle eye of R.O. Tom Prior spotted this Philadelphia Inquirer article discussing the work of yours truly, including the voting paper to the left, as well as recent work by Watts and Kleinberg. Double extra-credit and promotion to R.O. status for Aditi Jain, who managed to find this 2005 update of the 1999 empirical web structure paper by Broder et al. Thanks to R.O. Robyn Choo for vindicating my little Federer-Nadal game theory vignette.
Tu Mar 31 Th Apr 2 Tu Apr 7 Tu Apr 14	Networked Trade: Theory and Behavior (Rev. 3/23/09)	One assigned reading for these lectures: Behavioral Experiments in Networked Trade, S. Judd, MK. Here is Homework 2, due at the start of class Thursday April 9. More extra credit opportunities... first of all, there is this talk today, standard 1-2 page write-up relating to course themes. For those of you who participated in last Thursday's bargaining experiments, I will also accept a 1-2 page write-up in which you provide details on how you played, how you perceived others to play, and any other observations and thoughts you might have on the experiments. We are likely to run another session of experiments in a couple of weeks and a similar offer will be made. 4/6/09: Some important course announcements. Many of you have indicated you will be going home to family for the upcoming religious holidays. For this reason (a) there will be NO CLASS ON THURSDAY APRIL 9 (that's this Thursday), and (b) the deadline for HW 2 will be extended to the start of class Tue, April 14. Regarding (a), I normally refrain from this but we're a bit ahead of schedule compared to past years. Note that there WILL be class tomorrow (Tuesday 4/7). Regarding (b), please understand that this extension makes it likely you will have a third and final HW closely following on the heels of this one. Also, for ANY email queries on HW problems, be sure to send mail to ALL of mkearns@cis.upenn.edu, epitler@seas.upenn.edu, tsandler@cis.upenn.edu, kandylas@seas.upenn.edu. This will ensure the fastest response. Finally, several of you have asked when the final exam will be. It will be as specified in the Penn course registrar based on first class meeting --- namely, Tuesday May 5 from 9 to 11 AM. Reminder, extra credit for attending and writing up this talk on 4/7.	OK, finally some Fourth Column catch-up... From new F.A. William Green, some game theory from Hollywood: the more recent bar scence from "A Beautiful Mind", and digging (literally) into the archives, a classic scene from "The Good, the Bad and the Ugly". Clint always was one to feel lucky. Here's an entry from R.O. Clayton Gardner just a little bit ahead of its (our) time on real-world applications of Braess' Paradox. From F.A. Christian Barreiro, an application of network science to NBA teams. From F.A. Chintan Mehta, game theory at LAX. From F.A. Daniel Axelsen, an interesting and recent article on scientific interaction via clickstreams, including this visualization.
Th Apr 9	NO CLASS	.	.
Tu Apr 14 Th Apr 16	Economic Models of Network Formation (Rev. 4/16/09)	Reminder, extra-credit for attending and writing up what should be a very interesting talk April 14 by Duncan Watts. Save the Date: We are planning another round of human-subject experiments for the evening of Thursday April 23. An email call for participants will be sent shortly. As an incentive to participate, we note that subjects from the first round all made between about $44 and $72 for their efforts. Also, we expect this round to be more interesting strategically.	.
Tu Apr 21 Th Apr 23 Tu Apr 28	Internet Economics (Rev. 4/28/09)	Here is Homework 3, due in hardcopy form at the start of class Tuesday April 28. Homework 2 will be returned in class April 23. The average score was 92.5 and the standard deviation 7.9. Here are the solutions and grading guidelines; as always, for grading queries please first always visit the TA that graded the problem in question: Ted graded questions 1 and 2; Emily graded questions 3 and 5; Bill graded questions 4 and 6. Prof Kearns will hold office hours Friday April 24 from 2 to 3 PM in Levine 509. A number of you have asked for more detail about how the course will be graded. The combined homeworks, the midterm, and the final exam will each contribute 1/3 to the final course grade. Extra credit really will be extra credit: first I will assign letter grades based on the three items above, then I will potentially assign higher grades to some individuals based on extra credit. In general you should not expect extra credit to have a dramatic effect on your grade (e.g. raising it by an entire letter), but I definitely take it into consideration for students at the boundary between grade levels. Human subject experiment payments: several of you have asked about payments for the first round of human subject experiments. I apologize for the delay, but since we are holding a second round tonight (April 23) we decided to wait until we have the earnings of all subjects across both sessions to submit to the SEAS business office. Early next week I will provide detailed instructions for how to receive your payments (which involves some form-filling and providing a reliable address where you check can be mailed). UPDATE 4/28: If you participated in the experiments you should have received an email from Prof Kearns detailing what you need to do to receive payment. Please mail Prof Kearns if you did not get this email. Final exam reminder/information: The final exam will be held on TUESDAY, MAY 5 from 9 to 11 AM. The exam is CLOSED BOOK AND CLOSED NOTES and will be cumulative of the entire class, with perhaps a slight emphasis on topics since the midterm. To help you in studying for the final, here are the exams from 2004,   2005,   2006, and 2007 (this last one with solutions! ). Due to changes in emphasis over the years, not all material on these older exams may be relevant or applicable this year, but they should give you the idea. In addition to their normally scheduled office hours (see near the top of this page), the TAs will hold the following special or extended review OHs over the coming week: Emily on Thursday 12:00-1:30 in Towne 305; Bill extended office hours Monday 10:30 - 1:30 in Levine 513. Because of the class size, the exam will be split into two rooms. If your last name begins with A through L, please take the exam in Levine 101 (our normal location); if it begins with M through Z, please take it in Towne 100. COURSE REVIEWS: As you probably all know, this semester Penn has converted to an online system for course reviews and evaluations. I strive to improve NWLife every year and take your comments and thoughts very seriously, so I'd like to strongly encourage all of you to fill out the evaluations here. Here are solutions to Homework 3.	.
TUESDAY, MAY 5 9-11AM	FINAL EXAM	Because of the class size, the exam will be split into two rooms. If your last name begins with A through L, please take the exam in Levine 101 (our normal location); if it begins with M through Z, please take it in Towne 100.	.