The Internet, 1969. 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 (such as the Penn Facebook) to reliably have, and are there "simple" explanations for them?

How does your position in a social or economic network (dis)advantage you, and why?

What might we mean by the economics of spam?

What do game theory and the Paris subway have to do with Internet routing?

What was last year's class doing in the figure at the left... and why did they each earn $100 doing it?

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

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

Brief Notes on Curriculum Requirements Fulfilled by CSE 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.


    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 (such as the Penn Facebook) to reliably have, and are there "simple" explanations for them?
    How does your position in a social or economic network (dis)advantage you, and why?
    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 2007 will be the fourth offering of Networked Life. You can get a detailed sense for the course by visiting the extensive course web pages from Spring 2006,   Spring 2005, and Spring 2004. This year the course will cover many of the same topics, updated in light of considerable new research since the 2006 offering. As has become standard in the course, we will also engage in a series of communal experiments in distributed human decision-making on networks, and analyze topics such as how network structure influences individual behavior and collective outcomes.

    Finally, this year we will introduce two new topics to the course:

  • Economic Models of Network Formation. In past years we mainly examined statistical models for how networks grow, but there is now a recent and interesting body of work on economically-inspired network formation.
  • Sponsored Search. Sponsored search refers to the paid advertisements, formally conducted as auctions or markets, that drive the bulk of Google's and Yahoo!'s revenue. Our study of sponsored search will complement our examination of Google's PageRank algorithm for "organic" search results, and will draw on material developed in Prof Kearns' seminar on sponsored search from Fall 2006.


    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.


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

    Lauren Sterensis, teaching assistant
    Office hours: Monday 12-1 in Moore 100

    Stephen Judd, experimental collaborator and system architect


    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, projected in Powerpoint that will always be made available following the lecture (but not necessarily before).

    There will be a number of 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.


    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.


    The following three books, all in paperback and on order at the Penn Book Store, are required texts for the course:

  • The Tipping Point, by Malcolm Gladwell. Paperback. Little Brown & Company, 2000.
  • Six Degrees: The Science of a Connected Age, by Duncan J. Watts. Paperback. W.W. Norton, 2003.
  • Micromotives and Macrobehavior, by Thomas C. Schelling. Paperback. W.W. Norton, 1978.

    In addition to readings from these texts, there will be frequent articles from the recent scientific and popular literature that will be provided directly on this web page at the appropriate points in the syllabus.


    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.

    Tue Jan 9
    Course Introduction and Overview
    To get a sense of a few of the course themes, read pages 37 -- 39 of the article "Economics, Computer Science, and Policy". We will return to examine the latter material on interdependent security later in the term.

    Within the first two weeks of class, you should read Malcolm Gladwell's "The Tipping Point" in its entirety. Compared with past years, we will spend less lecture time directly on this book, but 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 (Th Jan 11), as we will analyze the results of the social experiment on the fly in class.

    Th Jan 11
    Tu Jan 16
    Th Jan 18
    The Networked Nature of Society

    Burn, Baby, Burn!: Here is an illustrative forest fire demo that we'll discuss in class, and here is an even slicker one. If you do a Google search on the magic phrase "percolation theory forest fire" you can discover the not-small scientific literature on this topic.

    Kudos to Christine Farag, who is the first to receive extra credit for her contribution of the Sick Love Chart , created by one of her high-school classmates. It is apparently along the same lines as the diagram we saw documenting the romantic liasons of a high-school class, but this time the subject is Christine's own class. The visualization has a certain home-spun charm that will be lacking in many of the computer-generated network diagrams we'll see in the course; those of you thirsting for more of the same might be interested in the works of conspiracy artist Mark Lombardi.

    OK, looks like Christine has opened up the floodgates. From Jeff Weinstein we have two interesting and course-relevant links. The first is this visualization of digg swarms, in which active digg stories are shown acquiring diggs that cause them to grow in size. What I haven't figured out yet is the meaning of the links that appear when you mouse over a story, but one guess is that they represent common users digging the two stories at the end of a link. So what we seem to have here is a "bipartite" content network in which users are connected to stories they digg, and stories can be viewed as connected if they are dugg by a common user (feel free to correct my interpretation). And also from Jeff W., a fascinating first-name popularity tool. There's no network here per se, but as we'll be discussing soon, my bet is that despite the twisting fortunes of various names over time (try "Cody", "Jackson", and "Fitzhugh" for starters), at any moment the frequency in the population of the k-th most popular name is something like 1/k.

    From Shruti Shah, a nice article on network effects in marketing, which discusses research of new Wharton faculty member Shawndra Hill.

    My 5-year Old Could Have Done That (Except Maybe for the Laser Etching of the Optical Glass): In the spirit of Lombardi's network art, Li Yi found this visualization of the world's air routes by Langlands and Bell.

    Tu Jan 23
    Th Jan 25
    Contagion, Tipping and Navigation in Networks Several of you have requested office hours with Prof. Kearns, so they will be held Tue Jan 23 at 4:30 PM in 509 Levine Hall.

    This lecture is the one most closely tied to "The Tipping Point". We'll also discuss the following assigned readings:

    Read ``An Experimental Study of the Small World Problem'', by J. Travers and S. Milgram.

    Read ``An Experimental Study of Search in Global Social Networks'', by P. Dodds, R. Muhamad, and D. Watts.

    Here's a first-rate contribution from Marnee Klein. It's the is-the-new network diagram, in which there is a directed edge between a phrase X and a phrase Y if the expression "X is the new Y" appeared in recent media sources, as in "progress is the new statis" or "Bono is the new Pope". It was compiled only from 2005 articles and so is quite fragmented; Perhaps if we take a longer time period, the "giant component" we will be discussing shortly will emerge.

    From Sheng Quan, here is a nice article on heavy-tailed distributions of consumer tastes and their economic implications, and in fact an entire blog devoted to similar topics.

    The forest fire simluations from class reminded Danh Trang of the classic Game of Life, which takes place on a similar gridworld but has more interesting dynamics than simple viral spread. We'll actually return to such population dynamics simulations later when we discuss Schelling's "Micromotives and Macrobehavior". For the CS afficionados, When Prof. Kearns was an undergrad, he took a computer architecture course whose final project cruelly required him to implement the Game of Life entirely in hardware. Being a born theoretician, the result was a predictable spaghetti rat's nest of tangled wires, gated clocks, race conditions, etc. But hey, it worked, and it was a "character building" experience.

    Every once in a while, one of you may make a comment or ask a question via email that strikes me as being of potential interest to the broader class. One student did so regarding the plot of neocortex ratio vs. social group size, so I am posting my exchange with them here.

    I was thinking about one of the graphs you put up in lecture today and was quite perplexed by the inferences made. I am referring to the one which shows strong correlation between neocortex ratio and average social grp size between members of different species. I was primarily confused as to why the graph was so important.

    Well, "so important" is a bit stronger than I would venture:) --- "illustrative" or "suggestive" is probably more accurate.

    1.) The chicken and egg issue seems appropriate here - how do we know that it is not the case that, _because_ higher beings have larger heads that is why they can remember more people and thereby have larger social groups. It is not so surprising then to think about the correlation and seems almost obvious. 2.) Aren't there numerous counter-examples such as ants and birds that have larger social groups despite having smaller brains? 3.) Is there any evidence to show that there is a hidden factor involved? It seems highly random to find a correlation between two such variables and you would probably find just as strong a correlation between neocortex ratio and the capability of learning new things (eg: working memory). What Im trying to say is that maybe this is just one of the many byproducts of having a larger brain and dont fully comprehend its implications on understanding networks.

    All of your points are entirely valid --- along with chickens and eggs, I think the distinction you are making is the classic one of causation vs. correlation, informally speaking. The figure was not offered as "proof" that the neocortex grew solely in order to accomodate tracking social relationships. Indeed, it would be scientifically impossible to ever prove such a statement, in the same way one cannot prove the neocortex grew primarily to faciliate language, etc. The figure is relevant to us in the class solely to illustrate the fact that there are scientists who take seriously the idea of hard limits on our cognitive resources for tracking social relationships, and the central importance some of them attribute to these relationships, in the sense that they may have played a primary evolutionary role. I wanted to provide some more "scientific" material related to Gladwell's anecdotal Magic Number 150. As for ants as a counterexample, I suspect that Dunbar et al. are limiting their attention to groups with richer social interactions --- e.g. primates recognize each other as individuals, have complex hierarchies of power, etc.

    Th Jan 25
    Tu Jan 30
    Th Feb 1
    Tu Feb 6
    Network Science: "Universal" Structure and Models of Formation
    You should start reading Duncan Watts' "Six Degrees" in its entirety.

    Here is Problem Set 1, due in hardcopy form at the start of class on Thursday, Feb 8.

    If you feel that you are taking meticulous notes during the course lectures that would be intelligible to a third party, and would like to make a little money doing so, please contact Prof. Kearns.

    Get yer networks here, we got networks. From Rob Eroh, here is an interesting visualization of the network of character co-occurrences in the New Testament. I like this one because it highlights the fact that there are many ways one can display a network other than the standard circles and lines method. It's possible that the restriction to the New Testament has religious motivation, but it might also be to avoid all those pesky "begat" chapters in the Old Testament.

    Special thanks to Charles Li for generating this plot of the fraction of forest burned as a function of forest density from the simulation we've looked at in class. We can clearly see the tipping behavior or phase transition occurring roughly around density 0.57, where interestingly the variance also seems higher. Each point represents 5 trials, except between 5.3 and 6.2, where 10 trials were used. The claim is that as we let the grid size become larger and take more trials, the transition from nothing burned to everything burned would approach a vertical line or "cliff".

    From Mjumbe Poe, here is a just-published article on simulating the spread of avian flu that makes use of an underlying network model based on worldwide air-travel data.

    From Kim Coughlan, one of the many terrorist network visualizations and analyses that cropped up in the aftermath of 9/11. Such work is clearly interesting from a descriptive standpoint, but what about a prescriptive one?

    From William Heyer, here's an amusing missive on an artificially induced "epidemic" resulting in the introduction and spread of the word "quiz". Maybe it's shenanigans like this that cause the distribution of word frequencies to have a long tail.

    From Han Hu, here is an interesting site on a project to visualize the Gnutella network. Han was particularly struck by how challenging network layout can be. And from Xavier Ibanez, we have an article on network structure and disease spread countermeasures that is perhaps representative of a larger literature on the subject.

    In case any of you were wondering whether there are any profitable uses of network science (other than, of course, being one of the Network Science management consultants that seem to be becoming commonplace) --- Adam Erlebacher has pointed out this article on the importance of social networks in venture capital, from, of all places, the esteemed Journal of Finance.

    Th Feb 8
    Tu Feb 13
    Long Tails and Navigation

    IMPORTANT NOTICE: The first of the required experimental sessions for the course will be held Friday, Feb 16 from 5 PM sharp to approximately 7 PM. In order to receive credit you must be present for the entire session.

    For logistical reasons, we need people to sign up and commit to being present at the experiments. In order to sign up for this upcoming session, send email by Thursday, Feb 8 to with the subject line "Signing up for the Feb 16 experiments". There are a limited number of slots for each session, which will be allocated on a first-come, first-serve basis.

    Please remember that it is a course requirement to participate in the experimental sessions this term. We expect to hold a total of three sessions, and require everyone to participate in two of them. The dates for the remaining sessions are tentatively set for Mar 16 and Mar 30, but these may change in response to people's availability.

    To accompany the lecture on "Long Tails and Navigation", please read this paper on the migration patterns of dollar bills. Don't worry about understanding the math of the paper, some of which is advanced; the purpose 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.

    Every once in a while, an extra credit submission not only touches on course themes but is central to our current discussion. Thanks to Aman Agarwal for exactly such a find, which is the entire NetLogo project, which includes very nice simulations of many of the network formation models we are currently examining. For instance, here is a simulation of the Erdos-Renyi model, with special emphasis on the emergence of the giant component. We'll look at the NetLogo simulations of the Watts-Strogatz and preferential attachment models in lecture.

    Here are a couple of nice contributions from Hyung Soo Byun. First, here is one of several recent examples I have seen of visualizations of political networks, in this case conservative and liberal blogs. Somehow it reminds me of old cartoon depictions of catfights. And Hyung Soo also discovered a Wiki page on network science, which appears to have material on many of the topics we're examining. Unlike the decision of the Middlebury College history department, in this course it somehow just doesn't feel right to ban Wikipedia.

    Th Feb 15
    Experiments in Behavioral Network Science I: Coloring and Consensus

    During this essential lecture, the overall nature of this term's mandatory participatory experiments will be described at a high level, along with details of the first experimental session to be held Fri Feb 16 5-7PM. Attendance at this lecture is mandatory whether you are a Feb 16 participant or not.

    The list of confirmed participants and alternates for the Feb 16 is given here. If you are on this list, we are expecting your participation Feb 16.

    Tu Feb 20
    Th Feb 22
    Coloring and Consensus Experiments: Brief Postmortem

    Network Science and the Web

    IMPORTANT NOTICE: Due to a conflicting SEAS event, the lecture of Tue Feb 20 will be held at the usual time, but in Heilmeier Hall (100 Towne).

    IMPORTANT NOTICE: The course midterm will be held Thursday, March 1 in class. It will cover all course material to that date, including all lectures, readings, and experiments.

    Graded Problem Set 1 will be returned in class Tue Feb 20, and a solution set should be available here shortly. The average score was 89.5 (out of 100). If you have questions or concerns about the grading of your problem set, you should see the appropriate TA first (Jinsong for problems 1, 3, 4, 5; Lauren for problems 2, 6, 7). In general you should limit your queries to cases where you think an actual grading error occurred.

    As promised above, here are sample solutions and grading guidelines for Problem Set 1.

    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 is some special guest extra credit from Duncan Watts, whose group at Columbia has rolled out a new social networking service called, appropriately enough, netLife. Duncan is interested in networks that not only document links between individuals, but document the purpose or "why" of those links. He extends a warm invitation to this year's NWLifers to join and use the service, and to provide feedback for its improvement.

    Some nice contributions from repeat offender Li Yi: first, a Google Maps mashup letting you construct networks in which the vertices are streets, and the edges represent reachability. Second, a collection of articles from the Harvard Business Review, at least two of which (Watts pg. 22 and Meyer pg. 47) are relevant to course themes.

    Tu Feb 27 Towards Rationality in Networks: Behavioral Graph Coloring Read "An Experimental Study of the Coloring Problem on Human Subject Networks by M.K., S. Suri, N. Montfort.

    Prof. Kearns will hold office hours on Tue Feb 27 from 4:30 to 6 PM.

    Hyung Soo Byun is back again, this time with a nice article comparing the major search engines and their biases. Notice that it is largely written from the perspective of parties that would like to "game" organic (left-side) search results, and includes useful nuggets like "cheesy off topic reciprocal links still work great in Yahoo!". The name for the cottage industry that has emerged around such gaming is Search Engine Optimization (SEO), in contrast to the optimization of paid search results, which is called Search Engine Marketing (SEM). For a sampling of the growing academic literature on the latter topic, look here. We'll return to this topic later in the course.

    Th Mar 1 MIDTERM EXAM The midterm will begin promptly at 12 noon and will be handed out as you enter the room. It is a closed book exam, so you should put all materials other than the exam itself and a pen on the floor. The exam will stop promptly at 1:20 PM.

    To help you prepare for the exam, I have tried to consolidate as many past midterms and finals as I can find, along with solutions where they exist.

    2004 midterm, with solutions
    2005 midterm
    2006 midterm, with solutions
    2004 final
    2005 final
    2006 final

    Week of March 4 Spring Break Have Fun! .
    Tu Mar 13 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.)

    Here is the list of confirmed participants and alternates for the March 16 experiments. If your name appears in either list, we expect to see you this Friday at 3 PM, and as always be sure to be at the lecture Thursday March 15 for required background.

    Many thanks to NWLifer and extra-credit three-peater Jeff Weinstein for pointing out this very relevant lecture on collective decision-making in ant colonies, which is directly related to "Micromotives and Macrobehavior", as well as our own ongoing experiments in collective decision-making and many other course themes. This one is so relevant to the course that I will provide extra credit to anyone attending the lecture and submitting a brief write-up (2-3 pages) on it. I particularly recommend this to those few of you who are having a hard time making it to the class experiments.

    Th Mar 15
    Experiments in Behavioral Network Science 2: Kings and Pawns

    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.

    As indicated to the left, part of the March 15 lecture will be spent describing the format of the March 16 experiments. Again, knowledge of this material is required whether you are an experimental participant or not.

    The midterms will be returned in class Thursday March 15. The average score was 73 and the standard deviation about 13; here you can find solutions and grading guidelines. For discussions of grading, please see Lauren for Problems 1-4 and Jinsong for problems 5-8.

    Tu Mar 20
    Th Mar 22
    Tu Mar 27
    Some Preliminary Analysis of Kings and Pawns (updated Mar 27)

    Introduction to Game Theory and Networks

    . Believe It: the World Rock-Paper-Scissors Society and RPS-25.

    OK, some belated extra-credit catch-up. From Han Hu, a pointer to a nice collection of game theory demos, including one on generating random sequences. From Shruti Shah, further appreciation of the difficulty of graph layout can be had by playing this planarity game. And from NWLifer '06 and now Field Agent Candice Davidoff, an interesting article on hub genes.

    Th Mar 29
    Tu Apr 3
    Th Apr 5
    Tu Apr 10
    Economic Exchange on Networks The final written homework assignment for the term is an essay on the behavioral network science experiments, due on April 25. This will be discussed in class April 3. For your convenience in writing your essay, below are the consolidated and updated BNS materials; please watch for updates over the coming weeks.
  • "An Experimental Study of the Coloring Problem on Human Subject Networks"
  • Prep Material for Coloring and Consensus Experiments
  • Analysis of Coloring and Consensus Experiments
  • Prep Material for Kings and Pawns
  • Analysis of Kings and Pawns Experiments (updated Apr 10)

    Profuse apologies for the hassle, but the third and final round of experiments must be rescheduled due to technical difficulties. The new date is Saturday, April 28 from 1 PM until approximately 3 PM. This is the Saturday that falls in the middle of final exams, so hopefully many of you will still be able to make it. However, we need to re-do sign-ups, so once again to sign up, send mail to with the subject line "Final experiments sign-up".

  • .
    Tu Apr 10
    Th Apr 12
    Internet Economics . Here are some tips for your BNS analysis and essay:

    1. If you don't see a clear or interesting difference between two network structures (or something else) in a set of experiments, don't force it. It just may be that certain things didn't matter in the experiments, e.g. two apparently different network structures didn't evoke clear differences in behavior. It's important to remember that there is nothing magic about the experiments we designed --- we had to try to guess ahead of time what would be "interesting" and on some things we guessed right and others wrong. For instance, the K&P experiments definitely showed interesting differences between the two mechanisms (non-tips and tips), but less so (at least with respect to the properties we have examined so far) regarding network structure. (However, there were differences between NW structures regarding the relationship between degree and payoffs, as I will further elaborate upon today.) Between last year's experiments and this year's, there are plenty of interesting findings, so just concentrate on what the data does demonstrate, and don't sweat what it does not.

    2. Some people have asked questions about "why" the behavior in experiments was a certain way. The bottom line is that I don't know any better than you --- if I did I wouldn't have needed to do the experiments in the first place! The interpretation of the experimental results is an area where you are invited to show creativity in your analysis --- think about what interaction of NW structure, the game, and human nature might have caused whatever empirical finding you are contemplating. Just be clear in your writing to distinguish factual/statistical statements about the behavior, and your subjective interpretations of it.

    Finally, there was a request to clarify how the Rewired Clique Chain networks were generated. In these networks, you begin with the chain of 6 cliques, each of size 6. Each clique has only one member that is connected to the chain part. You then have a rewiring probability p. You go to every clique edge in the graph (that is, all edges except those that connect the cliques in the chain). For each such edge e = (u,v), you "rewire" e with probability p. Rewiring means picking one of u and v at random as the vertex to "keep" the edge, while the other will "lose" this edge. Suppose u keeps the edge; then we simply choose a new random destination vertex w from among the entire network, excluding those u is already connected to. The edge (u,v) is thus replaced by (u,w). In this way we replace "local" clique edges by "long distance" edges while maintaining the same overall number of edges in the network.

    Tu Apr 17
    COURSE EVALUATION Prof Kearns is out of town for a long-standing commitment on this date, but we will use the class session to complete course evaluations. Prof Kearns takes the course evaluations very seriously and uses them to try to improve the course each year, so please participate! While you are not required to complete an evaluation, attendance is mandatory and will be taken. .
    Th Apr 19
    Internet Economics (continued) . .
    Tu Apr 24
    COURSE REVIEW On Tuesday, April 24 at 4 PM, Prof Kearns will hold a course review in preparation for the final exam. The location is Berger Auditorium in Skirkanich Hall (the new building with green brickwork across the interior courtyard behind Levine).

    TA Office Hours during the reading period: Lauren, Monday April 23 from 12-1 and Monday April 30 from 12-1, both in Moore 100. Jinsong, Tuesday April 24 from 3:30-4:30 and Thursday April 26 from 3:30-4:30, both in GRW 571.

    Sat Apr 28
    BNS Experiments 3 The third and final round of behavioral network science experiments at will be held Saturday, April 28 at 1 PM, in the computer lab of 207 Moore. Please arrive a few minutes early if you are a participant. The list of confirmed participants and alternates will be posted shortly. Here is the list of confirmed participants and alternates for the April 28 experiments. It is your responsibility to know if you are on this list, and to appear for the experiments if you are. Please also check your email and this site regularly for further details on the experiments.
    Tue May 1
    FINAL EXAM . .


    This area contains links to web pages, demos, articles, etc. that are related to course topics. Suggestions for additions are welcome.

  • The extensive and fascinating Erdos Number Project, one of the earliest organized social network studies
  • The Complex Human Networks Reading Group at the MIT Media Lab
  • The home page of Prof. Jon Kleinberg at Cornell and a link to a related course that he teaches
  • Link to a related course of Prof. Duncan Watts of Columbia
  • Papers by Andrew Odlyzko
  • Small World Project at Columbia
  • The forest fire and viral spread demos from class (both developed by Sangkyum Kim for the Spring 2004 course)
  • The very cool Atlas of Cyberspaces by Martin Dodge and Rob Kitchin
  • The TouchGraph browsers for visualizing content networks
  • The Dartmouth Segregation Simulator
  • The Social Explorer