CSSS 2010 Santa Fe-Projects & Working Groups

From Santa Fe Institute Events Wiki

CSSS Santa Fe 2010

Working Group Wiki Scratch Page

Smart Leadership Framework

next meeting

Wednesday, July 7th, Skype
3pm brussels/rome/amsterdam, 9pm shanghai, 7am santa fe, 9am washington dc

slide pack

under development

working paper

under development

discussion area

non linera dynamics

under development

large data sets

under development

Collective aesthetics

Daniel Jones Griffith Rees Katarzyna Samson

To address the CSSS tradition of an annual tshirt design, we propose a novel solution - a mechanism to collectively produce a design through an iterated series of local interactions. Via a web interface, each CSSS participant will be able to contribute an element to the design whilst limited to only perceiving the local region around their working area.

Systems failure in corporate networks

members: Bruno Abrahao, Pilar Opazo, Nicholas Foti, Roberta Sinatra, Oana Carja

"Word Bang", The Evolution of Words and Language

Nicholas Foti,Julie Granka,Erika Fille Legara,Thomas Maillart,Giovanni Petri,

The evolution of words and Language is thought to reflect the evolution of society. When new conceptual jumps (technology, art, philosophy) occur, very often a new bench of word are needed and thus introduced in the common language and eventually in official dictionaries.

By mining, two datasets and , we intend to uncover mechanisms of evolution of language (i) in general and over a long period (Gutenberg Project) and (ii) for a specific, yet fast evolving, subset of language (MIT Technology Review).

Initial Project Idea (by Dan Rockmore)

(Dan Rockmore) - In a class on complex systems that I teach at Dartmouth one of the final projects seemed to indicate from a small and somewhat biased sample of English words, that word origins (as indicated by one of the online dictionaries) seem clustered at certain times. As a start I would propose a mining of this info in some online dictionary, performing some initial analysis and see if "there is a there, there.." and if so, keep on going.


Julie: I'm (broadly) interested in looking at changes in word frequencies over time. Most simply, it might be interesting to see if there are words with drastic frequency changes: from very low to high frequency, or from intermediate frequency to extinction. Then, we could see if there are any reasons to explain these patterns (this would probably be more interpretable for the technology data). - Erika: Tracking these changes from articles taken from the Gutenberg Project might not tell us anything since each book talks about a particular story/plot. What do you think? I have to agree though that these patterns might be more common in technology blogs where the theme (broader: technology) is uniform all throughout our data set.

Julie: I think it would also be interesting to see if there are any correlations between words; i.e., pairs of words where frequencies are positively or negatively correlated over time. It might also be interesting to implement a clustering approach like the one Jure Leskovec used when he clustered the volume curves based on their shapes - but using word frequency changes over time instead. We could see if these results make sense given the word co-occurrence networks. I'm thinking that looking at the frequency data on a finer scale like this may be difficult to do with a very large number of words and sampling points - maybe we should think about if there are a particular set of words we would like to look at? - Erika: Regarding the co-occurrence network, the issue raised is well-founded. There could be a way out of this through some filtering methods. I believe that Nick is familiar with such techniques wherein certain edges, which are deemed "weak", are filtered out of the network thereby leaving us with "strongly" connected nodes. Looking at certain words is also a possibility but I'm just wondering how we are going to pick/choose some of them from a wide range of other content words. This might prove to be difficult and could easily be like cherry picking. :)

Julie: I think we should also look at changes in word network statistics over time, calculated from networks that people who know how to construct networks construct. - Erika: Yes! We could track changes in the networks' topological properties through time.

Dynamics of Equities Market Structure

( Dan Rockmore) -- In a paper of mine w/some of my buddies (some of whom you will meet this summer), "Topological Structures in the Equities Market," PNAS December 30, 2008 vol. 105 no. 52 20589-20594, we found some interesting structure in the correlation network of the NYSE equities market. This required a choice of a time window. It would be interesting to see how/if this structure changes over time and window size, especially on either side of market crises. Scott Pauls has code that could be used to do some of this analysis.

Style of Chess Play

( Dan Rockmore) -- I am curious to see if using tools from learning one can characterize the "style" of a chess player. The website has a database of chess games. I'm not sure if the annotation would enable the determination of particular players, but even without that, can clustering on the move data give sensible/interesting results with respect to style of play?

Trusting Swarms

see Trusting Swarms (Bruno Abrahao, Zhiyuan Song, Bogdan State)

"Genes for Breakfast"

(Yixian Song) - I've once read a paper of Redfield(1993) "Genes for Breakfast: The Have-Your-Cake and-Eat-lt-Too of Bacterial Transformation". Though it's an old publication, I still find the idea very inspiring. Well, considering bacteria living in a gene-pool with abandoned DNA strands, each bacterium can randomly "eat" free DNA strands, and use them as nutrition or for DNA repairing or even gene improvement. But the DNA strands were abandoned for a reason. Some of them can be virulent.(!!!) Besides bacteria can exchange DNA with each other, of course. We can define a population size of bacteria, amount of free DNA strands in gene-pool, percentage of virulent DNA and their virulence (impact on the bacteria fitness). We certainly can also consider the bacteria as a metapopulation.("A metapopulation consists of a group of spatially separated populations of the same species which interact at some level." - says The question to be answered will be "in which situation the bacterial population will become extinct in the end".

Patterns in Cenozoic Western US volcanism

(Leif Karlstrom) - Allen Glazner (UNC) has put together a neat database of volcanic activity over the past 65 million years in the Western US (here's a movie of it), including location, duration of activity and lava composition. This data is derived from several careers worth of geologic mapping and dating volcanic rocks exposed all over the West. While it is not complete (not everything is preserved, and not everything has been mapped yet), there is a wealth of information about volcanic processes in here. I think it would be neat to mine this dataset for correlations, then think about ways to model it. This could include actual physics and geology, but could also be based solely on the data.

Here is a link to data files for this project. More soon.

Pitch diffusion in groups of musicians

(Leif Karlstrom) - When the violin section of an orchestra tunes, the concertmaster gets up and plays a note that all the rest of the violins try to match. I did some experiments in my undergrad with John Toner (physics, U Oregon) where we looked at what happens when the frequency of this tuning note shifts during the time when players are actively trying to match one another. We found that the shifted pitch diffuses through group if it is a small shift (a few Hz), but is immediately sensed by the whole group if it is a large shift. This implies that there is a shift from local to long-range interaction that governs how pitch matching occurs. We envisioned a process similar to flocking behavior in birds for the local interactions, which is governed by an advection-diffusion equation. But we were unable to model the data with this model, because it does not allow for long-range interactions. I still have the data, and would be interested in thinking again about how people process sound in groups.

  • Sounds like a cool topic! A quick question: do you have data on the social structure of the orchestra? It would be interesting to look at the formal hierarchy, as well as at the informal social network, and see if it has any influence on pitch diffusion, especially for the long-range interactions. (Question asked by Bogdan State)
  • This is interesting and (vaguely) related to an ABM project that a student of mine started some years ago: constructing an ABM that would simulate Pauline Oliveros's "Tuning Meditation." The basic format of this is a large room of participants who choose a "pleasing" tone and sing it for an indeterminate time ("a breath"). They then choose someone else in the crowd and try to match their tone. Iterate. In performances, there is usually convergence to a given tone and duration. Here is a link to one simulation of this:

It would be fun to do this and try to take into account geometry of the performance space, range of sight, ability to match a tone, etc. (Rockmore)

Language Evolution in an Archipelago

(Erika Fille Legara) - The Philippines is an archipelago containing 7,106 islands with three broader divisions (three main islands): Luzon, Visayas, and Mindanao. It has around 175 individual languages, four of which already have no more known speakers. Moreover, the Constitution recognizes eight (8) major and twelve (12) regional languages (statistics are taken from Wikipedia on the Philippines). It is also interesting to note that most Filipinos know at least three languages: (1) his/her native language, (2) Filipino, and (3) English. Now, if I could get data on the different language distributions (per year or per decade) within the archipelago, it might give us new insights on how certain languages evolve. It would also be interesting to model or predict which languages would eventually thrive and die. Also, I'd like to predict what would happen to certain languages at certain regional boundaries after a few decades or a few centuries. And finally, taking a hint from Professor Dan's idea (above), it may also be interesting to look at how certain words in the Filipino dictionary evolve through time. Caveat: I still need to check if we could have the data available before June.

Social Cognition: Defining the Situation

(Lynette Shaw) – A foundational concept in social cognition is that of the “mental representation.” Essentially, this is a preexisting framework of meaning that is automatically imposed on perceived information in order to develop the inferences necessary for generating interpretations and expectations from that information. This basic concept bears a strong relationship to many popular ideas in the social sciences such as the “categories” involved in discrimination, cultural “schemas,” the “frames” of social movements, organizational “scripts,” and the “mental models” that are associated with institutions.

In his foundational piece, “On Perceptual Readiness,” Bruner proposes a very simple model of how these representations are essentially “selected for” on the basis of inference validation. Since that time, the complex interdependencies of this automatic, cognitive process occurring within a social context have been explicitly noted in work dealing with “expectancy confirmation.” Implicitly, the interdependent nature of this process within the social context has arguably undergirded several bodies of both classical and contemporary social theory - especially those relying on an idea of individuals reaching a “shared definition of the situation.”

Though this inference-validation model of mental representation is a relatively simple one, little work to date has really sought to represent it in ways that could be formally or systematically elaborated upon. This project would translate this conceptual model into an agent-based computer simulation and, if time allows, begin exploring key parameterizations of it that have interesting real world analogs.

  • If I understand this correctly, I find it interesting :-) Ligtvoet 21:37, 21 May 2010 (UTC)
  • Thanks! I look forward to getting to talk about it more in person. It's a pretty intuitive concept, but there isn't a lot of established vocabulary for it as of yet. Lynette Shaw

"Structure, Function and Spaces"

(Giovanni Petri): recently networks have been studied in relation to their space embeddings (usually hyperbolic) for a number of reasons, for example efficient navigation, data filtering or visualization (see here, here and here). To wet your appetite, one of the fascinating results is that any graph can be embedded as a planar graph on a surface with sufficiently high genus (i.e. how many donut's hole you make in the space). Now I would be interested in studying whether such hidden metric space analogy goes a bit deeper. For example, whether there is a relation between diffusion and transport properties on a networks and its space embedding, whether interacting systems (think of correlation matrices, multi-body systems etc) can be cast in such form and some of their properties derived from the embedding space's characteristics (say genus, curvature etc etc). As I'm currently reading on the subject but don't have a precise idea how to implement it, I would very much like feedback from any interested peer/p.


(Giovanni Petri): Brandes et al. (link broken) -> This seems to work recently extracted role-models for ego-networks from a dataset obtained through questionnaire in a large community of immigrants. It would be interesting to use some of the available data to try and identify behavioral archetypes (socialites, noobs, PKers, carebears, griefers etc etc) in online communities, how their interact and evolve. I'm thinking of virtual worlds (as Eve Online or Michael Szell's world for instance) as they do present a wider range of possible interactions than standard social networks, i.e. grouping, migrations, wars, commerce etc etc . This project however sounds pretty data-intensive and it might not be easy to get all the data involved.

  • (Michael Szell) I have begun working on exactly this topic, in succession to this paper. See Video of an aggressive player. One could follow the evolution of some players and their activities in time, and see how their "careers" evolve. I am sure one could observe a lot of interesting things, e.g. "bursty" behavior, long-range correlations, non-gaussian distributions of activity... I can try to extract data from some players, so we can take a look at it in June.
  • (Giovanni Petri) Great! Another issue might be the mobility of virtual agents as opposed to real agents (say from mobile networks). It would be interesting to see if there are any similarities or not (what I'm thinking of is something along the lines of, can we learn something useful for real-world applications from the virtual ones?) and maybe there might be links to the project proposed by Bogdan State at the top of the page.
  • (Lynette Shaw) There are many aspects of these papers and potential project that might intersect with social-structure based notions of “identity” (good article on the subject).One line of inquiry has centered on multiple identities (which are connected to the different roles people are expected to play as a result of the different groups to which they belong). Being able to suss out how much career paths depend on histories of involvement with different groups(as opposed to changes in individual traits) might be one way to get at that. In terms of “archetypes,” there also has been a recent drive to look at identity as a “schema” that is picked up in a social context and then imposed upon one’s own self. Once this happens, this “schema” then determines an individual’s social behavior. I would be interested in seeing if there was a way here to capture how well an individual’s exposure to certain models of behavior predicts their own subsequent behavior patterns.

"Phenotypic Plasticity and Climate Change"

(Kyla Dahlin): One of the biggest challenges to understanding how ecosystems will change with a changing climate is that we don't know species' fundamental niches. People like to take existing distributions ("realized niches"), correlate them with climate, then project where that climate will move in the future, but that ignores the fact that plants could actually be able to tolerate a much wider range of conditions than those we currently find them in. It sees like you could get a better handle on this if you knew (1) a plant's generation time, (2) how many generations it takes to evolve a new trait, and (3) the climate the plant experienced in the past. If the timescale of a plant's evolution is similar to that of, say, glacial cycles, that would suggest that the plant could handle a pretty wide range of temperatures and weather extremes. I'd love to know if any of the evolutionary bio folks have thought about this or know the literature better than I do!

Quantitative Analysis of Northern New Mexico Acequia Infrastructure: An Applied Complexity Approach

(John Paul)

Next group meeting follows lecture on Tuesday, June 15.

New Mexico has community ditch irrigation systems called acequias that are some of the oldest decentralized European social structures in the Americas. Some work has been done by a previous CSSS student studying the social structure of acequias and how they are both sustainable and vulnerable to novel disturbances. More academic work can be found here discussing social structures. Most of this work has been qualitative traditional sociological work.

I've come across some data from the New Mexico Office of the State Engineer detailing acequia water rights infrastructure I think may be interesting to look at. Please see the spreadsheets on this page.

Cursory data analysis is a good place to start.

I'm eventually interested either crafting a model to simulate acequia network growth (theoretical) for historical research purposes, or some research into the statewide structure of acequias that may determine future policy recommendations (applied).

-== emergence and decay of common property management regimes. ==

Inspired by Ostrom's work into common property regimes, I've been interested in Agent-based-simulations of these institutions, and how they are created and destroyed. There are a few readings around that here - including Cox's thesis from John Paul's link list.

--- Dan MacKinlay

"Roadkill as a means of spreading disease in Tasmanian Devils"

(Gavin Fay) - Living in Tasmania, it is hard not to become familiar with the plight of the Tasmanian Devil, whose population is currently dwindling due to Devil Facial Tumour Disease (DFTD), a rather nasty infectious cancer which has become prevalent through much of the state. DFTD infection relies on transmission of infected cells from contact, most likely due to biting, which these critters do a lot of during mating and around prey carcasses. A hot conservation topic right now is forestry plans to build roads opening up a wilderness area in the north of the state to ecotourism opportunities. The devil population in this area has until now remained disease free. There are concerns that the road will increase the likelihood that DFTD will spread to the diseasse-free population: Devils are scavengers and frequently feed on roadkill, the creation of a road may then provide an opportunity for increased frequency of contact between infected and disease-free devils. It might be interesting to investigate how introducing a fixed-location source of additional prey items (ie a road) to a devil population would change the contact network for Devils, and then also to what extent the increased contact frequency would have to be to facilitate transmission of DFTD from an infected devil population to a disease-free one.

  • This sounds interesting, especially if you have some data on how the populations move/interact/etc? I've done some predator/prey dynamic modeling both as ODE and Cellular Automata (CA), and I'd suspect CA would be an interesting approach. We should talk! (Megan Olsen)
    • I really like this project, specially if you taeckle it from a CA approach...this is a technique I would like to understand better!! I am a biologist, and have been working with diseases spread in spatial structures (malaria), but from differential equations modelling and time series...I would really like to be part of this project if it turns out to become one! Please, let me know! (Vanessa Weinberger)

"Manage lots of fish stocks, or a few?"

(Gavin Fay) - Australia's Southern and Eastern Scalefish and Shark Fishery (SESSF) is a multiple species fishery with a large number of vessels operating using a range of gears. The fishery exploits 80+ species, with a subset of target species managed by a total allowable catch (TAC) under a quota management system. Management of other species within the fishery is controlled by other measures such as trip limits, gesar restrictions, and spatial and seasonal closures. Specification of TACs requires data collection and routine stock assessment in order to calculate suitable catch limits given an assessment of stock status.

It is not feasible to perform full quantitative analyses for each quota species on an annual basis (from both a data perspective, instituional capacity, $$$, and other reasons) and rapid assessment methods are prevalent (or absent). Given that the fishery is multiple species there exist a considerable number of technical interactions within the fishery. ie targeting one species leads to catch of several others - single fishing opportunities (shots, hauls) are not single species.

Given these interactions: Which species should we manage for? Are there a suite of species that we can actively manage for such that the risk to other stocks is not too great? Should we target the high-value species, abundant species (that may be low in value per kg but overall count big $), or manage to minimise the catch of vulnerable species? What are the effects of these options on ecosystem biomass, proportion of stocks in danger of collapse, yield, profit, etc?

Indeed, just describing the multispecies interactions (which species are associated with others in the data, how do these fishery assemblages vary over time and space (perhaps by port)), would be an exercise in itself. Perhaps one could also look at the relative costs to a port-based community associated with the fished assemblage shifting from one to another (perhaps as a result of climate change?).

  • (Chaitanya Gokhale) If I understand the idea correctly I think this can be dealt with an evolutionary game theoretic approach. Although not completely, as per the reasons you have already stated, maybe we can abstract the system out to some important interactions for e.g. targeted catch of one species drags along some other species with it. I don't know if this makes sense, we can discuss it further next week.

"Estimating abundance trends of non-target species"

(Gavin Fay) - Trends in abundance of non-target, or bycatch species in fisheries is generally achieved by the results of fishery independent surveys. Surveys are expensive, and are not always available. How then can we estimate trends when these data are not available? Direct effects (ie incidental harvesting) can be measured (time series of catch), and it might be expected that the relative trends in exploitation rate of bycatch species should be similar to those target species with which the bycatch species are taken. This idea has been attempted in multispecies assessments under a 'Robin Hood' approach (steal from the data-rich to give to the poor). An issue is that the lack of information for the data-poor species can degrade the performance of the data-rich assessment, when the assessments are conducted simultaneously in a multispecies framework.

I'm thinking about a general multivariate state-space modelling framework for nontarget species, which could use correlations of direct effects with target species derived from fisheries logbook data, and the 'known' abundances and trends of the target species. An additional question is how to quantify indirect effects of fishing on abundance of nontarget species. One possibility could be to guide the covariance with the results of foodweb modelling, which could be limited to simply describing how connected nontarget species are with the various target species. Another might be to use information about life history, or trophic level to describe general expectations for the degree of correlation/change. It might be useful to make use of a system where it is possible to groundtruth methods - ie an ecosystem for which survey data are available. Alternatively, one could subset the data-rich species.

"Evolution of life history strategies in sea lions"

(Gavin Fay) - The Australian sea lion (ASL) is unique among the otariids (fur seals and sea lions) in that it exhibits a non-annual breeding strategy, with breeding cycle of ~17 months, an extended pupping season at rookeries of 4-5 months, and non-synchronous pupping among subpopulations (rookeries). In contrast, all other sea lions breed on 12 monthly cycle, with short pupping seasons, for which most species is synchronised among rookeries for the entire population.

A proposed idea is that the ASL strategy is in response to living in a low productivity environment (most other fur seals and sea lions live in highly productive, nutrient rich places). with the ability to vary the delay in implantantion of fertilised eggs depending on environmental conditions, thus enabling indiviudals to only invest in reproductive output when the probability for pup survival is high. Indeed, there is evidence that the length of breeding period is correlated with environemntal conditions. Perhaps it would be neat to see whether the 2 different life history strategies observed are concordant with the hypotheses given evolutionary pressure. I am not familiar with the methods involved, but one could evolve a suite of life histories given different environmental regimes and see which survive?

"How do organisms use space?"

(Andrew Hein). One fundamental problem in ecology and evolution is determining how and why organisms use space in the ways they do. Different organisms experience their environments at different “characteristic” spatial scales. For example, without the aid of technology, humans perceive and interact with their environments on the scale of meters (by sight) to kilometers (by sound or by walking from one place to another). Other organisms like bacteria perceive and interact with their environments on much smaller scales (e.g. micrometers). What determines these scales? Is it possible to predict the characteristic scale of an organism by knowing something about that organism? How do characteristic scales evolve and are they evolutionarily plastic or robust?

I envision two possible approaches to this problem. The first might be an evolutionary approach that assumes that characteristic scales evolve as a result of the need for organisms to communicate with one another. This would involve developing some evolutionary rules and allowing a network of organisms to “evolve” via simulations. These simulations could be used to understand the evolution and plasticity of characteristic scales. The second approach would be to try to understand what factors constrain the spatial scales used by different types of organisms. This might involve building some biological/physical models to try to predict how spatial scales ought to vary among organisms. These models could be compared to a data set on the spatial scales used by a broad variety of animals (I have one such data set).

  • (Giovanni Petri) Sounds pretty cool if I get it right. Also, I'm interested in information spreading myself, this looks very relevant for other applications, e.g. couple information/transportation systems.
  • (Megan Olsen) I'm also interested in the use of space, especially in ecology. I could see using genetic networks as a way to evolve the rules.
  • (Kyla Dahlin) Thinking about the memory/ cognition part of how animals use space, there's some work using brain/body size ratios as a proxy for intelligence (some of this work is shady, but at least the data exists) which might be an interesting addition to a predictive model of spatial scales.

"Does H1N1 make a comeback?"

(Xin Wang). In the last half year of 2009 and at the beginning of 2010, H1N1 diseases swept the whole world including China. At that time the TV programs were all filled with such related news. Somebody said that it was the conspiracy, but whether or not it is true, we have to focus on what we should do to prevent some unknown disease from being pandemic because the sweeping of another unkown disease all over the world will occur sooner or later such as H5N1 and SARS in 2003. So analyzing the evolution of the virus from the molecular level combining with the spread of the disease in the population from the macro level may help us find the general way to prevent the concept virus from outbreaking.

Traditionally we use SIR, SEIR and etc. to model the spread of the disease. Here we may use the multi-agent-based method to model the virus including genes and protein, and human beings, and to simulate three processes, the first of the evolution of the virus, the second of interaction between human and virus, the third of the infection with people moving. Because of my background in mathematical control theory and game theory, not in molecule biology or ecology, I am short of knowledge on biology and I am not sure whether or not this idea is feasible. Maybe make some restriction from the biological view is necessary.

Adding Genetics to Community phase-synchronization

(Vane Weinberger)- Browsing through Spatial Food Webs literature, I ran into a paper that I loved since the minute I read it: although a little too old, Blasius and Stone (1999)[[1]] simulated a simple tri-trophic ecological system that was able of the most incredibles fluctuations! I believe that this system can be expanded (maybe adding other relations into the local throphics phenomena), but what I REALLY wanted to add into the model was the population genetic subject: this work demostrate the great ammount of population crashes that are seen in a patch system and how they can be recovered when submerged on a spatial migrating system. However, as they are modelling the system from bottom-up approaches and thus adding the population-level processes of each guild, we could ask about how bad can these crashes affect the survival of the guild if we consider an Allee Effect or inbreeding phenomena. I do not know if someone has already done this before, but I think that this model would help us understand more about conservations efforts in the wild.

  • (Andrew Hein) This is a really nice idea. It would be interesting to try to track local and global oscillations in population genetic structure in the system you describe. It would also be interesting to try to determine the degree to which oscillations in genetic structure are synchronized (or out of phase) with population oscillations.

Scale-Free Networks in intertidal communities

Network Topology effects on population structure (Vane Weinberger)- In 2005, Nowak's team demostrated that certain networks topologies could alter the random fixation of an allelle (simulated through the Moran Process). More precisely, they discovered networks with many hubs augmented the effect of natural selection. The intertidal system is known for its great ammount of sessile or limited dispersal animals that can only disperse through their larval stage. Therefore, it was believed that the genetic population structure of a population was mainly a function of their dispersal capabilities (as larvae). However, if there is a sexual-limited-contact of their progenitors, which could create a network topology with many hubs (it happens in some gastropods) it could happen that there is an effect of the network topology that could alter the genetic population despite the homogeneization of the larvae pool. (Notice the two different contact networks that are created though this simulation...that something that is also worth for studyin, I am sure this could happen in other systems!). I apologize: this idea was discussed a long time ago and I stopped browsing about how to taeckle the topic...but I am sure we could arrange something for this!

  • (Roberta Sinatra) I would be very interested. Actually I am working on a dynamical model to detect topological communities on graphs, ispired to how genotype of walkers mutate when they move on the graph, meet and interact. Although I am more interested in finding topological properties of the graphs, I think that a realistic model based on plausible biological and genetic assumptions can highlight interesting properties of some self-organized systems. We can have a chat about that!

Modeling evolutionary dynamics of spatially structured populations

(Felix Hol) -- I am very interested in the interplay between ecology and evolution. Motivated by Sewall Wright's seminal 1932 paper I would like to investigate the effect that metapopulation formation has on the speed of evolution. The computational model to investigate this could be based on work by Mitchell & Crutchfield (and coworkers) where a genetic algorithm evolves a population of cellular automata to perform a certain task (see this paper). I propose to embed population structure in the genetic algorithm (GA) and find out what effect this has on the capabilities of the GA. One way of doing this might be to (bluntly) define subpopulations that cross breed at specified intervals; but I am sure that there are much more elegant/sophisticated ways of embedding structure. Some (wild) ideas for this are: putting them on graphs or lattices (with or without vacancies/movement)…. Any suggestions are greatly appreciated! (also other ideas for modeling stuff like this (evolutionary game theory etc..) are welcome)

  • I have the same idea and I am thinking about how to train the initial structure to be the one robust to different situations. (Xin Wang)
  • What about a metapopulation approach on a cellular automata? Each cell is a metapopulation, therefore giving local rules for the metapopulation and then global rules for the entire population (including migration). (Megan Olsen)
  • I was considering introducing population structure in my artificial evolution system (which uses a GA now). It is not based on cellular automata but on artificial gene regulatory networks. (Borys Wrobel)
  • (Andrew Hein) I have some ideas based on metapopulation and metacommunity models that may be pertinent. Sounds like a cool problem.
  • lets meet to chat about this project tonight (tuesday 8/6) at 8:30
  • some relevant papers are: [2] and [3]

The self-generation of patterns in Five-in-Row Game

(Xin Wang). In any human-machine or machine-machine game for chess, go, Five-in-Row and etc., the choice of patterns is very important, and so a good game-playing computer is always trained by both computer scientists and professional human players. After patterns are fixed, the weight of each pattern in the evaluation function can be optimized by NN, GA and other optimization methods. Although the depth of searching is another important factor, it only depends on fast searching algorithms and pruning algorithms. So the study on patterns makes sense to complex system. Traditionally the patterns are always fixed but here my initial idea is to train the computer to self generate its own patterns for use. This idea is very similar to "work by Mitchell & Crutchfield (and coworkers) where a genetic algorithm evolves a population of cellular automata to perform a certain task (see this paper)." (see above part by Felix Hol).

Network's shortest paths

(Sergey Melnik)

Consider a random network consisting of N nodes where each pair of nodes is connected with a given probability p (see Erdos-Renyi random graph). The question is about the shortest path through the network from one node to another (also called geodesic path, or intervertex distance):

Can we calculate analytically (and exactly) the probability distribution of shortest paths in such a network? That is, how likely it is that a pair of nodes chosen at random will be distance D apart. For distance D=1 the answer is obviously p. What are such probabilities for distances D=2, D=3, D=4, etc.?

Note that the network has a finite number of nodes (which is not necessarily large) and there are only 2 parameters here, N and p. This is a simple yet fundamental question and there is much more to follow in terms of immediate applications and new theories once we answer it.

The Monopoly project

(Sergey Melnik)

Have you ever wondered about the best strategy to play Monopoly?

We can start by answering simple questions such as "is it really better to be the first to throw the dice?", or "what are the most valuable squares on the field, and when?", or "to what extent do your skills help you overcome randomness to win this game?", or "how long would a game last?", or "how does all this changes with the number of players?". We can then go deeper to model negotiations and resource management strategies - plenty of possibilities here.

I am sure those who play this game already have some intuition. But can we precisely quantify these and other effects? I guess not yet. I think there is a lot here that can be modelled (analytically?) and compared with numerical (Monte Carlo?) simulations.

Finally, we can look into creating a new, even more exciting game to be played by the future generations. And surely you will have better calculated chances next time you play Monopoly with your friends!

  • I don't have references, but a friend of mine, who plays Monopoly competitions, has a whole bunch of rules that lead to better outcomes: what streets to buy, what streets not to buy etc. So to a certain extent somebody has done something familiar Ligtvoet

Properties of evolving artificial gene regulatory networks

see Properties of evolving artificial gene regulatory networks (Borys Wrobel)

I have built an artificial life platform (right now, it uses a genetic algorithm) that can generate a large number of gene regulatory networks that have evolved to perform certain computations (for example, process signals). I would be interested in investigating what are the statistical (or other) properties of these networks.

Here is a paper that describes (a version) of the model.

Grouping behavior and the evolution of animal migration

Andrew Hein see the project page for more info: Grouping behavior and the evolution of animal migration.

The blogosphere as a complex network: an empirical laboratory

Massimiliano Spaziani

Blognation ( is an aggregator of the Italian blogosphere. 2.500 blogs are aggregated, each blog produces about 10 posts a day, and a semantic engine automatically extracts tags (concepts) for each post. The database of the aggregator contains information about the relationships between blog and blog, and between post and concepts. Timestamp is traced. The database (MySQl) of the blog aggregator may be used as a laboratory where empirically measure network properties, calculate hubs and authorities, and design algorithms for post and blog ranking, for determining trends in time, etc.