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 ----------
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
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 O_{6}C_{2}N_{4}H_{12}. 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 search space more thoroughly before attempting to draw socially significant conclusions.
--
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_
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.
--
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_
Outstanding! (this too now at the website)
Wayne has now has captured your 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.