Professor White,
I am a high school math teacher mentoring a group of students doing an experiment concerning the emergence of clique-forming behavior using a computer simulation program (PLayer/Stage). My students started out merely wondering if clique-forming behavior could emerge from a system of individuals each following a simple algorithm based on local information. We created a simulated world of 50 robots each acting independently according to a simple algorithm (a la "Boids"). The algorithm directs a robot to approach or avoid other robots depending on the color of those robots. Eventually the robots find a stable configuration in which few, if any, robots have an incentive to move any more. Unexpectedly (for us) we found that the more heterogeneous the population of robots (i.e., the more colors of robots there were) the fewer cliques were formed and the larger the cliques were.
We think a final state with fewer and larger cliques represents a more complex and ordered state of the system of robots, and thus that we have stumbled on an experiment that is an example of greater diversity or heterogeneity leading to a more complex and ordered structure or system state. In writing up our report, we wanted to locate this experiment in the context of related work. In doing internet research towards that end, I came across the syllabus for your course "Social Dynamics and Self-Organizing Systems" and thought that our work might be of interest to you and that you might be able to refer us to some of the related works in the field that might help us understand this phenomenon better and that we might reference in our report.
We would be incredibly grateful for any advice/help.
David LeWine
I find this incredibly interesting! Congratulations to your students. Would you mind if (1) I posted this to our ongoing complex dynamics videoconference web page at http://eclectic.ss.uci.edu/~drwhite/center/cac.html#Jameson and (2) if I forwarded your very well-formed email to our mailing list of attendees for our videoconference, faculty and graduate students across 4 UC campuses, also some undergraduates taking it as a colloquium course?
You will find a paper by Delia Baldassarri (Sociology) and Peter Bearman (Sociology), Dynamics of Political Polarization, very interesting ( @ http://www.iserp.columbia.edu/research/working_papers/2006_07.html) tho a different but related problem. Am also cc:ing to Peter Bearman who may be interested in your result.
For the simulation wizards in our complexity group here is a very interesting problem. Send me proposed answers and I will post the question and the answers and authors of each to our site.
This is a high school class studying complexity and simulation; they have made a discovery and their teacher David LeWine is asking if we have any explanations.
-- Doug White
(David: this goes out to our mailing list by blind cc:)
---------- Forwarded message ----------
Please by all means feel free to share this with whoever might be interested, and we would be happy to give more detailed information on our experiment to anyone who is interested. The idea that they might contribute in any way to a professional scientific community is thrilling to my students. Thank you for that.
--David
My immediate guess is that the robots are exhausting their search preemptively. i.e., each time they find a random robot it decreasing the perceived probability to find a fit and
assuming that there is a threshold that if probability of finding a match very unlikely it is told to settle. Therefore the more heterogeneous the sample is the more the threshold
or number of trials it makes before it settles should also be increased. If not it would just settle very quickly, i.e., they all settle very quickly. Once a very unlikely pair is
formed like yellow and blue just based on sheer exhaustion of possibilities that instantly increase the likelihood that they would attract either another blue or yellow right which
could be paired with some other really weird color further increasing the acceptability of weird colors in to the clique.
I don't know if this is making sense but lets say quickly pairs are constructed that are all unlikely pairs (blue & yellow, red & green, orange & purple, etc) well instantly
they all increase the likelihood of attracting each other equally. Think in terms of atomic structure right, given free floating O (oxygen) , H (hydrogen), C (carbon), N (nitrogen)
well certain combination create new attractions to unlikely atoms right like OH will try to get other H to make water but OC will attract H,N,C,O all equally creating something
complex that wants to get even more complex like O6C2N4H12. This is strictly hypothetical and I doubt the atoms work like that but you get what I mean right? Don't they say that's
how a star begins to die is that there is a bunch of hydrogen splitting and combining between H and He over and over but as soon as the gravity is strong enough to compress the atoms to crate a heavier element such as Oxygen instantly that Oxygen start attracting all sort of H and He to create every heavier elements thus perpetuating the growth of a single mass. It's Keplar's laws of mass and attraction that are the basis of how the increased mass increases the attraction.
This equally explains why it works in the opposite direction when the colors are fairly homogeneous because they find appropriate pairs and settle down quickly there for the number of cliques are basically a matter of the population highly competing for complementary pairs equally, i.e., (red & red pair 1, and red & red pair 2) are all try to grab the remaining isolate reds as fast as they can and once they have they don't share because their nature is to take and not give. Sort of the atom example above but instead we only have H, and He and so it will just quickly form combinations of H2 and He and be happy and stop. Leaving us with a lot of small compound elements but only basic ones.
Well that's my take on it. I don't exactly know how the program works to be sure.
-Nam
Interesting! To get involved in advancing an opinion, I- personally - would need more information on the range of final configurations. Also, on the transition configurations for the intermediary steps
between fewer and more colors.
Paul (Jorion)
Doug,
Mathematically, the students have formulated a search problem ("find a
configuration in which no local, small perturbations produce a better
result"). This is a form of optimization problem ("find a
configuration of locally maximal happiness"). High-dimensional
optimization problems are notoriously difficult to solve from a
computational viewpoint. One of the banes of optimization is the
existence of "local" minima (or maxima, depending upon how you phrase
the optimization problem) that are substantially less optimal than the
*global* minimum. If you pretend that the function you're trying to
minimize is "energy", then the energy landscape for complex functions
(like the one the students are trying to optimize) is very hilly---
there are hills and valleys all over the landscape. In such problems,
it is always easy to find a *local* minimum (to "find the bottom of the
nearest valley", you just keep walking downhill until you get to a
place where every direction leads uphill). But finding the *global*
minimum ("find the absolute lowest place in the San Bernardino
mountains, given that you have no map and can only walk around using
your feet") is extremely difficult. Furthermore, it is usually
impossible to know how "good" your local minimum is to the global
minimum---the global minimum could be far away in the landscape, and
you have no way of knowing if you're almost as low as the lowest point,
or if the lowest point is *much* lower than your current local
minimum.
Type "Global Optimization" into Google and surf around for awhile
to see more about such problems.
My guess is that more heterogeneity in the network simply makes the
optimization problem harder to solve, and the students are finding
local minima, rather than global minima. I expect that the results
might be quite sensitive to such paramaters as
2) the "satisfaction" threshhold above which a robot is satisfied with
its current position. If the threshold is set low enough, one huge
clique would form, independent the configuration. A high enough
threshold would force the robots to keep trying to find a better
position---but this increases the amount of CPU time required to
solve the problem.
So, although the students have an interesting problem, I would
encourage them to explore the *parameter* space more thoroughly before
attempting to draw socially significant conclusions.
[*parameter* substituted for *search* in later email]
--
My interest in this kind of question at this time, as in our Social Circles
(http://en.wikipedia.org/wiki/Social-circles_network_model) aka generative Feedback Model for
complex networks, is in the kind of John Holland approach, and then some, taking the simplest set of processes necessary to generate a range of realistic outcomes,
build a generative probability function with parameter exponents, run the simulation varying those exponents, and then analyzing properties of the outcome networks
to get outcome parameters. Then to plot the outcome parameters as a function of the input parameters and vice versa. Possibly there is a 1-to-1 correspondence.
If so, you have a theoretical model that can serve as one possible theoretical explanation for analysis of real networks that have a parameter fit to the outcome model. This
is really intriguing because it can suggest exactly and quasi-analytically what the relation is between the theoretical model and the empirical world. The wikipedia site (at
the link above) describes these kinds of results from generative Feedback Model.
So my question to class members is whether you can think of a probabilistic geneerative network model that would duplicate your results? And once we know the outlines
of your simulation processes, can others do the same, i.e., are there competing models beyond what can be done with varying parameters in a single model?
This approach might also cut through the difficulties described by Wayne Hayes.
Dear David,
What a great project for HS students -- and all of us. I think you
should take a look at Simmel, esp. the essay on individuality and
group expansion. You should find there a wealth of corroborating
theoretical suggestions. All best
Peter
Doug,
Let me re-phrase my anwser in a much less abstract way. I'm going to
examine two variation of a similar problem. Assume we have a large,
dark room filled with 1000 people.
In the first variation, there are 500 people each from two different
rival high schools. Here I use "rival" to mean that people only want
to speak to each other if they're from the same highschool. In this
case, there are only two colors of "robots", and so any robot will very
easily be able to find a robot of the same color nearby, and this will
naturally lead to clique-forming. Eventually, we'll get to a point
where there are small clumps (say, 10-20 people each), where each clump
(clique) consists of robots of only one color. The general level of
happiness in such a crowd will be high---each student will be surrounded
by students from their own high-school, and students from the other
high-school will be far enough away not to be of concern. Since the
room is dark and crowded, it will be difficult for the cliques to
get much larger, because it would require moving entire sets of
large groups around---and furthermore, it might be difficult to even
*see* the next nearest group of the same colour (the room is large
and dark), and since everybody is reasonably happy with the current
configuration, there is no strong incentive to continue making
larger cliques.
The above situation models the case of just two colors, leading to
a large number of small cliques.
Now, the other situation: rather than two high-schools, we simply
have a 1000 people in a dark room, but the people are actually 250
four-person families: a mother, father, and two children. *HOWEVER*,
all 1000 people are scattered randomly, so that no family is actually
together. In this case, there are 250 colors, and every person is
surrounded only by people of random different colors. (We assume,
like in the robot model, that people are not allowed to make new
friends---colors do not mutate, or merge together.) Since the room
is dark and crowded, it is highly unlikely that anybody will be able
to see any other family members. Thus, nobody has any clue which
direction they should walk in order to find a member of their own
family. We end up with a single, large, diverse, "clique". HOWEVER,
the level of general happiness will be quite low in such a crowd.
So, my question to the students is: if you model something similar
to "happiness", then you should compare the level of "happiness"
in the above two situations. If you *don't* measure something analogous
to "happiness", then you need to add it to your model in order to draw
meaningful conclusions.
A final note: the major differences between this model and real life
are that, in real life, colors might tend to merge together after
awhile (people *can* become tolerant of each other). The current
model does not allow this. A parameter that would control the
merging of colours might be called "pig-headedness": the higher
the pig-headedness, the less likely colors are to merge, and the
longer the general unhappiness will linger. Lower the pig-headedness,
and colors merge, leading eventually to greater happiness.
--
Outstanding! (this too now at the website)
Wayne has now has captured aome of the logic from Boids, developed by Craig
Reynolds in 1986, and it has the flavor too in part of Schelling's
segregation model, which to quote from Wikipedia, is this "In 1971, he
published a widely cited article dealing with racial dynamics called
"Dynamic Models of Segregation". In this paper he showed that a small
preference for one's neighbors to be of the same color could lead to total
segregation" i.e., to large cliques. He has the happiness parameter, more
or less. Have your students see
http://en.wikipedia.org/wiki/Thomas_Schelling
They (WP) say there also "Schelling's most famous book, The Strategy of
Conflict (1960), has pioneered the study of bargaining and strategic
behavior and is considered one of the hundred books that have been most
influential in the West since 1945. In this book he introduced the concept
of the focal point, now commonly called the Schelling point." So here are
some good readings for your students.
[Added Sat, 28 Apr 2007 14:41 (PDT)] *But* there is an important caveat. Schelling's
segregation model was intended to show that evey a tiny amount of preference for
homogeneity in a market for housing, for example, could lead to maasive unintenational
segregation. This might suggest as a policy issue that incentives are needed to avoid racial segregation.
If you add a parameter called *happiness* that assumes that it is homogeneity
that makes people 'happy', as in the family example, then the simulation is assuming the consequent,
and the optimization may becomes trivial or misleading. A 'happiness' parameter could equally well
reflect positive value for heterogeneity. So perhaps the view that designing an
optimization for one or another assumption about 'happiness' is not what is interesting
about a simulation of clique-formation. It is often of more interest if the outcome that
comes out is counter-intuitive or non-obvious.
Hello David,
Douglas White forwarded your email...
You might be interested in the 200+ simulations that we have on our website:
http://gessler.bol.ucla.edu
If you have a simulation that you would like me or my class of students to write,
please send us the details and we'll see what we can do. No promises, but depending
on its difficulty and the time we have available, we might be able to oblige...
Now on to your question:
I think it would be a great "challenge" for my students to help your students!
Cheers,
Nicholas Gessler, Ph.D.
I found the comments and suggestions posted so far, on a first quick glance, very interesting and very helpful. I will be especially interested to look at the Schelling article "Dynamic Models of Segregation." We had wondered what the effect of increasing the probability that a robot would like his own color and decreasing the probability that a robot would like other colors would be. Specifically we wondered how much the probabilities would have to be adjusted before the inherent organizing effect of diversity was overcome to a significant degree.
Here below is more detailed description of our simulation. Add it in where you think best. When I get back to school I would be happy to provide even more information: anova test results of our data; screen shots of trials (we have lots of shots of final states, but could easily run some trials to take shots of intermediate states); and even the C++ code for the control program and anything else (answers to specific questions?) that you think would be of help.
We used the Player/Stage software to simulate 50 colored robots in a bounded world that are attracted to or repelled by each other depending on their
color and color preferences; each robot's control program is the same. A robot's color preferences are set randomly. The probability that a robot will like robots of a given color is .5. A robot's preference for a color is independent of its preferences for other colors and independent of the robot's own color; each robot's preferences are independent of the other robots' preferences. Thus a robot might like no robots (it dislikes all colors), it may like all robots (it likes all colors) or it may have any combination of color preferences in between. For example if there are five colors of robots, one green robot might like red, blue and yellow robots and dislike green and purple robots while another green robot might only like green robots.
Robots have a camera that can track color-blobs. The camera points in the direction the robot is facing and has a field of view of about 90 degrees. Robots react only to the largest blob in their field of view. Because the robots are all the same size and are roughly square, the largest blob will usually represent the closest robot in its field of view. If the largest blob is a color that the robot likes, it will turn towards that blob, and if it is a color the robot does not like, it will turn away from the blob. If there are no blobs in its field of view it meanders randomly. The robot's motion is controlled by setting its velocity and turn rate. The robots have proximity sensors at their forward corners that together give them a 180 degree field of view. If a robot detects that it is close to other robots, its velocity will decrease. If it is very close (within a set minimum distance) to another robot its velocity is set to zero. Robots continue to turn even if their velocity is zero. A robot will cease moving if a) it is very close to another robot and b) the largest blob is of a color it likes and is centered in its field of view.
We ran each trial for seven minutes. This was enough time for the system of robots to reach a fairly stable state. A group or clique was defined as a set of connected robots where two robots are connected if the distance separating them is less or equal to the set minimum distance. The world over which the robots roamed was finite but large enough so that it was very unlikely that, when the simulation ended, a robot that was still roaming freely would be counted as part of a clique.
We ran 25 trials each with 1, 2, 5 and 10 colors of robots and found that as the number of colors increased, the average number of cliques decreased and the average size of the largest clique increased. For each set of trials, the robots' initial location, orientation, and color were the same for each trial. What varied was the robots' color preferences.
One understandable consequence of the nature of our simulation is that robots tended to form chains: robot 5 liking and hence following robot 4, robot 4 following robot 3, robot 1 searching and trailing the rest behind. A chain will come to rest when it meets another chain head on or when it intersects a chain already at rest. Thus cliques usually have a branching structure.
--David
Hi David,
There is an interesting article in the March 17th, 2007, issue of New
Scientist on prejudice, which summarizes a paper by Ross Hammond and Robert
Axelrod (http://intl-jcr.sagepub.com/cgi/content/abstract/50/6/926). In a
world of agents of different "colors", and given a choice of cooperating or
cheating when two agents interact, they asked which of several strategies
would be most successful--ignoring color (and acting either randomly, or
consistently cooperating or cheating); cooperating with those of same color
and cheating those of another color ("ethnocentrism"); cooperating only with
those of another color. Apparently, their findings were that "ethnic"
groups of homogeneous color emerged, and that ethnocentrism was the most
successful strategy.
Personally, I'm interested in the problems of replicating agent modeling
results between researchers. If you and your students would be willing to
send me your model and results files, I'd spend some time seeing if I can
replicate your results. I don't have an opinion yet as to whether these
results are "right" or "wrong", but I'll tell you what I find.
Congratulations to you and your class on undertaking this experiment. I
think you are at the very leading edge of something I hope becomes part of
our educational system in the future -- the use of simulations to help us
understand social behavior.
regards,
Steve Doubleday
UC Irvine, IMBS
Date: Fri, 27 Apr 2007 20:57 (PDT) -0700
From: David L
To: Douglas R. White
Subject: re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior
Date: Sat, 28 Apr 2007 00:20 (PDT) -0700
From: Namanh Vu Hoang hoangnv @ uci edu (college senior)
Date: Sat, 28 Apr 2007 06:14 (PDT) -0700
From: pauljorion @ ucla.edu
To: Douglas R. White
Cc: David L
Subject: re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior (fwd)
To: Douglas R. White
Date: Sat, 28 Apr 2007 11:24 (PDT) -0700
From: Wayne Hayes
1) the distance that robots are allowed to "see"---increased distance
will allow them to better optimize and find more robots of the same
colour
Wayne Hayes, Assistant Professor, 360D Computer Science Department,
University of California, Irvine, CA 92697-3435
e-mail: wayne @ ics uci edu; Office Phone: +1-949-824-1753
"Science is an all-pervasive energy, for it is at once a mode of thought,
a source of strong emotion, and a faith as fanatical as any in history."
-- Jacques Barzun, _Science: The Glorious Entertainment_
Later sent as an email Sat, 28 Apr 2007 11:30 (PDT) From Doug White
Date: Sat, 28 Apr 2007 15:48 (12:48 PDT) -0400
From: PSB17 @ columbia.edu
To: Douglas R. White
Cc: David L
Subject: re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior
From wayne @ ics.uci.edu Sat Apr 28 13:15:46 2007
Date: Sat, 28 Apr 2007 11:59 (PDT) -0700
From: Wayne Hayes
To: Douglas R. White
Subject: Re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior (fwd)
Resent-Date: Sat, 28 Apr 2007 11:59:50 -0700
Resent-From: Wayne Hayes
Resent-To: drwhite @ orion.oac.uci.edu
Wayne Hayes, Assistant Professor, 360D Computer Science Department,
University of California, Irvine, CA 92697-3435
e-mail: wayne @ ics.uci.edu; Office Phone: +1-949-824-1753
"Science is an all-pervasive energy, for it is at once a mode of thought,
a source of strong emotion, and a faith as fanatical as any in history."
-- Jacques Barzun, _Science: The Glorious Entertainment_
Date: Sat, 28 Apr 2007 13:38:26 -0700 (PDT)
From: Douglas R. White
To: David LeWine
Date: Sat, 28 Apr 2007 14:41 (PDT) -0700
From: Nicholas Gessler
To: David L
Cc: Douglas R White
Subject: high school computer simulation experiments
Click on "Simulation."
They should run on any PC...
You might want to look at our "Segregation" section since it seems close to what you're doing.
I would really need to know PRECISELY what the parameters are for your simulation.
Is this a cellular world or a vector (can move in ANY direction) world?
How do your agents move? Square by square, or any direction to any distance?
How do they detect what is in their neighborhood? What shape and radius is their neighborhood?
Nick
"ALiCE - Artificial LIfe, Culture and Evolution."
UCLA Human Complex Systems Program
From davlew@mac.com Sun Apr 29 09:22:11 2007
Date: Sat, 28 Apr 2007 22:38:25 -0700
From: David L
To: Douglas R. White
Subject: Re: http://eclectic.ss.uci.edu/~drwhite/center/LeWine.html
Description of the clique forming simulation
Date: Sat, 28 Apr 2007 22:43:15 -0700
From: steve@lesscomputing.com
To: Douglas R. White
Cc: David L
Subject: Re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior