Missing Image
  Missing Image
  Missing Image
  Missing Image
  Missing Image

  • What science underlies these companies?
  • How might a social network influence election outcomes?
  • 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?
  • What structural properties might we expect any social network to have?
  • How does Google find what you're looking for...
  • ...and exactly how do they make money doing so?
  • Why do some people spend their time anonymously correcting punctuation on Wikipedia, without compensation or recognition?
  • How does your position in an economic network (dis)advantage you?
  • How are individual and collective behavior related in complex networks?

    Networked Life looks at how our world is connected -- socially, strategically and technologically -- and why it matters.

    (Jump to the course schedule. )

    CIS 112
    Spring 2010
    Tuesdays and Thursdays 12-1:30 PM, Levine Hall 101
    Prof. Michael Kearns

    Brief Notes on Curriculum Requirements Fulfilled by CIS 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 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 is cross listed as a course in the Philosophy, Politics and Economics (PPE) major.
  • Networked Life is approved as an elective course in the Science, Technology and Society (STSC) major.


    Networked Life looks at how our world is connected -- socially, economically, strategically and technologically -- and why it matters.

    The answers to the questions at the top of this page 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).

    Spring 2010 is the seventh offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from Spring 2009,   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.


    The following four books, available at the Penn Book Store, are required texts for the course:

  • The Tipping Point, by Malcolm Gladwell. Paperback. Little Brown & Company, 2000.
  • Connected, by Nicholas A. Christakis and James H. Fowler. Hardback. Little Brown & Company, 2009.
  • 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.


    Prof. Michael Kearns
    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.


    Kareem Amin, teaching assistant
    Office hours: Fridays, 1:30 - 3:00

    Mickey Brautbar, teaching assistant
    Office hours: Tuesdays, 1:30 - 3:00

    Office hours for both TAs will be held in the lounge area on the 5th floor of Levine Hall. Take the elevators up to 5, go down the ramp and take a right at the bottom; the lounge area is halfway down the hall on your left.


    Attendance at the main lectures is considered mandatory for enrolled students. They are held Tuesdays and Thursdays 12-1:30, Levine Hall 101.


    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.


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

    There may also be participatory social experiments and exercises.

    There will 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 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.


    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.


    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, "C+F", "Gladwell", "Watts" and "Schelling" refer to the four 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.

    Th Jan 14
    Course Introduction and Overview
    (Rev. 1/14)

    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. If you want to get a jump start, begin reading "Connected" by C+F immediately afterwards.

    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 19), as we will analyze the results of the social experiment on the fly in class.

    Be the first Field Agent of the term!

    Tu Jan 19
    Th Jan 21
    Tu Jan 26
    Contagion, Tipping and Navigation in Networks
    (Rev. 1/28)

    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.

    Update 1/25: I have been told by the Penn Bookstore that "Connected" should now be in stock on the shelves; please let me know if you don't find it there.

    And we have winners! First-to-Field-Agent honors go to Thomas Abel for pointing out this Penn lecture by Tipping Point author Malcolm Gladwell on January 28; to Zac Costlow for this article on the use of social networks for information about Haiti; and to Stephen Guss for this NYT article on technology-induced generation gaps. I somehow find this last one especially disturbing. Keep 'em coming.

    IMHO, this example of contagious behavior by newly minted Field Agent Thomas Boutin takes the all-time NWLife prize for most entertaining Fourth Column submission. Plus it so nicely illustrates certain course themes: the importance of both individual behavior and collective dynamics in group formation; the rate of adoption of new technologies and activities; tipping and cascades; etc. Not to mention the patience and foresight of the videographer --- you'd have thought 30 seconds of this would have been plenty, but no. Finally, keep your eye on the woman in yellow apparently applying sunscreen for most of the time. Priceless stuff all around.

    From F.A. Louis Bergelson, the Wikipedia game.

    To his already distinguished career as a Benchmark Capital founder, CEO of the startup Kaching, and chair of the SEAS Board of Overseers, Andy Rachleff adds what may be his highest honor yet: NWLife Field Agent. He checks in from out West with the very cool We Feel Fine project.

    Not sure what's in the air out in Silicon Valley these days, but everyone's checking into the Fourth Column. From seasoned-technology-exec-and-now-Field-Agent Danny Shader comes this fascinating article on slime mold growing the Tokyo subway (and yes, that's actually just "growing", not "growing in"). For the interested, here is the source article.

    I've posted these in years past but they are worth checking out if you've not seen them before: Facebook Friends Wheel (courtesy of F.A. Zachary Wasserman) and TouchGraph's Google,   Amazon, and Facebook browsers (courtesy of F.A. Kunal Kandimalla).

    From our first Repeat Offender Stephen Guss, a NYT piece on Google search completion winners, whose logical conclusion is "vanity search completion", first brought to my attention by the inimitable Chris Dixon.

    Th Jan 28
    Tu Feb 2
    Th Feb 4
    Universal Network Structure and Generative Models
    (Rev. 2/4)

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

    You should be reading "Connected" in parallel; much of it is related to ongoing course topics, and I would estimate that we'll discuss it in more detail in a couple of weeks or so.

    We have a slew of new Field Agents today. From James Katz, the White House visitor network. From Brynn Shepherd, weak ties and "consequential strangers". From Tony Zheng, the Pope pushes Facebook. From Aurelien Meunier, the PoliticoSphere. From Rebecca Sussman, the Sotu Spinner.

    And from F.A. Hillary Reinsberg, Internet Famous at Parsons, the first "algorithmically graded class" (not so sure about that claim). Of course, as we shall eventually discuss, the real key to a good grade here is probably a first-rate SEO and SEM campaign.

    From R.O. and FoNWL (Friend of Networked Life) Kim Kearns, an NPR story on peer-produced pricing pressure in China (a.k.a. "tuangou"), another modern example of disintermediation.

    Tu Feb 9
    Th Feb 11 (snowed out)
    Tu Feb 16
    Th Feb 18
    Long Tails and Navigation
    (Rev. 2/18)

    Here is Homework 1 (revised 2/12, fixed bugs in Problems 1 and 5), due at the start of class Tuesday Feb 23 in hardcopy form.

    The TA office hours have moved location to the 5th floor lounge area of Levine Hall; see directions above.

    Professor Kearns will hold office hours on Monday, February 15 at 4PM in 509 Levine.

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

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

    Navigation in a Small World, Kleinberg.

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

    TA Mickey Brautbar's office hours have been moved half an hour earlier, to Tuesdays at 1:30.

    The midterm examination will be held in class on Thursday March 4.

    I will provide extra credit to anyone who attends a lecture in the ongoing Market and Social Systems Engineering series, and submits a brief (about one page) write-up about it. Send them to Prof Kearns as attachments via email with the subject like "MKSE lecture write-up". You can do as many of them as you like.

    Like the snow, our Special Forces are piling up faster than I can shovel. From F.A. Shawn Chen, Web 2.0 suicide. How do I politely suggest this to some of my FB friends? And Shawn immediately earns promotion to R.O. with the spam that is social. From R.O. Tony Zheng, the many dangers of social media. From F.A. Troy Shu, All Your Meme Are Belong to Us. From F.A. Spencer Lance Hopkins darkened Twitter avatars down under. R.O. Zachary Wasserman is back with the Human Diseasome. F.A. Jay Fiddelman debuts with an extensive Economist report on social networking. From F.A. Rodrigo Abreu, yet another structural measure of importance. From F.A. Shubhi Nigam, Internet Nominated for Nobel Prize. The article has enough typos to make me suspicious but I support the nomination only so that in its acceptance speech, Internet can thank Al Gore for inventing it.

    Today's Entertainment Award goes to F.A. Sam Pasternak, who channels Honorary R.O. Stephen Colbert in the last Word on social networking and blippy.com

    A number of you noted the introduction of Google Buzz, the latest purported Facebook-Twitter-Etc destroyer, but whose features and functionality were supplanted in the news by the buzzkill over privacy snafus. You'd think they'd have thought this through a little more carefully out there in Mountain View. I haven't tried it yet, but it does bring to mind a funny story about my gmail account and Pizza Hut...

    I ran into now-F.A. Anyu Dai at a Philadelphia Orchestra concert on Saturday, and later she wrote about the tipping phenomenon of standing ovations at such events, as well as my own insect-like participation. It got me thinking that this is such a natural problem it must have been studied before, and indeed it has. As always, there's nothing new under the sun.

    From F.A. Peng Fei Chen, use twiangulation to understand your cwustewing cwoefficient. From F.A. Allison Mishkin, a domestic version of the aforementioned concept of "tuangou" at GroupOn. From F.A. Alice Lee, a cool network visualization of time travel in the movies.

    Tu Feb 23
    The Web as Network: A Case Study
    (Rev. 2/25)

    Related articles:

    Graph Structure in the Web, Broder et al.

    Web Structure in 2005, Hirate, Kato, Yamana.

    Extra credit opp: for attending and submitting a brief write-up of this talk by Internet pioneers Kahn and Cerf, winners of the 2010 Pender Award.


    Th Feb 25
    Network Structure and Web Search
    (Rev. 2/25)

    Everyone should read this excellent article on Google's search algorithm from the current issue of Wired. (Note that it is three pages long.) It emphasizes the point that PageRank --- one of the main topics of this lecture --- is now but one small piece or "signal" in the overall algorithm. Thanks to several unnamed F.A.s for pointing it out.

    The following two articles are directly related to the lecture material, but are not required; they are just posted for the curious and/or mathematically inclined.

    Authoritative Sources in a Hyperlinked Environment, J. Kleinberg.

    The PageRank Citation Ranking: Bringing Order to the Web, L. Page, S. Brin, R. Motwani, T. Winograd.

    A bit of Fourth Column catch-up. From R.O. Thomas Abel, the latest social web entry, Strings. From F.A. Amanda Smith, contagion via touching. And from F.A.s Andrew Lum, Jonathan Schwartz and Yash Mittal, chatroulette and its 17-year-old founder in Moscow. From R.O. Brynn Shepherd, Steve Strogatz on negative connectivity. From R.O. Rodrigo Abreu, Please Rob Me.

    Tu Mar 2
    "Connected" At Last
    (Rev. 3/2)

    March 2: Here are solutions and grading guidelines for Homework 1, written by Kareem and Mickey.

    In this lecture we will (finally) go over some of the themes explored in the book "Connected". In service of this goal, here are links to the Christakis and Fowler papers on happiness,   loneliness,   obesity, and smoking. We will mainly discuss the yellow highlighted portions of each.

    Th Mar 4

    The midterm will cover material for the entire course so far, all the way through the March 2 lecture. The exam is closed books --- no books, notes, devices, etc. are permitted.

    In preparation for the midterm, Prof Kearns will hold a Q&A session on Tuesday March 2 at 3 PM in Berger Auditorium of Skirkanich Hall. Skirkanich Hall is the building across the courtyard behind Levine Hall, and Berger Auditorium is on the basement level. Please come prepared with your questions about course material.

    To help you study for the midterm, here are midterms with solutions from 2009,   2008,   2007, and 2006. Please be aware that the material covered in class has varied slightly from year to year, so there are questions on these exams which I wouldn't expect you to be able to easily answer. (And a good test of your understanding of class material is that you'll immediately recognize such questions.) There are also some missing figures.


    Tu Mar 16
    Incentives and Collective Behavior
    (Rev. 3/15)

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

    From Yours Truly, another hilarious Colbert segment, this time on the start-up Kwedit. (Full disclosure: I am an advisor to them.) From F.A. Yiyi Zhou, the twitter grader. From F.A. Scott Thorn, the South Korean sausage epidemic. From F.A. Jay Paik, Facebook diplomacy. From R.O. Rodrigo Abreu, more network inspiration from Mother Nature. From F.A. Ran Wei, Internet vigilantes in China.

    Th Mar 18
    Introduction to Game Theory and Strategic Behavior
    (Rev. 3/18)



    Tu Mar 23
    Th Mar 25
    Tu Mar 30
    Behavioral Experiments in Network Science
    (Rev. 4/1)

    There are three 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.

    Behavioral Conflict and Fairness in Social Networks. S. Judd, MK, Y. Vorobeychik.

    Midterms will be returned in class March 23, and available afterwards from Cheryl Hickey in Levine 502; here is the solution set. The average score on the midterm was 70, with a standard deviation of 15.

    Lots of great Fourth Column material lately, thanks to all and keep it coming! From F.A. Peng Fei Chen, the Twitter Predictor Game from Hunch, which I will describe and demo in class. From F.A. Jason Gui, a cool location-based media sharing iPhone app named LoKast, which Jason helped to launch. From R.O. Zachary Wasserman, In Praise of Obscurity. A double-header from R.O. Shawn Chen: the latest from our friends C+F. and online status anxiety. From F.A. Scott Biddle, network science for Brazilian hookers. From F.A. Yiyi Zhou, the Chatroulette Map.

    Th Apr 1
    Tu Apr 6
    Th Apr 8
    Tu Apr 13
    Trading in Networks
    (Rev. 4/13)
    Save the Date! It looks like we are planning the first of two or possibly three sessions of behavioral experiments in network formation games for the evening of Friday April 23. Details about signing up as a participant will be coming shortly.

    Here is Homework 2, due as hardcopy at the start of class on Tuesday, April 27.

    Breaking news from R.O. Jay Fiddelman: a Slate article surveying doubts about contagion research. Haven't read it yet, but looks highly relevant. From R.O. Ann Dai, data artist Stefanie Posavec. From F.A. Noah Fox, Twitter box-office and sleeping predictions. Here is a related article. From F.A. Dan Markowitz fiverr.com, a kind of Five Below of online labor markets.

    At long last, a revenue model for Twitter: monetization via Promoted   Tweets.

    Th Apr 15
    Tu Apr 20
    Strategic Models of Network Formation
    (Rev. 4/15)



    Tu Apr 20
    Behavioral Experiments on a Network Formation Game
    (Rev. 4/22)

    The first session of behavioral experiments in network formation games will be held Friday, April 23. We are also planning sessions on Thursday, April 29 and Monday, May 3. Calls for participants in the second two sessions will be sent out via email 4/21.

    UPDATED 4/21: It is now a course requirement counting towards your final grade that you participate in the experiments in one of two ways. If you participate as a subject in one of the sessions, that will fulfill your experimental requirement. If you do not participate as a subject, you will instead write an essay in which you will be asked to speculate and predict about various aspects of the experiments; details will be forthcoming.

    In the 4/20 lecture I will describe the basic set-up of the experiments, the payoffs or incentives, and the GUI. This information will be repeated at each session itself, and is necessary background for both the experiments and essays.

    Today at 3 PM there will be a talk by Prof. Ed Lazowska of the University of Washington on the future of computer science, which I suspect will be excellent and touch on some course themes; extra credit for attending and writing up a brief report as usual.

    Th Apr 22
    Tu Apr 27
    Internet Economics
    (Rev. 4/22)

    Update 4/27: By now (4/27) we have sent email to everyone selected as a regular participant for the final two experimental sessions on 4/29 and 5/3. If you did not receive such an email, you must instead complete a short essay assignment, which is described here. It is due May 11. See the assignment for details.

    Homework 2 is due in class today (4/27).

    Please complete an online evaluation for the course! Your feedback is taken seriously and influences the evolution of the course.

    One last round of Fourth Column; thanks to all of you who contributed this semester, even if I didn't post them all.

    From R.O. Alison Mishkin, the Radiohead approach to wine bars. From R.O. Zac Costlow, Twitter stupid fight. From R.O. Hillary Reinsberg, the electricfoxy facebook ping test (bonus: guess the Sixties reference). From F.A. Daniel Baume, browser blackmail. (Why didn't I think of this?) From R.O. Shawn Chen, more uses of Where's George. From F.A. Andrew Braunstein, the marketing genius of the Grateful Dead.

    And finally, we come full circle: from R.O. Zachary Wasserman, a TED analysis of the Sasquatch dance.

    MAY 11 FINAL EXAM The final exam will be held Tuesday, May 11, 9-11 AM, in Meyerson Hall B1. It will be cumulative of the entire course. We will hold some extra office hours and a review session before the exam.

    UPDATE 5/3: We intend to get your HW2s graded and back to you in time to help you prepare for the final; details as they emerge. Second, a reminder that the final is *cumulative* --- everything from the entire course is fair game. There will be perhaps slightly greater emphasis on material since the midterm, but not significantly so.

    I will hold a review session on Friday, May 7 at noon in Berger Auditorium in Skirkanich Hall. Skirkanich is the building across the courtyard right next to our usual auditorium; Berger is in the basement there. As with the midterm review, I will largely let the review be driven by questions from the audience, with perhaps some chronological structuring. I will go for a couple of hours or until your questions are exhausted, whichever comes first.

    TAs Mickey and Kareem will also hold extra office hours this week; note that these *differ* from their usual office hours in order for us to get some good coverage across the week.

    TA office hours this week:

    Tuesday 1:30-3pm (Mickey)
    Wednesday 1:30-3pm (Kareem)
    Thursday 1:30-3pm (Kareem)
    Friday 2:30-4pm (Mickey)

    All OHs will be held at their usual spot for the respective TA.

    UPDATE 5/7: Here are Homework 2 solutions. The average score was 82, and the standard deviation 13. As usual, see the TA who graded a particular problem for grading inquiries.

    UPDATE 5/9: Here is a sample final with solutions from 2007.

    Enjoy your summer!