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.
December 8 - last meeting of the semester
We had a request to look at Zipf's Law -- the one pertaining the language,
not cities. In particular, this long known power law relates word
frequency to its frequency ranking. Particularly, if you look at a sample
text, the word frequency of a particular word will go as 1/r, where r is
the word ranking (from most frequent on down). Without trying to spoil
anything, there are other, potentially more meaningful definitions.
Over the years, there have been heated discussions about how meaningful
this law actually is. G. Miller argued in 1957 that it arises from the
use of rank in the definition (for references on this side of the
argument, see references by W. Li below).
At any rate, for our meeting, we will be reading one of the lastest papers
in this discussion:
ZIPF'S LAW AND RANDOM TEXTS
by Ramon Ferrer i Cancho, and Ricard V. Sole
http://www.worldscinet.com/acs/05/0501/S0219525902000468.html
Random-text models have been proposed as an explanation for the power law
relationship between word frequency and rank, the so-called Zipf's law.
They are generally regarded as null hypotheses rather than models in the
strict sense. In this context, recent theories of language emergence and
evolution assume this law as a priori information with no need of
explanation. Here, random texts and real texts are compared through (a)
the so-called lexical spectrum and (b) the distribution of words having
the same length. It is shown that real texts fill the lexical spectrum
much more efficiently and regardless of the word length, suggesting that
the meaningfulness of Zipf's law is high.
Even if you haven't read the paper, feel free to drop by...
By the way, if you are interested in the particulars of the debate
mentioned above, check out for instance
W. Li, "Random texts exhibit Zipf's-law-like word frequency
distribution", IEEE Transactions on Information Theory, 38(6),
pp.1842-1845, 1992.
http://www.umich.edu/~warrencp/WLi.pdf
If you'd like refinements of this argument, you might want to check out
Letters to the Editor by Wentian Li, COMPLEXITY, 3(5):9-10 (1998)
http://linkage.rockefeller.edu/wli/pub/comp98_zipf.html
All of these papers are quite short.
If you are more interested in Zipf's law (we may not have found the best
articles), you might want to check out
http://linkage.rockefeller.edu/wli/zipf/
for references on Zipf's law and some other stuff as well.
December 1st
We will be exploring the nature of the hubs found in genetic networks...
The Connectivity of Large Genetic Networks: Design, History, or Mere
Chemistry?
by Andreas Wagner
http://www.santafe.edu/sfi/publications/wpabstract/200311062
This is a review of evolutionary explanations of broad-tailed connectivity
or degree distributions observed in metabolic networks and protein
interaction networks. Self-assembled chemical reaction networks show
degree distributions similar to those observed for metabolic networks,
which argues against the postulated role of natural selection in
maintaining this degree distribution. In addition, metabolic networks
contain traces of their ancient history in the form of highly connected
metabolites. Similarly to the degree distribution of metabolic networks,
that of protein interaction networks can be explained without resorting
to natural selection on the network level. I present data suggesting that
highly connected proteins are not distinguishably older than other
proteins, and explain this finding with a simple model of how a protein's
degree changes in evolutionary time.
November 24
We will be reading and discussing a paper about the information flow
within organizations and how it affects the structure of organizations...
Information exchange and the robustness of organizational networks
by Peter Sheridan Dodds, Duncan J. Watts, and Charles F. Sabel
Proceedings of the National Academy of Sciences, October 14, 2003, vol.
100(21):12516-12521.
http://www.umich.edu/~warrencp/Info_Exchange.pdf
The dynamics of information exchange is an important but understudied
aspect of collective communication, coordination, and problem solving in a
wide range of distributed systems, both physical (e.g., the Internet) and
social (e.g., business firms). In this paper, we introduce a model of
organizational networks according to which links are added incrementally
to a hierarchical backbone and test the resulting networks under variable
conditions of information exchange. Our main result is the identification
of a class of multiscale networks that reduce, over a wide range of
environments, the likelihood that individual nodes will suffer
congestion-related failure and that the network as a whole will
disintegrate when failures do occur. We call this dual robustness property of
multiscale networks "ultrarobustness." Furthermore, we find that
multiscale networks attain most of their robustness with surprisingly few
link additions, suggesting that ultrarobust organizational networks can be
generated in an efficient and scalable manner. Our results are directly
relevant to the relief of congestion in communication networks and also
more broadly to activities, like distributed problem solving, that require
individuals to exchange information in an unpredictable manner.
November 17
No Meeting This Week
November 10
This week's paper will switch gears a bit and explore potential models of
altruism...
The nature of human altruism
Ernst Fehr AND Urs Fischbacher
http://www.umich.edu/~warrencp/altruism.pdf
Some of the most fundamental questions concerning our evolutionary
origins, our social relations, and the organization of society are centred
around issues of altruism and selfishness. Experimental evidence
indicates that human altruism is a powerful force and is unique in the
animal world. However, there is much individual heterogeneity and the
interaction between altruists and selfish individuals is vital to human
cooperation. Depending on the environment, a minority of altruists can
force a majority of selfish individuals to cooperate or, conversely, a
few egoists can induce a large number of altruists to defect. Current
gene-based evolutionary theories cannot explain important patterns of
human altruism, pointing towards the importance of both theories of
cultural evolution as well as gene-culture co-evolution.
November 3
This week we will look a bit further at the idea of robustness and
modularity in biological networks...
The Role of Computation in Complex Regulatory Networks
by Pau Fernandez and Ricard V. Sole
http://www.santafe.edu/sfi/publications/wpabstract/200310055
Abstract:
Biological phenomena differ significantly from physical phenomena. At the
heart of this distinction is the fact that biological entities have
computational abilities and thus they are inherently difficult to
predict. This is the reason why simplified models that provide the minimal
requirements for computation turn out to be very useful to study networks
of many components. In this chapter, we briefly review the dynamical
aspects of models of regulatory networks, discussing their most salient
features, and we also show how these models can give clues about the
way in which networks may organize their capacity to evolve, by providing
simple examples of the implementation of robustness and modularity.
October 27
This week we will look at a paper that explores another aspect of
biology and networks - the structure of biochemical networks:
Biological Networks: The Tinkerer as an Engineer
by Uri Alon
http://www.umich.edu/~warrencp/1866.pdf
The viewpoint comments on recent advances in understanding the design
principles of biological networks. It highlights the surprising
discovery of "good-engineering" principles in biochemical circuitry that
evolved by random tinkering.
If you are further interested in this topic, check out the papers
and info on Alon's website:
http://www.weizmann.ac.il/mcb/UriAlon/
October 20
The paper for this week looks like an interesting concept in evolutionary
theory...
"A fitness cost of learning ability in Drosophila melanogaster [i.e. fruit flies]"
by Frederic Mery and Taseusz J. Kawecki
accepted by Proc. R. Soc. Lond. B and published online
http://www.unifr.ch/biol/ecology/kawecki/publications/procrsoc2003.pdf
Maintenance of substantial genetic variation for learning ability in many
animal populations suggests that learning ability has fitness costs, but
there is little empirical evidence for them. In this paper, we
demonstrate an evolutionary trade-off between learning ability and
competitive ability in Drosophila melanogaster. We show that the
evolution of an improved learning ability in replicated experimental fly
populations has been consistently associated with a decline of larval
competitive ability, compared with replicated control populations. The
competitive ability was not affected by crossing of the replicate
populations within each selection regime, excluding differential
inbreeding as a potential confounding factor. Our results provide
evidence for a constitutive fitness cost of learning ability, i.e. one
that is paid irrespective of whether or not the learning ability is
actually used.
A brief intro/synopsis of the work is given here...
http://www.newscientist.com/news/news.jsp?id=ns99994200
October 13
This week's paper combines two strands we've been looking at
this fall - communcation and networks - in the context of the brain's
neuronal network...
"Communication in Neuronal Networks"
by Simon B. Laughlin and Terrence J. Sejnowski
http://www.sciencemag.org/cgi/reprint/301/5641/1870.pdf
Brains perform with remarkable efficiency, are capable of prodigious
computation, and are marvels of communication. We are beginning to
understand some of the geometric, biophysical, and energy constraints
that have governed the evolution of cortical networks. To operate
efficiently within these constraints, nature has optimized the structure
and function of cortical networks with design principles similar to
those used in electronic networks. The brain also exploits the
adaptability of biological systems to reconfigure in response to
changing needs.
October 6
We will be looking at another classic paper, this time in encryption
theory (so get your decoder rings ready)...
"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"
by R.L. Rivest, A. Shamir, and L. Adleman
http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
Also, Bill Rand will talk about a proposed workshop related to Complex
Systems specifically oriented towards students working on their
dissertations. The workshop would be coordinated with the Complex Systems
Reading Group. Bill is working on applying for a POTENTIAL grant from
Rackham to create the workshop.
If you are interested in this group being proposed and interested in its
direction, especially if you are a grad student or faculty, stop by the
next CSRG meeting or email Bill Rand (wrand@umich.edu).
September 29
We will be looking at a classic paper in information theory, Claude E.
Shannon's A Mathematical Theory of Communication. Shannon was interested
in the issue of more efficiently transmitting information. The concepts he
developed in this paper have been "adopted by researchers in various disciplines
and applied to computer science, physics, molecular biology and biotechnology,
psychology, linguistics and communications." Here is a webpage with a simple
intro to Shannon's work:
http://www.exploratorium.edu/complexity/CompLexicon/Shannon.html
September 22
We will be looking at a recent Science paper in which the authors redo
Stanley Milgram's famous letter experiment, which demonstrated the small world
concept. Further, they try to understand why this experiment works...
An Experimental Study of Search in Global Social Networks
by Peter Sheridan Dodds, Roby Muhamad, Duncan J. Watts
Abstract:
We report on a global social-search experiment in which more than
60,000 e-mail users attempted to reach one of 18 target persons in 13
countries by forwarding messages to acquaintances. We find that
successful social search is conducted primarily through intermediate to
weak strength ties, does not require highly connected "hubs" to succeed,
and, in contrast to unsuccessful social search, disproportionately relies
on professional relationships. By accounting for the attrition of message
chains, we estimate that social searches can reach their targets in a
median of five to seven steps, depending on the separation of source and
target, although small variations in chain lengths and participation rates
generate large differences in target reachability. We conclude that
although global social networks are, in principle, searchable, actual
success depends sensitively on individual incentives.
If you are further interested in this experiment, check out
http://smallworld.columbia.edu/
September 15
Our first paper, described below, will be an application of network theory
to linguistics. Hope to see you there.
Universality in Syntactic Dependency Networks
http://www.santafe.edu/sfi/publications/wpabstract/200306042
by Ramon Ferrer, Ricard V. Sole, and Reinhard Kohler
Abstract:
Many languages are spoken on Earth. Despite their diversity,
many robust language universals are known to exist. All languages
share syntax, i.e. the ability to combine words to form sentences.
The origins of such a trait are an open debate. Most linguistic
universals are defined in a way that strictly confines them to a
linguistic context. This is not the case for the previously
unreported potential syntactic universals presented here. By using
recent developments from the statistical physics of complex networks,
we show that different syntactic dependency networks (from Czech,
German, and Romanian) share many non-trivial statistical patterns
such as the small world phenomenon, scaling in the distribution of
degrees, and disassortative mixing. Such previously unreported
features of syntax organization are not a trivial consequence of the
structure of sentences, but an emergent trait at the global scale.
Our results strongly suggest that existent languages might belong
to the same universality class as it is defined in physics.
I've had a request for a good introduction to this network theory that we
have been looking at a great deal recently (small worlds, scale-free
network, disassortative mixing, etc.). The great review of this area
of network theory has been put together by Mark Newman:
http://arxiv.org/abs/cond-mat/0303516
Since it's comprehensive, it is also rather than lengthy, so, if you're
just starting out, you might want to pick your spots. Another older
review has been written by Albert and Barabasi:
http://arxiv.org/abs/cond-mat/0106096
-Chris Warren <warrencp@umich.edu>
