CS 790R SEMINAR
Computational Models of
Complex Systems


Dept of Computer Science & Engineering
UNR, Spring 2006
Course Information - Description - Objectives - Prerequisites - Textbooks - Topics
Organization - Grading - Schedule & Notes - Assignments - Bibliography - Useful links

Course Information

  • Credits: 1.0 - 3.0
  • Class hours: Monday & Wednesday, 2:30 - 3:45pm
  • Classroom: LME 316 (Laxalt Mineral Engineering)
  • Call number: #28013
  • Maximum Enrollment: 20

  • Instructor: Dr. René Doursat
  • Phone: (775) 327-2246 / (775) 784-6974
  • Web page: http://www.cse.unr.edu/~doursat
  • Office: SEM 230 (Scrugham Engineering-Mines)
  • Office hours (tentative):
    • Monday, 4 - 5:30pm
    • Tuesday, 5:30 - 7pm
    • Wednesday, 4 - 5:30pm
    • or by appointment

  • Course flyer

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.

Self-organized, decentralized and adaptive systems, whether physical, biological or human-made, are pervasive in the environment. Yet, because they raise the problem of the "form" and its appearance, emergent systems have been dismissed as nonobjective phenomena by strict reductionists 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 the 21st 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 created. These make use of massively parallel, distributed 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
(a) Cases of complex systems
in nature & human structures
(b) Unifying concepts
of complex systems
(c) Theoretical & computational
fields of complex systems
  • spin glasses, convection cells
  • excitable media & waves
  • genes & cell differentiation
  • animal patterns (coats, shells)
  • insect societies (ants, termites)
  • flocks, herds, schools
  • ecosystems & evolution
  • neurons, brain & cognition
  • cities, economy, Internet
  • etc.
  • emergence
  • self-organization
  • nonlinear dynamics
  • order, chaos, complexity
  • competition/cooperation
  • feedback & homeostasis
  • phase transitions
  • adaptation
  • edge of chaos, criticality
  • etc.
  • cellular automata
  • artificial life, virtual ants
  • swarm intelligence
  • pattern formation
  • oscillators, synchronization
  • Boolean networks
  • genetic algorithms
  • neural networks
  • small worlds
  • etc.
As it appears in this list, complex systems constitute an immensely vast interdisciplinary topic! Therefore, it cannot be the intention of this seminar to be exhaustive or systematic but rather to offer an exploration and discovery of complex systems through "sampling" of the literature and pragmatic experiments.

Prerequisites

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

Beside lectures by the instructor, students will read and present scientific articles (1.0 credit) and can also elect to complete modeling & simulation programming exercises and a term research project (3.0 credits).

Other faculty members will also be invited to give talks and co-supervise student projects, with potential for publications. Prerequisites: a basic mathematical background, a curious scientific mind and, if elected, good programming skills.

Textbooks

  • Required printed textbook
    Camazine, S., Deneubourg, J.-L., Franks, N. R., Sneyd, J., Theraulaz, G. and Bonabeau, E. (2003) Self-Organization in Biological Systems. Princeton University Press (ISBN: 0691116245).
  • Required online textbooks
    Wolfram, S. (2002) A New Kind of Science. Wolfram Media (ISBN: 1579550088).
    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.
    Bar-Yam, Y. (1997) Dynamics of Complex Systems. Perseus Books (ISBN: 0813341213).
    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.
  • Recommended textbooks
    Flake, G. (1998) The Computational Beauty of Nature. MIT Press (ISBN: 0262561271).
    Ball, P. (1999) The Self-Made Tapestry: Pattern Formation in Nature. Oxford University Press (ISBN: 0198502435).

Topics Covered (Tentative)

This is an illustrative list of topics. It does not necessarily follow the chronological order of the meetings 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. Overview of complex systems
    • Examples & principles
    • NetLogo platform

  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

Organization

  • Assignments

    1. Lectures & guest talks   I will give introductory lectures to complex systems, NetLogo and other complexity topics. I will open, moderate and conclude the students' paper presentations. 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. Quizzes   There may be announced and unannounced short quizzes about the contents of the articles and concepts reviewed in class. There will be no makeups for missed quizzes. The lowest quiz grade(s) might be dropped at the end of the term.

    4. 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).

    5. 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   There will be no team projects or reports in this class, therefore all assignments and quizzes must be prepared strictly individually. Any form of cheating such as plagiarism or ghostwriting will incur a severe penalty, usually failure in the course. 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 the instructor or someone at the Disability Resource Center (Thompson Student Services - 107) as soon as possible.

Grading (Tentative)

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

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

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

Grading Policy

  1.0 credit 3.0 credits
1. Attendance & participation 20% 10%
2. Paper presentations 60% 20%
3. Quizzes 20% 10%
4. Programming exercises -- 20%
5. Research project -- 40%
    Grading Scale

90% - 100%A-, A
80% - 89%B-, B, B+
65% - 79%C-, C, C+
55% - 64%D
0% - 54%F

Schedule & Course Notes

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 23 René
Doursat
Introduction 1 - Examples of complex systems (part I) and course organization
Jan 25 René
Doursat
Introduction 2 - Examples (part II) and concepts of complex systems
Jan 30 Jirakhom
Ruttanavakul
Cellular Automata 1 -
a. Introduction
b. Types of Behaviors
Gardner (1970)
Wolfram (2002), Ch. 1, 2
-- NetLogo: Life
Adam
Olenderski
Wolfram (2002), Ch. 3 -- NetLogo: CA 1D
Feb 1 Edward
Dochtermann
Cellular Automata 2 -
a. Types of Randomness
b. Models of Nature
Wolfram (2002), Ch. 7 -- --
Beifang Yi Wolfram (2002), Ch. 8 -- --
Feb 6 Kyle
McDermott
Pattern Formation 1 -
Reaction-Diffusion
Patterns
Wolfram (2002), pp. 422-429
Bar-Yam (1997), 7.1, 7.2.1-7.2.5
Pearson (1993)
Ball (1999), "Bodies"
Young (1984)
NetLogo: Fur
Texture Garden
Feb 8 Kara
DeSouza
Pattern Formation 2 -
Excitable Media
Waves
Camazine et al. (2003), Ch. 8
  (pp. 94-109 & Box 8.2)

Gerhardt & Schuster (1989)
Dewdney (1988)
Ball (1999), "Waves" NetLogo: B-Z
Feb 13 Erick
Luerken
Swarm Intelligence 1 -
Particle Swarm
Optimization
Camazine et al. (2003), Ch. 11
Reynolds (1987)
Kennedy & Eberhart (1995)
Kennedy & Eberhart (1997)
Huth & Wissel (1992)
Pomeroy (2003)
PSO site
NetLogo: Flocking
Boids
Feb 15 Edward
Dochtermann
Swarm Intelligence 2 -
Ant Colony
Optimization
Camazine et al. (2003), Ch. 13
Dorigo et al. (1996)
Dorigo & Gambardella (1997)
ACO site NetLogo: Ants
Feb 20 President's Day - no class
Feb 22 René
Doursat
Neural Networks 1 - Synchronization in Neural Networks
Feb 27 Olenderski Project Proposal - Robot Learning by Demonstration
McDermott Project Proposal - Retinal Remodeling by Ant Colonies
Zirpe Project Proposal - Neocortical Microcircuits
Ruttanavakul Project Proposal - A Dynamic-Network Robot Controller
Mar 1 Milind Zirpe Neural Networks 2 -
Attractor Networks
Flake (1998), Ch. 18
Bar-Yam (1997), 2.1 & 2.2
Hopfield (1982) NetLogo: Hopfield
Hopfield applet
Mar 6 Kara
DeSouza
Complex Networks 1 -
a. Small-World Experiments
b. Small-World Models
Travers & Milgram (1969)
Watts & Strogatz (1998)
Watts et al. (2002)
Watts (1999)
Small World Project
Big World critique
NetLogo: Small World
Small World applet
Oracle of Bacon
Kyle
McDermott
Mar 8 Jirakhom
Ruttanavakul
Complex Networks 2 -
a. Scale-Free Networks
b. Complex Networks
Barabási & Bonabeau (2003)
Barabási & Albert (1999)
Barabási et al. (2002)
Complex Network Center NetLogo: Attachment
Visual Complexity
René Doursat
Mar 13 Milind Zirpe Spatial Communities 1 -
a. Spatial Ecology (a)
b. Spatial Ecology (b)
Flake (1998), Ch. 12
Hassell et al. (1991)
Bascompte & Solé (1995)
Ball (1999), pp. 223-231 NetLogo: Predation
NetLogo: Pred. docked
Erick
Luerken
Mar 15 Adam
Olenderski
Spatial Communities 2 -
Evolutionary Game
Theory
Flake (1998), Ch. 17
Axelrod & Hamilton (1981)
Nowak & May (1992)
Ball (1999), pp. 231-242 NetLogo: PD Two Person
NetLogo: PD Evolutionary
Mar 20 Spring Break - no class
Mar 22 Spring Break - no class
Mar 27 Kara
DeSouza
Paper Review -
Conceptual Topology
Motter et al. (2002) -- --
Adam
Olenderski
Paper Review -
Small-World Language
Ferrer & Solé (2001) -- --
Mar 29 Kyle
McDermott
Paper Review -
Mobile Social Agents
González et al. (2006) -- --
Erick
Luerken
Paper Review -
Distance in Complex Nets
Gorman et al. (2004) -- --
Apr 3 Edward
Dochtermann
Paper Review -
Complex Food Webs
Williams & Martinez (2000) -- --
Jirakhom
Ruttanavakul
Paper Review -
Dynamics of Complex Nets
Strogatz (2001) -- --
Apr 5 Milind Zirpe Paper Review -
Self-Organized Behavior
Millor et al. (1999) -- --
Sebastian
Smith
Paper Review -
Plant Computation
Peak et al. (2004) -- --
Apr 10 Olenderski Project Status - Conceptual Structure of the Human Mind
McDermott Project Status - Retinal Remodeling by Ant Colonies
Zirpe Project Status - Neocortical Microcircuits
Ruttanavakul Project Status - A Dynamic-Network Robot Controller
Apr 12 Guy Hoelzer Invited Talk - Evolution as a complex process
Apr 17 Ruttanavakul Artificial Life 1 -
Genetic Algorithms
Goldberg (1989), Ch. 1
Flake (1998), Ch. 20
-- Introduction to GAs
GA Viewer
Smith
Apr 19 Dochtermann Artificial Life 2 -
Evolutionary Computation
Lenski et al. (2003) -- Avida
Zirpe
Apr 24 DeSouza Order for Free 1 -
Genetic Nets
Kauffman (1969) Kauffman (1995), Ch. 2-4
Order for Free
The Origin of Order
Investigations
--
McDermott
Apr 26 Luerken Order for Free 2 -
Autocatalytic Sets
Kauffman (1986) --
Olenderski
May 1 Allen Brady Invited Talk -
Computational Universality
Wolfram (2002), Ch. 11, 12
Brady (1988)
-- --
May 3 ALL Self-Organization 1
Camazine et al. (2003), Ch. 1-3
-- --
May 8 ALL Self-Organization 2
Camazine et al. (2003), Ch. 4-7
-- --
May 10 Prep Day - no class
May 11 Olenderski Project Final - Conceptual Structure of the Human Mind
McDermott Project Final - Retinal Remodeling by Ant Colonies
Zirpe Project Final - Neocortical Microcircuits
Ruttanavakul Project Final - A Dynamic-Network Robot Controller

Homework Assignments

See Bibliography below for references.

Start Date Due Date Assignment References
Jan 23 Jan 30, 2:30pm • Install and play with NetLogo on your computer NetLogo
Feb 13 Feb 22, 2:30pm Written Assignment 1
Written Assignment 2
--
Feb 22 Mar 1, 2:30pm Written Assignment 3 --
Mar 15 Mar 29, 2:30pm Written Assignment 4 --

Bibliography

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

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).

Books links refer either to the full text, a third-party review of the book or a presentation Web site that may include useful information and material such as table of contents, illustrations, selected chapters, companion software, etc.

Disclaimer: third-party Web sites offering online contents or reviews are not considered course material in their entirety, only the specific links presented here.

Useful Links

Course Information - Description - Objectives - Prerequisites - Textbooks - Topics
Organization - Grading - Schedule & Notes - Assignments - Bibliography - Useful links
Created and maintained by
René Doursat
Last update: 5/5/2006