re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior
  • On Fri, 27 Apr 2007, at 09:45AM, David LeWine wrote:

    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


    On Friday, April 27, 2007, at 10:26AM, "Douglas R. White" wrote:

    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.


    Date: Fri, 27 Apr 2007 at 22:27 (PDT)
    From: Douglas R. White
    To: Complexity Group, David L
    Subject: re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior (fwd)

    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


    Date: Sat, 28 Apr 2007 00:20 (PDT) -0700
    From: Namanh Vu Hoang hoangnv @ uci edu (college senior)

    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


    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)

    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)


    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)
    Date: Sat, 28 Apr 2007 11:24 (PDT) -0700
    From: Wayne Hayes

    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

      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

      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]

    --
    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

    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.


    Date: Sat, 28 Apr 2007 15:48 (12:48 PDT) -0400
    From: PSB17 @ columbia.edu
    To: Douglas R. White
    Cc: David L , douglas.white @ uci.edu
    Subject: re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior

    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


    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

    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_



    Date: Sat, 28 Apr 2007 13:38:26 -0700 (PDT)
    From: Douglas R. White
    To: David LeWine , Wayne Hayes

    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.


    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

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

    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 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?

    I think it would be a great "challenge" for my students to help your students!

    Cheers,
    Nick

    Nicholas Gessler, Ph.D.
    "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

    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.




    Description of the clique forming simulation

    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


    Date: Sat, 28 Apr 2007 22:43:15 -0700
    From: steve@lesscomputing.com
    To: Douglas R. White
    Cc: David L , Douglas R White
    Subject: Re: "the key to complexity is internal diversity" and a high school computer simulation experiment re emergent clique-forming behavior

    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