Complex Systems Reading Group
Note: All meetings are at 7pm on Tuesdays
at The Old Town Tavern (corner of Liberty and Ashley, in back under the
large Rubenesque painting) unless otherwise noted.
November 23
Plenty of news this week. First of all, I'd like to introduce our new
Complex Systems Reading Group moderator, Aaron Bramson. My wife and I
will be moving to Baltimore at the end of December, where my wife will be
starting a postdoc at Johns Hopkins. We've have been tag-teaming with
our new little boy, so, in the short term, I'll be looking after the
little guy and completing a bit of research.
I'd just like to thank everyone in the reading group, especially Ted
Belding, for the opportunity of being your moderator, and I'd like to
thank the wider complex systems community for so much. It's been a
valuable, enlightening and fun time. Best wishes! I know I am leaving
CSRG in good, capable hands.
Second, our next meeting is the last CSRG meeting of the semester. This
week's reading is a paper on the evolution of weighted networks that I've
been pining for all semester, but, if you'd like to just drop by and jaw
about the end of the semester or your impending tryptophan overdose, feel
free. As usual, we will be meet at Old Town Tavern at 7 pm on Tuesday,
November 23 (corner of Liberty and Ashley, in back under the large
Rubenesque painting).
Title: Modeling the evolution of weighted networks
Authors: Barrat, Marc Barthelemy, Alessandro Vespignani
Abstract: We present a general model for the growth of weighted
networks in which the structural growth is coupled with the edges'
weight dynamical evolution. The model is based on a simple
weight-driven dynamics and a weights' reinforcement mechanism
coupled to the local network growth. That coupling can be
generalized in order to include the effect of additional randomness
and non-linearities which can be present in real-world networks. The
model generates weighted graphs exhibiting the statistical
properties observed in several real-world systems. In particular,
the model yields a non-trivial time evolution of vertices properties
and scale-free behavior with exponents depending on the microscopic
parameters characterizing the coupling rules. Very interestingly,
the generated graphs spontaneously achieve a complex hierarchical
architecture characterized by clustering and connectivity
correlations varying as a function of the vertices' degree.
Web link: http://www.arxiv.org/abs/cond-mat/0406238
Take care!
------------------------------------------------------------------------------
If you have ideas of readings for CSRG next semester, please post them
at
http://www.cscs.umich.edu:8000/CSRG/1
Simply type the relevant information into the provided box and press the
"add to the page" button. It will ask for a username and password.
If you have technical problems with the page, email me.
------------------------------------------------------------------------------
November 16
Upon request, the Complex Systems Reading Group will be reading a
follow-up to Thursday's speaker, Alfred Hubler, about adjusting to the
edge of chaos. BTW, if you have questions about cellular automata and
edge of chaos, check the links below the citation. As usual, we will be meet
at Old Town Tavern at 7 pm on Tuesday, November 16 (corner of Liberty and
Ashley, in back under the large Rubenesque painting).
On to the paper!
Title: Adaptation to the Edge of Chaos in the Self-Adjusting Logistic Map
Authors: Paul Melby, Jorg Kaidel, Nicholas Weber, Alfred Hubler
Journal-ref: Phys. Rev. Lett. 84, 5991 (2000)
Link: http://www.arxiv.org/abs/nlin.AO/0007006
Abstract: Self-adjusting, or adaptive systems have gathered much recent
interest. We present a model for self-adjusting systems which treats the
control parameters of the system as slowly varying, rather than constant. The
dynamics of these parameters is governed by a low-pass filtered feedback
from the dynamical variables of the system. We apply this model to the
logistic map and examine the behavior of the control parameter. We find
that the parameter leaves the chaotic regime. We observe a high
probability of finding the parameter at the boundary between periodicity
and chaos. We therefore find that this system exhibits adaptation to the
edge of chaos.
For a brief explanation of edge of chaos and cellular automata and a
nifty applet, check out
http://math.hws.edu/xJava/CA/index.html
http://math.hws.edu/xJava/CA/EdgeOfChaosCA.html
------------------------------------------------------------------------------
If you have ideas for other possible readings for CSRG, please post them
at
http://www.cscs.umich.edu:8000/CSRG/1
Simply type the relevant information into the provided box and press the
"add to the page" button. It will ask for a username and password.
As always, if you have technical problems with the page, email me.
------------------------------------------------------------------------------
November 9
Here is a brief reminder that the Complex Systems Reading Group will meet
at Old Town Tavern at 7 pm on Tuesday, November 9 (corner of Liberty and
Ashley, in back under the large Rubenesque painting). This week we will
be looking at an interesting application of genetic algorithms -- land
use planning.
Title: A genetic algorithm approach to multiobjective land use planning
Authors: Theodor J. Stewart, Ron Janssen and Marjan van Herwijnen
Journal: Computers & Operations Research 31(14):2293-2313 (December 2004)
Abstract: This paper describes a class of spatial planning problems in
which different land uses have to be allocated across a geographical
region, subject to a variety of constraints and conflicting management
objectives. A goal programming/reference point approach to the problem is
formulated, which leads however to a difficult nonlinear combinatorial
optimization problem. A special purpose genetic algorithm is developed for
the solution of this problem, and is extensively tested numerically. The
model and algorithm is then applied to a specific land use planning
problem in The Netherlands. The ultimate goal is to integrate the
algorithm into a complete land use planning decision support system.
Web link: http://www.umich.edu/~warrencp/genetic_algorithms_and_land_use.pdf
------------------------------------------------------------------------------
CSRG Swiki: Since we've been thinning out the proposed CSRG Swiki papers
list,
http://www.cscs.umich.edu:8000/CSRG/1
we are looking for more proposals. It would also be great to get
feedback on the papers that are there.
To add a proposal, simply type the relevant information into the provided
box and press the "add to the page" button. It will ask for a username
and password.
As always, if you have technical problems with the page, email me.
------------------------------------------------------------------------------
November 2
At our meeting Tuesday, November 2 at 7pm at the Old Town (corner
of W. Liberty and S. Ashley), the complex systems reading group will
discuss the two attached papers (plus one attached figure):
McCrone, John. (2004). How do you persist when your molecules don't?
Science and Consciousness Review, June 2004, No. 1.
http://www.sci-con.org/articles/reprints/20040601.pdf
Abstract: Now the brain is supposed to be some sort of computer. It is
an intricate network of some 1,000 trillion synaptic connections, each of
these synapses having been lovingly crafted by experience to have a
particular shape, a particular neurochemistry. It is of course the
information represented at these junctions that makes us who we are. But
how the heck do these synapses retain a stable identity when the
chemistry of cells is almost on the boil, with large molecules falling
apart nearly as soon as they are made?
Lisman, J.E., and Fallon J.R. (1999). What maintains memories? Science
283:339-340. http://www.sciencemag.org/cgi/content/full/283/5400/339
October 26
This week's reading for the Complex Systems Reading Group looks at the
interplay of catastrophic shifts and self-organized patchiness in
ecosystems. As usual, we will meet at Old Town Tavern at 7 pm on
Tuesday, October 26 (corner of Liberty and Ashley, in back under the large
Rubenesque painting).
Title: Self-Organized Patchiness and Catastrophic Shifts in Ecosystems
Authors: Max Rietkerk, Stefan C. Dekker, Peter C. de Ruiter, Johan van de
Koppel
Journal: Science, Vol 305, pp. 1926-1929 (24 September 2004)
Abstract: Unexpected sudden catastrophic shifts may occur in ecosystems,
with concomitant losses or gains of ecological and economic resources.
Such shifts have been theoretically attributed to positive feedback and
bistability of ecosystem states. However, verifications and predictive
power with respect to catastrophic responses to a changing environment are
lacking for spatially extensive ecosystems. This situation impedes
management and recovery strategies for such ecosystems. Here, we review
recent studies on various ecosystems that link self-organized patchiness
to catastrophic shifts between ecosystem states.
Web link:
http://mk.geog.uu.nl/homepages/Max/PDF/RietkerketalScience_2004_1926.pdf
See you there!
------------------------------------------------------------------------------
I'd be glad to have feedback on the recently proposed papers at the CSRG
Swiki:
http://www.cscs.umich.edu:8000/CSRG/1
If those papers don't strike your fancy, please propose other paper(s).
Simply type the relevant information into the provided box and press the
"add to the page" button. It will ask for a username and password.
As always, if you have technical problems with the page, email me.
------------------------------------------------------------------------------
October 19
Let me first thank all of the folks that have been attending this fall.
It's been a great and lively discussion. So, once again, the Complex
Systems Group will meet at Old Town Tavern at 7 pm on Tuesday, October 19
(corner of Liberty and Ashley, in back under the large Rubenesque painting).
Before we get to this week's paper on the use of percolation in searching
networks, let me first ask you to check out the recently proposed papers
at the CSRG Swiki:
http://www.cscs.umich.edu:8000/CSRG/1
We have a number of great contenders -- application of genetic
algorithms to land use planning, network analysis of regulatory network
dynamics, pattern formation and catastrophes in ecosystems, the
preservation of memory in a physically ephemeral brain structure, and
the evolution of weighted networks. If those papers don't strike
your fancy, feel free to propose another paper. Simply type the relevant
information into the provided box and press the "add to the page" button.
Then enter the username and password. As always, if you have technical
problems with the page or need the username/password, email me.
Onto this week's paper!
Title: Scalable Percolation Search in Power Law Networks
Author: Nima Sarshar, P.Oscar Boykin, Vwani P. Roychowdhury
Abstract: We introduce a scalable searching algorithm for finding nodes
and contents in random networks with Power-Law (PL) and heavy-tailed
degree distributions. The network is searched using a probabilistic
broadcast algorithm, where a query message is relayed on each edge with
probability just above the bond percolation threshold of the network. We
show that if each node caches its directory via a short random walk, then
the total number of {\em accessible contents exhibits a first-order phase
transition}, ensuring very high hit rates just above the percolation
threshold. In any random PL network of size, $N$, and exponent, $2 \leq
\tau < 3$, the total traffic per query scales sub-linearly, while the
search time scales as $O(\log N)$. In a PL network with exponent, $\tau
\approx 2$, {\em any content or node} can be located in the network with
{\em probability approaching one} in time $O(\log N)$, while generating
traffic that scales as $O(\log^2 N)$, if the maximum degree, $k_{max}$, is
unconstrained, and as $O(N^{{1/2}+\epsilon})$ (for any $\epsilon>0$) if $
k_{max}=O(\sqrt{N})$. Extensive large-scale simulations show these scaling
laws to be precise. We discuss how this percolation search algorithm can
be directly adapted to solve the well-known scaling problem in
unstructured Peer-to-Peer (P2P) networks. Simulations of the protocol on
sample large-scale subnetworks of existing P2P services show that overall
traffic can be reduced by almost two-orders of magnitude, without any
significant loss in search performance.
Web link: http://arxiv.org/abs/cond-mat/0406152
Special thanks to Jose Nazario.
By the way, if you wonder what percolation is, here are a few potentially
helpful links...
http://www.anu.edu.au/Physics/courses/CP/percolation.html
http://fafnir.phyast.pitt.edu/myjava/perc/percTest.html
http://www.krl.caltech.edu/~adami/CD1/Percolation/percolation.html
If you know of other good links, I'd be glad to know about them.
October 12
This week, we have the honor of looking at the work of two more local
celebrities. Cosma and Kristina Shalizi will be present their newly
published research on quantifying complexity. As usual, we will meet at
Old Town Tavern at 7 pm on Tuesday, October 12 (corner of Liberty and
Ashley, in back under the large Rubenesque painting).
Title: Quantifying Self-Organization with Optimal Predictors
Authors: Cosma Rohilla Shalizi, Kristina Lisa Shalizi and Robert Haslinger
Journal: Physical Review Letters 93 (2004): 118701
Abstract: Despite broad interest in self-organizing systems, there are few
quantitative, experimentally applicable criteria for self-organization.
The existing criteria all give counter-intuitive results for important
cases. In this Letter, we propose a new criterion, namely, an internally
generated increase in the statistical complexity, the amount of
information required for optimal prediction of the system's dynamics. We
precisely define this complexity for spatially extended dynamical systems,
using the probabilistic ideas of mutual information and minimal sufficient
statistics. This leads to a general method for predicting such systems and
a simple algorithm for estimating statistical complexity. The results of
applying this algorithm to a class of models of excitable media (cyclic
cellular automata) strongly support our proposal.
Web link: http://www.arxiv.org/abs/nlin.AO/0409024
-------------------------------------------------------------------------
SWIKI UPDATE: Check the CSRG Swiki out for other proposed CSRG papers:
http://www.cscs.umich.edu:8000/CSRG/1
If you'd like to propose a paper, simply type your text into the provided
box and press the "add to the page" button. Then enter the username and
password.
If you have technical problems with the page, email me.
-------------------------------------------------------------------------
October 7
For our next meeting, Ted Belding, the original founder and moderator of
the Complex Systems Reading Group, has offered to present some of his own
agent-based modelling/archaeological research for next week. We will meet
at Old Town Tavern at 7 pm on Tuesday, October 5 (corner of Liberty and
Ashley, in back under the large Rubenesque painting).
Title: Nobility and Stupidity: Modeling the Evolution of Class Endogamy
Authors: Theodore C. Belding
Weblink: http://www.arxiv.org/abs/nlin.AO/0405048
Abstract: Class endogamy is a phenomenon in which nobles only marry other
nobles and commoners only marry other commoners. The origin of class
endogamy, and of social stratification in general, is a major open
question in archaeology. This paper implements a verbal model proposed by
Marcus and Flannery as a class of agent-based computer models by
generalizing and simplifying a mathematical model of marriage markets
developed by Burdett and Coles. One force that can produce class endogamy
occurs if agents are only willing to marry suitors having status no less
than some fixed value below the status of their highest-status suitor,
which they can learn. Another such force results if children inherit the
average of their parents' statuses. In contrast, status achieved over an
agent's lifetime can be viewed as noise, analogous to mutation in
biological evolution. I propose that class endogamy may have resulted
from the interaction of forces such as these, along with other factors
such as ideology. Simulation results are presented, and potential areas
for future research are sketched out. The validity of these models for
any particular culture depends, of course, on whether these forces were
actually operating in that society.
-------------------------------------------------------------------------
SWIKI UPDATE: Bill has added a paper to the Swiki, so check it out the
for the proposed CSRG papers,
http://www.cscs.umich.edu:8000/CSRG/1
If you'd like to propose a paper, simply type your text into the provided
box and press the "add to the page" button. Enter the username and
password.
If you have technical problems with the page, email me.
-------------------------------------------------------------------------
September 28
Now that we all have our email back, I have plenty of news. First of all,
let me tell you that the Complex Systems Reading Group will be meeting on
======> TUESDAYS <======
not Mondays. The Old Town Tavern tends to be quieter on Monday, but a
couple people couldn't make it on Monday, so Tuesdays it is.
The next CSRG meeting will be at Old Town Tavern at 7 pm on Tuesday,
September 28 (corner of Liberty and Ashley, in back under the
large Rubenesque painting).
Before I get to this week's paper, let me first say thanks for the
feedback on the proposed papers. As a general rule, I'll try to
final tally votes Thursday mornings. Check out the Swiki,
http://www.cscs.umich.edu:8000/CSRG/1
where a paper has been added. Even if you have not attended our
meetings, we'd be glad to get your votes and feedback. There were a
couple of viable candidates for this week that I'm sure we will be
reading in the coming weeks. For your convenience, I will try to put the
user/password for Swiki contributions in each of the emails...
To add to the CSRG Swiki, simply type your text into the provided box and
press the "add to the page" button. It will ask for a username and
password--please e-mail me if you do not have it.
If you have technical problems with the page, email me.
Without further ado, here is this week's paper...
Title: Network motifs in the transcriptional regulation network of
Escherichia coli
Authors: S Shen-Orr, R Milo, S Mangan & U Alon
Journal: Nature Genetics, 31:64-68 (2002).
Abstract: Little is known about the design principles of transcriptional
regulation networks that control gene expression in cells. Recent advances
in data collection and analysis, however, are generating unprecedented
amounts of information about gene regulation networks. To understand these
complex wiring diagrams, we sought to break down such networks into basic
building blocks. We generalize the notion of motifs, widely used in
sequence analysis, to the level of networks. We define 'network motifs' as
patterns of interconnections that recur in many different parts of a
network at frequencies much higher than those found in randomized
networks. We apply new algorithms for systematically detecting network
motifs to one of the best-characterized regulation networks, that of E.
coli. We find that much of the network is composed of repeated appearances
of three highly significant motifs. Each network motif has a specific
function in determining gene expression, such as generating temporal
expression signals. The motif structure also allows an easily
interpretable view of the entire known transcription network of the
organism. This approach may help define the basic computational elements
of other biological networks.
Web link:
http://www.weizmann.ac.il/mcb/UriAlon/Papers/network_motifs_in_coli.pdf
Also, check out Uri Alon's webpage for a number of other papers they've
written,
http://www.weizmann.ac.il/mcb/UriAlon/index.html
and let me know if you are interested in any others.
September 20
Here is a reminder that Complex Systems Reading Group will start the fall
off with an organizational meeting at Old Town Tavern at 7 pm on Monday,
September 20 (corner of Liberty and Ashley, in back under the
large Rubenesque painting).
There we'll be deciding when and where to meet this fall as well as
potential topics. Remember that, if you can't make it to this
meeting, you should send me an email with your suggestions about
better times and topics.
Check out the CSRG's new Swiki
http://www.cscs.umich.edu:8000/CSRG/1
where you give us direct input on possible papers and topics. The idea
is to have a place to explore potential discussion papers for the reading
group more closely and get feedback from the wider reading group.
The success of this webpage depends your input, so PLEASE check it out,
VOTE, and add more papers to it. If you don't like CSRG's candidate
papers, help point us in the right direction and suggest better ones.
IMPORTANT: To add to the CSRG Swiki, simply type your text into the
provided box and press the "add to the page" button. It will ask for a
username and password--please e-mail me if you do not have it.
If you have technical problems with the page, email me.
If you'd like to present some of your research to the group, we'd be
glad to hear about it. If you know of some nifty complex systems
papers and would like to bring 'em with you the old-fashioned way to the
meeting, that's fine too.
Let me know what you folks think, and I hope to see you there!
