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.
|
DATES
|
SLIDES
|
ASSIGNMENTS AND ANNOUNCEMENTS
|
COMMENTS AND LINKS
|
Lectures:
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 jinsong@seas.upenn.edu 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 jinsong@seas.upenn.edu
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.
