Complex Systems Reading Group
Note: All meets are at 7 p.m. at the Old Town tavern (corner of
Liberty and Ashley, in back under the large Rubenesque painting) unless otherwise noted.
April 20
The Complex Systems Reading Group will be celebrating the end of the
semester with one final paper that combines at least two topics of
interest -- networks and genetic algorithms. Please feel free to drop by
even if you would like to just complexly rub a few elbows and have a
few beers.
Optimizing genetic algorithm strategies for evolving networks
http://arxiv.org/abs/cs/0404019
Matthew J. Berryman, Andrew Allison, Derek Abbott
This paper explores the use of genetic algorithms for the design of
networks, where the demands on the network fluctuate in time. For varying
network constraints, we find the best network using the standard genetic
algorithm operators such as inversion, mutation and crossover. We also
examine how the choice of genetic algorithm operators affects the quality
of the best network found. Such networks typically contain redundancy in
servers, where several servers perform the same task and pleiotropy, where
servers perform multiple tasks. We explore this trade-off between
pleiotropy versus redundancy on the cost versus reliability as a measure
of the quality of the network.
April 13
This week the Complex Systems Reading Group will be discussing an
interesting paper that relates the internal dynamics of a plant to a
cellular automata. After you read this paper, you'll never look at a
cocklebur in quite the same way.
As usual, we will be meeting on Tuesday (April 13) at
7 p.m. at the Old Town Tavern (corner of Liberty and Ashley, in back under
the large Rubenesque painting).
Evidence for complex, collective dynamics and emergent, distributed
computation in plants
by David Peak, Jevin D. West , Susanna M. Messinger and Keith A. Mott
http://www.umich.edu/~warrencp/918.pdf
Proceedings of the National Academy of Sciences 101(4): 918-922 (2004)
It has been suggested that some biological processes are equivalent to
computation, but quantitative evidence for that view is weak. Plants must
solve the problem of adjusting stomatal apertures to allow sufficient CO2
uptake for photosynthesis while preventing excessive water loss. Under
some conditions, stomatal apertures become synchronized into patches that
exhibit richly complicated dynamics, similar to behaviors found in
cellular automata that perform computational tasks. Using sequences of
chlorophyll fluorescence images from leaves of Xanthium strumarium L.
(cocklebur), we quantified spatial and temporal correlations in stomatal
dynamics. Our values are statistically indistinguishable from those of the
same correlations found in the dynamics of automata that compute. These
results are consistent with the proposition that a plant solves its
optimal gas exchange problem through an emergent, distributed computation
performed by its leaves.
April 6
This week the Complex Systems Reading Group will be discussing a
paper that takes the complex adaptive systems approach to an interesting
but quite natural subject -- stem cells.
One more thing before I get to the paper:
First, I have been talking with folks at CSAAW, and they were mentioning
the role of CSRG in discussing, reviewing and understanding the "canon"
of complex systems, and I think (correct me if I'm wrong, Ted) that was
the original inspiration for the CSRG. Rick Riolo has done a great job
of constructing such a "canon" to be studied in his courses in the
UM complex systems program, but I realize that (a) nonstudents may not
have access to or time for those courses and (b) everyone has a different
idea of what the complex systems canon should be.
CSRG has reviewed a few subjects (Zipf's law, Shannon theory of
information, small worlds) this year, but we have been primarily
been looking at current research. So, if there is a subject
(coevolution, genetic algorithms, Bayesian networks, critical theory,
etc.) that you would like to dig into with more depth ("I have been
interested in _______, but I'd really like to understand it..."), please
send me an email, and we can see if we can find a good reading.
On to the paper...As usual, we will be meeting on Tuesday (April 6) at
7 p.m. at the Old Town Tavern (corner of Liberty and Ashley, in back under
the large Rubenesque painting).
Understanding cell lineages as complex adaptive systems
http://www.umich.edu/~warrencp/stem_cell.pdf
by Neil D. Theisea and Mark d'Inverno
Blood Cells, Molecules, and Diseases
Volume 32, Issue 1 , January-February 2004, Pages 17-20
Stem cells may be considered complex reactive systems because of their
vast number in a living system, their reactive nature, and the influence
of local environmental factors (such as the state of neighboring cells,
tissue matrix, stem cell physiological processes) on their behavior. In
such systems, emergent global behavior arises through the multitude of
local interactions among the cell agents. Approaching hematopoietic and
other stem cell lineages from this perspective have critical ramifications
on current thinking relating to the plasticity of these lineage systems,
the modeling of stem cell systems, and the interpretation of clinical data
regarding many diseases within such models.
March 30
This week the Complex Systems Reading Group will be discussing a paper
that separates a number of technological, biological, language and
social networks into a number of "superfamilies" by looking at the
statistical significance of their local structures, or "motifs".
Glancing at the text, it did not seem to explain the importance of all
these structures, so you might want to bring your thinking caps.
As usual, we will be meeting on Tuesday, March 30 at 7 p.m. at the Old
Town Tavern (corner of Liberty and Ashley, in back under the large
Rubenesque painting).
Here are the details on the paper...
Superfamilies of Evolved and Designed Networks
http://www.umich.edu/~warrencp/1538.pdf
Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr,
Inbal Ayzenshtat, Michal Sheffer, Uri Alon
Science 303(5663): 1538-1542 (2004).
Complex biological, technological, and sociological networks can be of
very different sizes and connectivities, making it difficult to compare
their structures. Here we present an approach to systematically study
similarity in the local structure of networks, based on the significance
profile (SP) of small subgraphs in the network compared to randomized
networks. We find several superfamilies of previously unrelated networks
with very similar SPs. One superfamily, including transcription networks
of microorganisms, represents "rate-limited" information-processing
networks strongly constrained by the response time of their components. A
distinct superfamily includes protein signaling, developmental genetic
networks, and neuronal wiring. Additional superfamilies include power
grids, protein-structure networks and geometric networks, World Wide Web
links and social networks, and word-adjacency networks from different
languages.
March 23
This week's paper for the Complex Systems Reading Group will look at the
importance of criticality in the functioning of brain networks. As usual,
the reading group will be meeting on Tuesday, March 23 at 7 p.m. at the
Old Town Tavern (corner of Liberty and Ashley, in back under the large
Rubenesque painting).
On to the details of this week's paper...
Critical brain networks
by Dante R. Chialvo
http://arxiv.org/abs/cond-mat/0402538
Highly correlated brain dynamics produces synchronized states with no
behavioral value, while weakly correlated dynamics prevents information
flow. We discuss the idea put forward by Per Bak that the working brain
stays at an intermediate (critical) regime characterized by power-law
correlations.
March 16
This week's topic is Bayesian networks, particularly their
interesting applications to genetics, and we have a number of resources
to peruse. Let me thank Ken Winter for his help in gathering them all.
First of all, for a very brief, simple description of the Bayesian
networks and their potential, you should check out #4 in the
"10 Emerging Technologies That Will Change Your World"
http://www.umich.edu/~warrencp/emergingtech.htm
Gregory T Huang, Lauren Gravitz, Ivan Amato, Wade Roush, et. al.
Technology Review 107(1):32 (2004).
The easiest way to find it is to search the document for "Bayesian".
--->Secondly, the primary paper for this week is a Science review article
that looks at the application of Bayesian networks to genetics:
Inferring Cellular Networks Using Probabilistic Graphical Models
http://www.umich.edu/~warrencp/799.pdf
Nir Friedman
Science 303(6):799-805 (2004)
High-throughput genome-wide molecular assays, which probe cellular
networks from different perspectives, have become central to molecular
biology. Probabilistic graphical models are useful for extracting
meaningful biological insights from the resulting data sets. These models
provide a concise representation of complex cellular networks by composing
simpler submodels. Procedures based on well-understood principles for
inferring such models from data facilitate a model-based methodology for
analysis and discovery. This methodology and its capabilities are
illustrated by several recent applications to gene expression data.
Also, if you looking for further help with the concepts and details of
Bayesian networks or if you are further interested in Bayesian networks,
you may want to look at the helpful tutorials on David Heckerman's
website:
http://research.microsoft.com/~heckerman/
March 9
We have recently be discussing Zipf's law for languages, but this week we
will be looking at issues surrounding the Zipf's law for CITIES, an
analogous scaling law for urban populations. If you would also like to
discuss the "BONUS LISGUISTICS PAPER" I mentioned earlier this week, feel
free to drop by, and we can discuss that as well.
On to the paper...
http://www.santafe.edu/sfi/publications/wpabstract/200402002
Scaling Laws and Urban Systems
by Denise Pumain
Abstract: This paper is a review of a few problems associated with the
observation of scaling laws in urban systems. Two levels in the spatial
organization have to be formalized, cities as systems and systems of
cities. Both encounter problems of measurement, especially in the
identification and delimitation of towns and cities. The problem of city
sizes and its relation to urbanization processes have been conceptualized
in connection with Pareto laws, central place theory, space-time
transformations, and fractal geometry. All approaches raise the question
of how the autonomy that characterizes the evolution of urban systems at a
macro level can be realized, either by random growth, or optimization
processes, or controlled by systems of social and spatial interactions at
a micro-level.
March 2
Rested and hopefully recovered from winter or spring break, the Complex
Systems Reading Group will be meeting this Tuesday, March 2 at 7 p.m.
at the Old Town Tavern (corner of Liberty and Ashley, in back under the
large Rubenesque painting).
For this week's paper, we will return to Zipf's law for word frequency in
language, a topic we briefly discussed last semester. If you are also
interested in what Zipf's law papers we did last semester, you might want
to check out the December 8 references on
http://www.cscs.umich.edu/discussionGroup/csrg-f03.html
On to this week's paper...
Two Regimes in the Frequency of Words and the Origins of Complex Lexicons:
Zipf's Law Revisited
by Ramon Ferrer Cancho and Ricard V. Soli
http://www.santafe.edu/sfi/publications/wpabstract/200012068
Zipf's law states that the frequency of a word is a power function of its
rank. The exponent of the power is usually accepted to be close to (-)1.
Great deviations between the predicted and real number of different words
of a text, disagreements between the predicted and real exponent of the
probability density function and statistics on a big corpus, make evident
that word frequency as a function of the rank follows two different
exponents, $\approx (-)1$ for the first regime and $\approx (-)2$ for the
second. The implications of the change in exponents for the metrics of
texts and for the origins of complex lexicons are analyzed.
February 17
Well, I asked for some adaptation papers last week, and Science (and Ken
Winter, who suggest a good paper we'll get to a bit later [Thanks!])
delivered. This week's paper is a review of new developments in
evolutionary game theory applications to biology, looking not only at
adaptation but coevolution as well. It even claims to have applications
to human language. Here it is...
Evolutionary Dynamics of Biological Games
http://www.umich.edu/~warrencp/793.pdf
by Martin A. Nowak and Karl Sigmund
Science 303, 793-799 (2004)
Darwinian dynamics based on mutation and selection form the core of
mathematical models for adaptation and coevolution of biological
populations. The evolutionary outcome is often not a fitness-maximizing
equilibrium but can include oscillations and chaos. For studying
frequency-dependent selection, game-theoretic arguments are more
appropriate than optimization algorithms. Replicator and adaptive dynamics
describe short- and long-term evolution in phenotype space and have found
applications ranging from animal behavior and ecology to speciation,
macroevolution, and human language. Evolutionary game theory is an
essential component of a mathematical and computational approach to
biology.
February 10
Hopefully this week's paper, hot of the presses, will be an interesting
combination of the human and the technical. I realize we've been a bit
weak on the adaptive part of complex systems lately, so, if you have any
suggestions on papers, adaptive or otherwise, please feel free to chime
in. On to the paper...
Topology of large-scale engineering problem-solving networks
http://www-personal.umich.edu/~warrencp/problemsolve.pdf
by Dan Braha and Yaneer Bar-Yam
Physical Review E 69:016113 (2004)
The last few years have led to a series of discoveries that uncovered
statistical properties that are common to a variety of diverse real-world
social, information, biological, and technological networks. The goal of
the present paper is to investigate the statistical properties of networks
of people engaged in distributed problem solving and discuss their
significance. We show that problem-solving networks have properties
(sparseness, small world, scaling regimes) that are like those displayed
by information, biological, and technological networks. More importantly,
we demonstrate a previously unreported difference between the distribution
of incoming and outgoing links of directed networks. Specifically, the
incoming link distributions have sharp cutoffs that are substantially
lower than those of the outgoing link distributions (sometimes the
outgoing cutoffs are not even present). This asymmetry can be explained by
considering the dynamical interactions that take place in distributed
problem solving and may be related to differences between each actor's
capacity to process information provided by others and the actor's
capacity to transmit information over the network. We conjecture that the
asymmetric link distribution is likely to hold for other human or nonhuman
directed networks when nodes represent information processing and using
elements.
February 3
Although we had a few hardy souls that showed up last week despite the
weather, there were a few who responded wanting to do the queuing theory/genetic
network paper this week, so here it is...
Bridging genetic networks and queueing theory
by Arnon Arazia, Eshel Ben-Jacob, and Uri Yechialia
Physica A, 332: 585-616 (2004).
http://www.umich.edu/~warrencp/bridge.pdf
One of the main challenges facing biology today is the understanding of
the joint action of genes, proteins and RNA molecules, interwoven in
intricate interdependencies commonly known as genetic networks. To this
end, several mathematical approaches have been introduced to date. In
addition to developing the analytical tools required for this task anew,
one can utilize knowledge found in existing disciplines, specializing in
the representation and analysis of systems featuring similar aspects. We
suggest queueing theory as a possible source of such knowledge. This
discipline, which focuses on the study of workloads forming in a variety
of scenarios, offers an assortment of tools allowing for the derivation of
the statistical properties of the inspected systems. We argue that a
proper adaptation of modeling techniques and analytical methods used in
queueing theory can contribute to the study of genetic regulatory
networks. This is demonstrated by presenting a queueing-inspired model of
a genetic network of arbitrary size and structure, for which the
probability distribution function is derived. This model is further
applied to the description of the lac operon regulation mechanism. In
addition, we discuss the possible benefits stemming for queueing theory
from the interdisciplinary dialogue with molecular biology
in particular, the incorporation of various dynamical behaviours into
queueing networks.
Also, here is some potentially relevant info about queuing theory...
http://www.new-destiny.co.uk/andrew/past_work/queueing_theory/main.html
January 27
Carrying a bit over from last semester, our first paper of the semester
will look at an application of queuing theory to genetic networks.
Before I get to the paper, for those of us who are curious about what
queuing theory is, you might want to check out the following webpage...
http://www.new-destiny.co.uk/andrew/past_work/queueing_theory/main.html
If you find better relevant webpages, feel free to clue me in. I'll pass
them on. So, on to the paper:
Bridging genetic networks and queueing theory
by Arnon Arazia, Eshel Ben-Jacob, and Uri Yechialia
Physica A, 332: 585-616 (2004).
http://www.umich.edu/~warrencp/bridge.pdf
One of the main challenges facing biology today is the understanding of
the joint action of genes, proteins and RNA molecules, interwoven in
intricate interdependencies commonly known as genetic networks. To this
end, several mathematical approaches have been introduced to date. In
addition to developing the analytical tools required for this task anew,
one can utilize knowledge found in existing disciplines, specializing in
the representation and analysis of systems featuring similar aspects. We
suggest queueing theory as a possible source of such knowledge. This
discipline, which focuses on the study of workloads forming in a variety
of scenarios, offers an assortment of tools allowing for the derivation of
the statistical properties of the inspected systems. We argue that a
proper adaptation of modeling techniques and analytical methods used in
queueing theory can contribute to the study of genetic regulatory
networks. This is demonstrated by presenting a queueing-inspired model of
a genetic network of arbitrary size and structure, for which the
probability distribution function is derived. This model is further
applied to the description of the lac operon regulation mechanism. In
addition, we discuss the possible benefits stemming for queueing theory
from the interdisciplinary dialogue with molecular biology
in particular, the incorporation of various dynamical behaviours into
queueing networks.
January 20
We will be kicking off the winter term with an organizational meeting
for the Complex Systems Reading Group next TUESDAY, January 20 at 7 p.m.
at the Old Town tavern (corner of Liberty and Ashley, in back under the
large Rubenesque painting).
We will be deciding when and where to meet and what to read during the
semester. We had been meeting on Mondays last semester (and Mondays
did have the advantage of being relatively quiet at Old Town), but we had
a request to move it to Tuesdays. If you cannot make Tuesday nights,
please email me and tell me what nights of the week you could make it.
If you have come across some nifty or even semi-nifty papers about
complex systems, bring 'em with you next Tuesday. If you'd like to
present some of your research to the group, we'd be glad to hear about it.
IMPORTANT: If you can't make it to this meeting, please feel free to send
an email with your suggestions about papers and topics as well.
