• Credits: 1.0 - 3.0
• Class hours: Tuesday & Thursday, 4:00 - 5:15pm
• Class room: FA 109 (Fleischmann Agriculture)
• Call number: #32697
• Maximum Enrollment: 20
  
  
• Instructor: Dr. René Doursat
• 
• Web page: http://www.cse.unr.edu/~doursat
• Office: ARF 120
• Office hours: by appointment only
  
  
• Course flyer

Prerequisites

This advanced level interdisciplinary course welcomes graduate students in science and engineering, including: Computer Science & Engineering, Mathematics, Physics, Electrical Engineering, Chemistry, Biology, Biomedical Engineering, Earth Sciences and others.

Students should have good scientific programming skills, knowledge of calculus and linear algebra, a curious mind for exploring other sciences and a willingness to share their own field of expertise.

If you are interested in this seminar but do not feel you have the necessary computational and/or mathematical background, please contact me for possible arrangements (credit assignment follows a sliding scale; see below).

Organization

1. Introductory & guest lectures   I will give an introduction to complex systems and an overview of the topics addressed in the seminar. I will open, moderate and conclude the paper sessions. There will also be a few invited talks from other faculty members.
   
   
2. Paper presentations and discussions   Students will choose journal papers and book chapters from a reading list and prepare presentations for the class. There will be 1 or 2 required readings per session (possibly in combination with additional sources), to be read by everyone and presented by 1 or 2 students. Presentations must be prepared using Microsoft PowerPoint, contain figures and be emailed to the instructor. Speakers should also run a companion demo (ready-made or self-made) to illustrate the presented topic, including an exploration of the parameters and overview of the code. Total duration: 60 minutes, including the demo.
   
   
3. Homework assignments  Students will carry out "convince-yourself" experiments in the form of programming exercises, generally derived from the models reviewed in class. Some exercises will be based on the NetLogo platform, others written in a programmation language such as C/C++, Java, Fortran, MATLAB, etc. There will be approximately one homework assignment every other week (every 4 sessions).
   
   
4. Research project  Students will also complete a modeling & simulation project individually. This includes a program (written in the language of their choice), a technical report and a presentation to the class with a live demo. Topics chosen by the students must address complex systems and may be either related to the paper reviews, or overlapping with their current MSc or PhD work in progress, or fully original for this seminar. Important deadlines (see schedule below): 1 month after start = project proposals; 2 months after start = project status reports; end of the semester = final code, report and presentation.

Late policy: Late assignments of any kind (presentation, exercises, project) will not be accepted.

Academic integrity: All assignments must be prepared individually. Cheating and plagiarism will not be tolerated. Please refer to the UNR policy on Academic Standards.

Disability statement: If you have a disability for which you will need to request accommodations, please contact me or someone at the Disability Resource Center (Thompson Student Services - 107), as soon as possible.

Grading

Credits will be based on the involvement with assignments 2, 3 and 4 (see above) and attendance throughout the semester, according to the following sliding scale:

• 1.0 credit for attendance + completion of assignment 2
• 3.0 credits for attendance + completion of assignments 2, 3 and 4.

Grading from A to F will depend on the quality of the presentations and participation in the discussions (see 2) and, if elected, the successful completion of both programming exercises and research project (see 3 and 4).

Grading policy (tentative)

1. Attendance and participation in discussions: 40% (1.0 credit), 20% (3.0 credits)
2. Paper review presentation: 60% (1.0 credit), 20% (3.0 credits)
3. Programming exercises: 20% (3.0 credits)
4. Research project: 40% (3.0 credits)

Grading scale (tentative)

• 90% - 100%: A-, A
• 80% - 90%: B-, B, B+
• 65% - 80%: C-, C, C+
• 55% - 65%: D
• 0% - 55%: F

Description

This course explores the cross-disciplinary field of complex systems, or "complexity", through modeling and numerical simulation. Complex systems are characterized by a large number of elements interacting locally and combining their simple individual behaviors to produce an emergent behavior at a macroscopic scale. It is difficult or impossible to explain this emergence in analytical terms, whereas numerical models are often able to reproduce it and make valid predictions.

Processes of self-organization far from equilibrium are pervasive in nature (inanimate systems and living organisms) and human-made structures. Yet, because they raise the problem of the "form" and its appearance, emergent systems have been dismissed as nonobjective phenomena for a long time. Only recently did they become legitimate objects of study per se and a renewed focus of inquiry. After a boom in the 1980's and 1990's, they now promise to be the leading scientific paradigm of this century.

Increasing needs for prediction and control of geophysical, biological or societal structures have triggered rapid advances in the understanding of complexity at the transition between order and chaos. These important insights were made possible by the dramatic progress of information technology and computing power. Consequently, new algorithmic disciplines and new ways to solve problems were founded. These make use of massively parallel, decentralized systems that store and process information as single entities ("emergent computation"). Striking similarities in the observation of various complex phenomena created a fruitful exchange of ideas and techniques among disciplines—such as the ecological perspective on economics (based on the evolution and extinction of species) or the behavior of ant colonies exported to optimization problems.

Objectives

1. become familiarized with some of the most prominent case studies and models of complex systems across a variety of topics
   
   
2. understand the key concepts that unify these phenomena
   
   
3. introduce some of the theoretical and computational fields dealing with complexity and their important potential for applications

Schedule & Slides

See Bibliography below for references. The NetLogo demo scripts can be found in the /models folder of the NetLogo installation directory.

Date	Speaker	Topic	Presentation Papers	Background References	Presentation Demo
Jan 18	Dr. René Doursat	Lecture 1: Examples of complex systems (part I) and course organization
Jan 20	Dr. René Doursat	Lecture 2: Examples (part II) and concepts of complex systems
Jan 25	Christine Wilson	Topic review: Cellular Automata 1	• Gardner (1970) • Wolfram (2002), Ch. 1, 2 & 3	--	• Life • CA 1D Elementary
Jan 27	Richard Tillett	Topic review: Slime Mold	• Camazine et al. (2003), Ch. 8	• Höfer et al. (1995) • Pálsson & Cox (1996)	• B-Z Reaction • Slime
Feb 1	Rich Drewes	Topic review: Animal Patterns	• Wolfram (2002), pp422-429 • Bar-Yam (1997), 7.1, 7.2.1-7.2.5	• Young (1984)	• Fur
Feb 3	Kai Xu	Topic review: Ant Trails	• Camazine et al. (2003), Ch. 13	--	• Ants
Feb 8	Jeff Wallace	Topic review: Iterated Prisoner's Dilemma	• Flake (1998), Ch. 17 • Lindgren & Nordahl (1994)	• Axelrod & Hamilton (1981) • Nowak & May (1992)	• PD Evolutionary
Feb 10	Janet Snape	Topic review: Attractor Neural Networks	• Flake (1998), Ch. 18 • Bar-Yam (1997), 2.1 & 2.2	• Hopfield (1982)	• Hopfield Java applet
Feb 15	Dr. René Doursat	Lecture 3 (Review): Complex Networks	• Strogatz (2001) • Barabási & Bonabeau (2003) • Wang, X. F. (2002)	• Barabási & Albert (1999) • Watts & Strogatz (1998)	--
Feb 17	R. Drewes	Project proposal: Self-emergence of spatial structure of genetically distinct subpopulations
	J. Snape	Project proposal: Music networks as complex systems
	J. Wallace	Project proposal: Optimizing the game of Pente with a genetic algorithm
	K. Xu	Project proposal: Modeling collective insect behavior in a maze
Feb 22	Dr. René Doursat	Lecture 4 (Tutorial): Introduction to NetLogo			• Termites Tutorial
Feb 24	Richard Tillett	Topic review: Cellular Automata 2	• Wolfram (2002), Ch. 6 & 8	--	• CA 1D Elementary • Tree Simple
Mar 1	Dr. Allen Brady	Lecture 5 (Guest): Computability and Mechanism	• Wolfram (2002), Ch. 11 & 12 • Brady (1988)	--	--
Mar 3	Christine Wilson	Topic review: Flocking and Schooling	• Camazine et al. (2003), Ch. 11 • Huth & Wissel (1992) • Reynolds (1987)	--	• Flocking • Boids
Mar 8	Kai Xu	Topic review: Self-Assembling	• Bonabeau et al. (1999), Ch. 1 & 6 • Camazine et al. (2003), Ch. 19	• Theraulaz & Bonabeau (1995a) • Theraulaz & Bonabeau (1995b)	• Wasp Nest Building Simulator
Mar 10	Rich Drewes	Topic review: Spatial Ecology	• Solé & Goodwin (2000), Ch. 7 • Solé et al. (1992) • Bascompte, J. & Solé (1996) • May (1972) • Solé & Manrubia (1995)	--	--
Mar 15	Jeff Wallace	Topic review: Coevolution	• Solé & Goodwin (2000), Ch. 9 • Kauffman (1993), Ch. 2 & 6	• Kauffman & Weinberger (1989) • Kauffman & Johnsen (1991)	--
Mar 17	Janet Snape	Topic review: Autocatalytic and Genetic Nets	• Kauffman (1995), Ch. 2-5 • Kauffman (1969) • Kauffman (1986)	--	--
Mar 22	Dr. Thomas Nickles	Lecture 6 (Guest): Selection Theory vs. Complexity Theory?	• Campbell (1974) • Goodwin (1994), Ch. 5	--	--
Mar 24	R. Drewes	Project status: Self-emergence of spatial structure of genetically distinct subpopulations
	J. Snape	Project status: Music networks as complex systems
	J. Wallace	Project status: Optimizing the game of Pente with a genetic algorithm
	K. Xu	Project status: Modeling collective insect behavior in a maze
Mar 29	Spring break - no class
Mar 31	Spring break - no class
Apr 5	R. Tillett	Paper review: Self-Organization and Adaptation	• Cole (2002)	• (see Homework 2)	--
	R. Drewes	Paper review: Evolution of Complex Features (Avida)	• Lenski et al. (2003)	--	--
Apr 7	J. Wallace	Paper review: Cohort Genetic Algorithms	• Holland (2000)	--	--
	K. Xu	Paper review: Complex Food Webs	• Williams & Martinez (2000)	--	--
Apr 12	J. Snape	Paper review: Compositionality in Synfire Chains	• Abeles et al. (2004)	--	--
	C. Wilson	Paper review: Complex Biological Signaling	• Weng et al. (1999)	--	--
Apr 14	Sam Talaie	Guest talk: Tuning CA with GA	• Goldberg (1989), Ch. 1 • Louis & Raines (2003)	--	--
Apr 19	Dr. Guy Hoelzer	Lecture 7 (Guest): Natural Selection & Self-Organization	• Hoelzer et al. (2005) • Schneider & Kay (1994)	--	--
Apr 21	Project preparation - no class
Apr 26	Project preparation - no class
Apr 28	Dr. René Doursat	Lecture 8: Synchronization in Neural Networks	• Wang, D. L. (2000) • Bienenstock & Geman (1995) • Abeles et al. (2004)	--	--
May 3	J. Snape	Final project presentation: Music networks as complex systems
	J. Wallace	Final project presentation: Optimizing the game of Pente with a genetic algorithm
May 5	K. Chu	Final project presentation: Modeling collective insect behavior in a maze
	R. Drewes	Final project presentation: Self-emergence of spatial structure of genetically distinct subpopulations
	Dr. Guy Hoelzer	Lecture 7 (part II): Natural Selection & Self-Organization
	Dr. René Doursat	Conclusion/Discussion

Homework Assignments

See Bibliography below for references.

Start Date	Due Date	Assignment	References
Feb 22	Mar 1, 4pm	Sandpile Automaton	• Solé & Goodwin (2000), pp53-57 • Bak (1996)
Mar 1	Mar 22, 4pm	Fluid Neural Network Model of Ant Colony	• Solé & Goodwin (2000), pp157-164 • Solé et al. (1993) • Solé & Miramontes (1995)

Bibliography

References will be continuously added as the seminar unfolds. Please check again regularly.

Books with full online text are indicated in boldface. Other links refer either to a review of the book or to a presentation Web site that may include useful information and material such as table of contents, illustrations, selected chapters, companion software, etc.

Articles with online text are indicated with a direct link to the text or a link to the journal via the UNR Library subscription (you will need your library code outside of the university network). Individual third-party Web sites that host journal articles online are not considered course material as a whole, only the specific links that lead to the papers.

• Abeles, M., Hayon, G. and Lehmann, D. (2004) Modeling compositionality by dynamic binding of synfire chains. Journal of Computational Neuroscience, 17(2): 179-201.
  
  
• Axelrod, R. and Hamilton, W. D. (1981) The evolution of cooperation. Science, 211(4489): 1390-1396.
  
  
• Bak, P. (1996) How Nature Works: The Science of Self-Organized Criticality. Springer, New York.
  
  
• Barabási, A.-L. (2002) Linked: The New Science of Networks. Perseus Books.
  
  
• Barabási, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science, 286(5439): 509-512.
  
  
• Barabási, A.-L. and Bonabeau, E. (2003) Scale-free networks [9.3MB]. Scientific American, 288: 60-69.
  
  
• Bascompte, J. and Solé, R. V. (1996) Habitat fragmentation and extinction thresholds in spatially explicit models. Journal of Animal Ecology, 65: 465-473.
  
  
• Bar-Yam, Y. (1997) Dynamics of Complex Systems. Perseus Books. (Note: If the page does not appear, copy and paste the following URL in your browser: http://necsi.org/publications/dcs The problem seems to be caused by a server-side redirection to a nonconventional port, which your firewall might be blocking.)
  
  
• Bienenstock, E. and Geman, S. (1995) Compositionality in neural systems. In The Handbook of Brain Theory and Neural Networks, M. Arbib, ed., pp. 223-226. Bradford Books/MIT Press.
  
  
• Brady, A. H. (1988) The Busy Beaver game and the meaning of life. In The Universal Turing Machine: A Half-Century Survey, R. Herken, ed., pp. 259-277. Oxford University Press.
  
  
• Bonabeau, E., Dorigo, M. and Theraulaz, G. (1999) Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
  
  
• Camazine, S., Deneubourg, J.-L., Franks, N. R., Sneyd, J., Theraulaz, G. and Bonabeau, E. (2003) Self-Organization in Biological Systems. Princeton University Press.
  
  
• Campbell, D. T. (1974) Unjustified variation and selective retention in scientific discovery. In Studies in the Philosophy of Biology, F. J. Ayala and T. Dobzhansky, eds., pp. 139-161. University of California Press.
  
  
• Cocho, G., Perez-Pascual, R. and Rius, J. L. (1987) Discrete systems, cell-cell interactions and color pattern of animals. Journal of Theoretical Biology, 125(4): 419-435.
  
  
• Cole, B. J. (2002) Evolution of self-organized systems. Biol. Bull., 202(3): 256-261.
  
  
• Flake, G. (1998) The Computational Beauty of Nature. MIT Press.
  
  
• Gardner, M. (1970) Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life". Scientific American, 223(4): 120-123.
  
  
• Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.
  
  
• Goodwin, B. (1994) How the Leopard Changed Its Spots: The Evolution of Complexity. Princeton University Press.
  
  
• Hoelzer, G. A., Pepper, J. and Smith, E. (2005) On the logical relationship between natural selection and self-organization. (Submitted to Evolution.)
  
  
• Höfer, T., Sherratt, J. A. and Maini, P. K. (1995) Dictyostelium discoideum: cellular self-organisation in an excitable biological medium. Proc. R. Soc. Lond. B, 259: 249-257.
  
  
• Holland, J. H. (2000) Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation, 8(4): 373-391.
  
  
• Hopfield, J. J. (1982) Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA, 79(8): 2554-2558.
  
  
• Huth, A. and Wissel, C. (1992) The simulation of the movement of fish schools. Journal of Theoretical Biology, 156: 365-385.
  
  
• Kauffman, S. A. (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology, 22: 437-467.
  
  
• Kauffman, S. A. (1986) Autocatalytic sets of proteins. Journal of Theoretical Biology, 119: 1-24.
  
  
• Kauffman, S. A. (1993) The Origins of Order. Oxford University Press.
  
  
• Kauffman, S. A. (1995) At Home in the Universe: The Search for the Laws of Self-Organization and Complexity. Oxford University Press.
  
  
• Kauffman, S. A. and Johnsen, S. (1991) Coevolution to the edge of chaos: Coupled fitness landscapes, poised states, and coevolutionary avalanches. Journal of Theoretical Biology, 149: 467-505.
  
  
• Kauffman, S. A. and Weinberger, E. D. (1989) The NK model of rugged fitness landscapes and its application to maturation of the immune response. Journal of Theoretical Biology, 141: 211-245.
  
  
• Lenski, R. E., Ofria, C., Pennock, R. T. and Adami, C. (2003) The evolutionary origin of complex features. Nature, 423: 139-144.
  
  
• Lindgren, K. and Nordahl, M. G. (1994) Evolutionary dynamics of spatial games. Physica D, 75: 292-309.
  
  
• Louis, S. J. and Raines, G. L. (2003) Genetic algorithm calibration of probabilistic cellular automata for modeling mining permit activity. In Proceedings of the International Conference on Tools for AI (ICTAI) 2003, Sacramento, CA. IEEE Press.
  
  
• May, R. M. (1972) Will a large complex system be stable? Nature, 238: 413-414.
  
  
• Nowak, M. A. and May, R. M. (1992) Evolutionary games and spatial chaos. Nature, 359(6398): 826-829.
  
  
• Pálsson, E. and Cox, E. C. (1996) Origin and evolution of circular waves and spiral in Dictyostelium discoideum territories. Proc. Natl. Acad. Sci. USA, 93(3): 1151-1155.
  
  
• Reynolds, C. W. (1987) Flocks, herds and schools: a distributed behavioral model. Computer Graphics, 21(4): 25-34.
  
  
• Schneider, E. D. and Kay, J. J. (1994) Life as a manifestation of the second law of thermodynamics. Mathematical and Computer Modelling, 19(6-8): 25-48.
  
  
• Solé, R. V., Bascompte, J. and Valls, J. (1992) Stability and complexity of spatially extended two-species competition. Journal of Theoretical Biology, 159: 469-480.
  
  
• Solé, R. V. and Goodwin, B. C. (2000) Signs of Life: How Complexity Pervades Biology. Perseus Books.
  
  
• Solé, R. V. and Manrubia, S. C. (1995) Are rainforests self-organized in a critical state? Journal of Theoretical Biology, 173: 31-40.
  
  
• Solé, R. V. and Miramontes, O. (1995) Information at the edge of chaos in fluid neural networks. Physica D, 80: 171-180.
  
  
• Solé, R. V., Miramontes, O. and Goodwin, B. C. (1993) Oscillations and chaos in ant societies. Journal of Theoretical Biology, 161(3): 343-357. (Note: Despite the start date of 1/7/1995 mentioned in the UNR Library catalog, the full text of this article is available online.)
  
  
• Strogatz, S. H. (2001) Exploring complex networks. Nature, 410(6825): 268-276.
  
  
• Theraulaz, G. and Bonabeau, E. (1995a) Coordination in distributed building. Science, 269(5224): 686-688.
  
  
• Theraulaz, G. and Bonabeau, E. (1995b) Modelling the collective building of complex architectures in social insects with lattice swarms. Journal of Theoretical Biology, 177: 381-400.
  
  
• Wang, D. L. (2000) On connectedness: a solution based on oscillatory correlation. Neural Computation, 12: 131-139.
  
  
• Wang, X. F. (2002) Complex networks: topology, dynamics and synchronization. International Journal of Bifurcation and Chaos, 12(5): 885-916.
  
  
• Watts, D. J. and Strogatz, S. H. (1998) Collective dynamics of "small-world" networks. Nature, 393(6684): 440-442.
  
  
• Weaver, W. (1948) Science and Complexity. American Scientist, 36: 536.
  
  
• Weng, G., Bhalla, U. S. and Iyengar, R. (1999) Complexity in biological signaling systems. Science, 284(5411): 92-96.
  
  
• Williams, R. J. and Martinez, N. D. (2000) Simple rules yield complex food webs. Nature, 404(6774): 180-183.
  
  
• Wolfram, S. (2002) A New Kind of Science. Wolfram Media. (Note: After browsing a few pages, you will be asked to register your email for further reading. Refer to the FAQs about NKS|Online for help.)
  
  
• Young, D. (1984) A local activator-inhibitor model of vertebrate skin patterns. Mathematical Biosciences, 72: 51-58.

Useful Links

• Santa Fe Institute (SFI)
• New England Complex Systems Institute (NECSI)
• NetLogo
• Reviews of A New Kind of Science
• Self-Organized Networks (University of Notre Dame)

Topics Covered (Tentative)

This is an illustrative list of topics. It does not necessarily follow the chronological order of the sessions and is subject to modification and reorganization, depending on the number of participants. Not all authors or works are cited here, while some items cited here might not be addressed in class.

1. Introductory lectures
   
   
2. Physics & phase transitions
   • spin glasses, Ising model
   • Rayleigh-Bénard convection
   
   
3. Cellular automata
   • Conway's "Game of Life"
   • Wolfram's four classes of cellular automata
   • Langton's "lambda" parameter
   
   
4. Excitable media: chemical and cellular traveling waves
   • processes of reaction-diffusion
   • chemical oscillations and the Belousov-Zhabotinsky reaction
   • slime mold aggregation
   • pacemaker heart waves
   • wave dynamics in cortical neural networks
   
   
5. Developmental biology
   • Kauffman's gene networks (cellular differentiation)
   • pattern formation in organism development
   • Turing's morphogenesis paper (1952)
   • animal coats (spots & stripes)
   • butterfly wings
   • sea shells (cellular automata)
   • plant growth & phyllotaxis
   
   
6. Social insects and swarm intelligence
   • adaptive trail formation in ants
   • swarm raids in army ants
   • division of labor in ants
   • Dorigo's "Ant Colony Optimization" (ACO)
   • nest building by termites (continuous stigmergy)
   • nest building by wasps (discrete stigmergy)
   • comb patterns in honey bees
   
   
7. Coordinated population behavior
   • synchronized flashing in fireflies
   • fish schooling, bird flocking, cattle herding (Reynold's "boids")
   • Kennedy & Eberhardt's "Particle Swarm Optimization"
   • traffic jams
   
   
8. Ecosystems & economics
   • elements of Game Theory
   • spatially extended ecological systems
   • Robert Axelrod's "Iterated Prisoner's Dilemma"
   • competition & cooperation
   • Kaneko & Solé's "Coupled Map Lattices"
   • Jim Lovelock's "Daisy World" (homeostasis)
   • multi-population dynamics, community ecology, complex webs
   
   
9. Evolution & adaptation
   • Kauffman's random autocatalytic networks (origins of life)
   • Holland's "Genetic Algorithms"
   • variants: Evolutionary Programming, Evolutionary Strategies, Genetic Programming
   • Kauffman's NK models
   • rugged fitness landscapes
   • coevolution
   • explosions and extinctions
   • Langton's "Artificial Life"
   • Ray's "Tierra"
   
   
10. Neural networks & cognitive science
    • Hopfield's associative memory
    • perceptrons
    • spiking neuron models
    • synchronized oscillators
    • pulse coupled networks
    • synfire chains
    • chaotic EEG's
    
    
11. Complex networks
    • random networks
    • "small-world" networks
    • scale-free networks
    • network dynamics
    • spread of diseases
    • food webs
    • Internet & the Web