MAT 351 Dynamics of Public Opinion About Political Ideologies Project

Description

Hi,I need detailed solutions for both parts of the final project.**The final project, a guideline for how to solve the project, as well as the book for the course have been attached**
Thanks 🙂

3 attachmentsSlide 1 of 3attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3

Unformatted Attachment Preview

MAT-351: MATHEMATICAL MODELING
Final Project
OVERVIEW
You are required to complete a final project on modeling in two parts. In the first part you are to write a
mathematical model for a given scenario and study its asymptotic behavior. The second part will have
you pick a specific case and carry out linear stability analysis of the model you wrote. The final report will
include the description of the model, some calculations, and analysis of the results of the models.
Course objectives covered in this project include CO1, CO2, CO3, CO4, CO5, CO6, CO7, CO8, CO9,
CO10, CO11, CO12, CO13
SCENARIO AND PROBLEM STATEMENTS
Consider the dynamics of public opinion about political ideologies.
For simplicity, let’s assume that there are only three options: Republican, Democrat, and Independent.
Republican and Democrat are equally attractive (or annoying, maybe) to people, with no fundamental
asymmetry between them. The popularities of Republican and Democrat ideologies can be represented
by two variables, pr and pd, respectively (0 ≤ pr ≤ 1; 0 ≤ pd ≤ 1; 0≤ pr + pd ≤ 1). This implies that 1- pr pd = pi represents the popularity of Independent. Assume that at each election poll, people will change
their ideological states among the three options according to their relative popularities in the previous poll.
For example, the rate of switching from option X to option Y can be considered proportional to (pY – pX) if
pY > pX, or 0 otherwise. You should consider six different cases of such switching behaviors (Republican
to Democrat, Republican to Independent, Democrat to Republican, Democrat to Independent,
Independent to Republican, and Independent to Democrat) and represent them in dynamical equations.
1. Complete a discrete-time mathematical model that describes this system, and simulate its
behavior. See what the possible final outcomes are after a sufficiently long time period. (Hint:
Revise Code 4.13 and use.)
For a specific case of pX, pY, and pZ:
2. Find equilibrium points.
3. Calculate the Jacobian matrix at each of the equilibrium points.
Copyright © 2020 by Thomas Edison State University. All rights reserved.
4. Calculate the eigenvalues of each of the matrices obtained above. (Hint: Revise Code 5.6 and
use.)
5. Based on the results, discuss the stability of each equilibrium point.
6. Why is an all Independent state (electorate) not feasible?
7. Give one major cause of change of state of convergence (Democrat or Republican) from election
to election in the context of this model.
WRITING AND RESEARCH RESOURCES
The following links provide online writing and research aids to help you with your paper assignments.
●
●
●
●
OWL (Online Writing Lab) at Purdue University
Writer’s Handbook, the Writing Center at the University of Wisconsin–Madison
APA Guidelines
Information Literacy for TESU Students (an online guide from the New Jersey State Library to
assist you in starting your research, searching databases for articles, citing sources, using ILLiad
to request books or articles, etc.)
Copyright © 2020 by Thomas Edison State University. All rights reserved.
Final Project Answer Guide
1. Let pd=X; pr=Y; and pi=Z. The X+Y+Z=1
Xt= Xt-1+r*max(Xt-1-Yt-1,0)*Yt-1+r*max(Xt-1-Zt-1,0)*Zt-1-r*max(Yt-1-Xt-1,0)*Xt-1-r*max(Zt-1-Xt-1,0)*Xt-1
Yt= Yt-1+r*max(Yt-1-Xt-1,0)*Xt-1+r*max(Yt-1-Zt-1,0)*Zt-1-r*max(Xt-1-Yt-1,0)*Yt-1-r*max(Zt-1-Yt-1,0)*Yt-1
Zt= Zt-1+r*max(Zt-1-Yt-1,0)*Yt-1+r*max(Zt-1-Xt-1,0)*Xt-1-r*max(Xt-1-Zt-1,0)*Zt-1-r*max(Yt-1-Zt-1,0)*Zt-1
To simulate, you need initial conditions. Hint: There are three main possible cases of initial conditions.
Case 1. X0>Y0,Z0
Case 2. Y0>X0,Z0
Case 3. Z0>X0,Y0
When you set the initial conditions, then the maximum function will no longer be necessary and the equations will
simplify as some terms will fall out due to being multiplied by zero. For example,
X0= 0.5
Y0= 0.3
Z0= 0.2
r=4/5
Our equations simplify as follows:
Xt= Xt-1+r(Xt-1-Yt-1)Yt-1+r(Xt-1-Zt-1)Zt-1
(1)
Yt= Yt-1+r(Yt-1-Zt-1)Zt-1-r(Xt-1-Yt-1)Yt-1
(2)
Zt= Zt-1-r(Xt-1-Zt-1)Zt-1-r(Yt-1-Zt-1)Zt-1
(3)
Simulate using a revised code 4.13. Depending on the initial conditions the model will converge to and all democratic
state (1,0,0), republican state (0,1,0), or independent state (0,0,1). With the above initial conditions, the model will
converge to (1,0,0).
2. Finding equilibrium points. At equilibrium Xt=x, Yt=y, and Zt=z. From equation (3) you will get z=(x+y)/2 or
z=0. Substituting z=(x+y)/2 in equations (1) and (2) and solving for x we get x=y or -5y. But -5y is impossible
since all values must be in the cube [0,1]^3. Also, z=1-x-y. Setting (x+y)/2=1-x-y, you get x+y=2/3. Hence z=1/3.
x=y and x+y=2/3 means x=1/3 and y=1/3. Hence an interior equilibrium at (1/3, 1/3, 1/3). From z=1-x-y we get
the boundary equilibrium points at (1,0,0), (0,1,0), and (0,0,1).
3. Jacobian Matrix:
1
2
4. To find the eigenvalues we have to solve the equation (1 − 𝜆) (5 − 𝜆) = 0
1
Hence the eigenvalues are 𝜆 = 1, 𝜆 = 5
5. Consequently, the dominant eigenvalue is 1, and the other ones have absolute value less than 1. The equilibrium
point is Lyapunov stable.
Finding the Jacobian matrix for (0,1,0) and (0,0,1) and their eigenvalues, you will see that the dominant
eigenvalue in each case has absolute value greater than 1, confirming that the equilibrium points unstable. Hence
for the initial condition (0.5, 0.3, 0.2) the model converges to (1,0,0).
Cases 2 and 3 can be verified accordingly. Notice that the equilibrium point (1/3, 1/3, 1/3) will be unstable for any
initial condition. Must be verified!
6. An all independent electorate is not feasible because each citizen who identifies as independent leans either
democratic or republican.
7. In the context of this model, a change from democratic to republican from election to election will be caused by a
change in initial condition. This means massive registration of first time voters at the beginning of the election
cycle by one or the other party.
Note: Since the Jacobian matrix depends on the constant of proportionality r, the numerical values of these
matrices will vary from student to student. Consequently, the eigenvalues will also vary. But the conclusions will
stay the same.
Introduction to the Modeling and Analysis of
Complex Systems
Hiroki Sayama
c 2015 Hiroki Sayama
ISBN:
978-1-942341-06-2 (deluxe color edition)
978-1-942341-08-6 (print edition)
978-1-942341-09-3 (ebook)
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike
3.0 Unported License.
You are free to:
Share—copy and redistribute the material in any medium or format
Adapt—remix, transform, and build upon the material
The licensor cannot revoke these freedoms as long as you follow the license terms. Under
the following terms:
Attribution—You must give appropriate credit, provide a link to the license, and indicate if
changes were made. You may do so in any reasonable manner, but not in any way that
suggests the licensor endorses you or your use.
NonCommercial—You may not use the material for commercial purposes.
ShareAlike—If you remix, transform, or build upon the material, you must distribute your
contributions under the same license as the original.
This publication was made possible by a SUNY Innovative Instruction Technology Grant
(IITG). IITG is a competitive grants program open to SUNY faculty and support staff
across all disciplines. IITG encourages development of innovations that meet the Power
of SUNY’s transformative vision.
Published by Open SUNY Textbooks, Milne Library
State University of New York at Geneseo
Geneseo, NY 14454
iii
About the Textbook
Introduction to the Modeling and Analysis of Complex Systems introduces students to
mathematical/computational modeling and analysis developed in the emerging interdisciplinary field of Complex Systems Science. Complex systems are systems made of a
large number of microscopic components interacting with each other in nontrivial ways.
Many real-world systems can be understood as complex systems, where critically important information resides in the relationships between the parts and not necessarily within
the parts themselves.
This textbook offers an accessible yet technically-oriented introduction to the modeling
and analysis of complex systems. The topics covered include: fundamentals of modeling,
basics of dynamical systems, discrete-time models, continuous-time models, bifurcations,
chaos, cellular automata, continuous field models, static networks, dynamic networks, and
agent-based models. Most of these topics are discussed in two chapters, one focusing on
computational modeling and the other on mathematical analysis. This unique approach
provides a comprehensive view of related concepts and techniques, and allows readers
and instructors to flexibly choose relevant materials based on their objectives and needs.
Python sample codes are provided for each modeling example.
About the Author
Hiroki Sayama, D.Sc., is an Associate Professor in the Department of Systems Science
and Industrial Engineering, and the Director of the Center for Collective Dynamics of
Complex Systems (CoCo), at Binghamton University, State University of New York. He
received his BSc, MSc and DSc in Information Science, all from the University of Tokyo,
Japan. He did his postdoctoral work at the New England Complex Systems Institute in
Cambridge, Massachusetts, from 1999 to 2002. His research interests include complex
dynamical networks, human and social dynamics, collective behaviors, artificial life/chemistry, and interactive systems, among others.
He is an expert of mathematical/computational modeling and analysis of various complex systems. He has published more than 100 peer-reviewed journal articles and conference proceedings papers and has edited eight books and conference proceedings about
complex systems related topics. His publications have acquired more than 2000 citations
as of July 2015. He currently serves as an elected Board Member of the International
Society for Artificial Life (ISAL) and as an editorial board member for Complex Adaptive
Systems Modeling (SpringerOpen), International Journal of Parallel, Emergent and Distributed Systems (Taylor & Francis), and Applied Network Science (SpringerOpen).
iv
Reviewer’s Notes
This book provides an excellent introduction to the field of modeling and analysis of complex systems to both undergraduate and graduate students in the physical sciences, social
sciences, health sciences, humanities, and engineering. Knowledge of basic mathematics is presumed of the reader who is given glimpses into the vast, diverse and rich world of
nonlinear algebraic and differential equations that model various real-world phenomena.
The treatment of the field is thorough and comprehensive, and the book is written in a
very lucid and student-oriented fashion. A distinguishing feature of the book, which uses
the freely available software Python, is numerous examples and hands-on exercises on
complex system modeling, with the student being encouraged to develop and test his or
her own code in order to gain vital experience.
The book is divided into three parts. Part I provides a basic introduction to the art
and science of model building and gives a brief historical overview of complex system
modeling. Part II is concerned with systems having a small number of variables. After
introducing the reader to the important concept of phase space of a dynamical system,
it covers the modeling and analysis of both discrete- and continuous-time systems in a
systematic fashion. A very interesting feature of this part is the analysis of the behavior of
such a system around its equilibrium state, small perturbations around which can lead to
bifurcations and chaos. Part III covers the simulation of systems with a large number of
variables. After introducing the reader to the interactive simulation tool PyCX, it presents
the modeling and analysis of complex systems (e.g., waves in excitable media, spread
of epidemics and forest fires) with cellular automata. It next discusses the modeling and
analysis of continuous fields that are represented by partial differential equations. Examples are diffusion-reaction systems which can exhibit spontaneous self-organizing behavior (e.g., Turing pattern formation, Belousov-Zhabotinsky reaction and Gray-Scott pattern
formation). Part III concludes with the modeling and analysis of dynamical networks and
agent-based models.
The concepts of emergence and self-organization constitute the underlying thread that
weaves the various chapters of the book together.
About the Reviewer: Dr. Siddharth G. Chatterjee received his Bachelor’s Degree in Technology (Honors) from the Indian Institute of Technology, Kharagpur, India, and M.S. and
Ph.D. degrees from Rensselaer Polytechnic Institute, Troy, New York, USA, all in Chemical Engineering. He has taught a variety of engineering and mathematical courses and
his research interests are the areas of philosophy of science, mathematical modeling and
simulation. Presently he is Associate Professor in the Department of Paper and Bioprocess Engineering at SUNY College of Environmental Science and Forestry, Syracuse,
v
New York. He is also a Fellow of the Institution of Engineers (India) and Member of the
Indian Institute of Chemical Engineers.
Sayama has produced a very comprehensive introduction and overview of complexity.
Typically, these topics would occur in many different courses, as a side note or possible
behavior of a particular type of mathematical model, but only after overcoming a huge
hurdle of technical detail. Thus, initially, I saw this book as a “mile-wide, inch-deep” approach to teaching dynamical systems, cellular automata, networks, and the like. Then
I realized that while students will learn a great deal about these topics, the real focus is
learning about complexity and its hallmarks through particular mathematical models in
which it occurs. In that respect, the book is remarkably deep and excellent at illustrating
how complexity occurs in so many different contexts that it is worth studying in its own
right. In other words, Sayama sort of rotates the axes from “calculus”, “linear algebra”,
and so forth, so that the axes are “self-organization”, “emergence”, etc. This means that I
would be equally happy to use the modeling chapters in a 100-level introduction to modeling course or to use the analysis chapters in an upper-level, calculus-based modeling
course. The Python programming used throughout provides a nice introduction to simulation and gives readers an excellent sandbox in which to explore the topic. The exercises
provide an excellent starting point to help readers ask and answer interesting questions
about the models and about the underlying situations being modeled. The logical structure of the material takes maximum advantage of early material to support analysis and
understanding of more difficult models. The organization also means that students experiencing such material early in their academic careers will naturally have a framework for
later studies that delve more deeply into the analysis and application of particular mathematical tools, like PDEs or networks.
About the Reviewer: Dr. Kris Green earned his Ph.D. in applied mathematics from the University of Arizona. Since then, he has earned the rank of full professor at St. John Fisher
College where he often teaches differential equations, mathematical modeling, multivariable calculus and numerical analysis, as well as a variety of other courses. He has guided
a number of successful undergraduate research projects related to modeling of complex
systems, and is currently interested in applications of such models to education, both in
terms of teaching and learning and of the educational system as a whole. Outside of the
office, he can often be found training in various martial arts or enjoying life with his wife
and two cats.
To Mari
Preface
This is an introductory textbook about the concepts and techniques of mathematical/computational modeling and analysis developed in the emerging interdisciplinary field of complex systems science. Complex systems can be informally defined as networks of many
interacting components that may arise and evolve through self-organization. Many realworld systems can be modeled and understood as complex systems, such as political
organizations, human cultures/languages, national and international economies, stock
markets, the Internet, social networks, the global climate, food webs, brains, physiological systems, and even gene regulatory networks within a single cell; essentially, they
are everywhere. In all of these systems, a massive amount of microscopic components
are interacting with each other in nontrivial ways, where important information resides in
the relationships between the parts and not necessarily within the parts themselves. It
is therefore imperative to model and analyze how such interactions form and operate in
order to understand what will emerge at a macroscopic scale in the system.
Complex systems science has gained an increasing amount of attention from both inside and outside of academia over the last few decades. There are many excellent books
already published, which can introduce you to the big ideas and key take-home messages
about complex systems. In the meantime, one persistent challenge I have been having in
teaching complex systems over the last several years is the apparent lack of accessible,
easy-to-follow, introductory-level technical textbooks. What I mean by technical textbooks
are the ones that get down to the “wet and dirty” details of how to build mathematical or
computational models of complex systems and how to simulate and analyze them. Other
books that go into such levels of detail are typically written for advanced students who are
already doing some kind of research in physics, mathematics, or computer science. What
I needed, instead, was a technical textbook that would be more appropriate for a broader
audience—college freshmen and sophomores in any science, technology, engineering,
and mathematics (STEM) areas, undergraduate/graduate students in other majors, such
as the social sciences, management/organizational sciences, health sciences and the humanities, and even advanced high school students looking for research projects who are
ix
x
interested in complex systems modeling.
This OpenSUNY textbook is my humble attempt to meet this need. As someone who
didn’t major in either physics or mathematics, and who moved away from the mainstream
of computer science, I thought I could be a good “translator” of technical material for
laypeople who don’t major in those quantitative fields. To make the material as tangible
as possible, I included a lot of step-by-step instructions on how to develop models (especially computer simulation codes), as well as many visuals, in this book. Those detailed
instructions/visuals may sometimes look a bit redundant, but hopefully they will make the
technical material more accessible to many of you. I also hope that this book can serve
as a good introduction and reference for graduate students and researchers who are new
to the field of complex systems.
In this textbook, we will use Python for computational modeling and simulation. Python
is a rapidly growing computer programming language widely used for scientific computing
and also for system development in the information technology industries. It is freely
available and quite easy to learn for non-computer science majors. I hope that using
Python as a modeling and simulation tool will help you gain some real marketable skills,
and it will thus be much more beneficial than using other pre-made modeling/simulation
software. All the Python sample codes for modeling examples are available from the
textbook’s website at http://bingweb.binghamton.edu/~sayama/textbook/, which are
directly linked from each code example shown in this textbook (if you are reading this
electronically). Solutions for the exercises are also available from this website.
To maintain a good balance between accessibility and technical depth/rigor, I have
written most of the topics in two chapters, one focusing on hands-on modeling work and
the other focusing on more advanced mathematical analysis. Here is a more specific
breakdown:
Preliminary chapters 1, 2
Modeling chapters 3, 4, 6, 10, 11, 13, 15, 16, 19
Analysis chapters 5, 7, 8, 9, 12, 14, 17, 18
The preliminary and modeling chapters are marked with an orange side bar at the top,
while the analysis chapters are marked with a blue side bar at the bottom. The modeling
chapters won’t require any in-depth mathematical skills; some basic knowledge of derivatives and probabilities is enough. The analysis chapters are based on a more solid understanding of calculus, differential equations, linear algebra, and probability and statistics.
I hope this unique way of organizing topics in two complementary chapters will provide
xi
a comprehensive view of the related concepts and techniques, as well as allow you to
flexibly choose relevant materials based on your learning/teaching objectives and needs.
If you are an instructor, here are some suggested uses for this textbook:
• One-semester course as an introduction to complex systems modeling
– Target audience: College freshmen or sophomores (or also for research projects
by advanced high school students)
– Chapters to be covered: Part I and some modeling chapters selected from
Parts II & III
• One-semester course as an introduction to dynamical systems
– Target audience: Senior undergraduate or graduate students
– Chapters to be covered: Parts I & II, plus Continuous Field Models chapters
(both modeling and analysis)
• One-semester advanced course on complex systems modeling and analysis
– Target audience: Graduate students who already know dynamical systems
– Chapters to be covered: Part III (both modeling and analysis)
• Two-semester course sequence on both modeling and analysis of complex systems
– Target audience: Senior undergraduate or graduate students
– Chapters to be covered: Whole textbook
Note that the chapters of this textbook are organized purely based on their content. They
are not designed to be convenient curricular modules that can be learned or taught in
similar amounts of time. Some chapters (especially the preliminary ones) are very short
and easy, while others (especially the analysis ones) are extensive and challenging. If you
are teaching a course using this book, it is recommended to allocate time and resources
to each chapter according to its length and difficulty level.
One more thing I need to note is that the contents of this book are focused on dynamical models, and as such, they are not intended to cover all aspects of complex systems
science. There are many important topics that are not included in the text because of
the limitation of space and time. For example, topics that involve probability, stochasticity,
and statistics, such as information theory, entropy, complexity measurement, stochastic
models, statistical analysis, and machine learning, are not discussed much in this book.
Fortunately, there are several excellent textbooks on these topics already available.
xii
This textbook was made possible, thanks to the help and support of a number of
people. I would like to first express my sincere gratitude to Ken McLeod, the former
Chair of the Department of Bioengineering at Binghamton University, who encouraged
me to write this textbook. The initial brainstorming discussions I had with him helped me
tremendously in shaping the basic topics and structure of this book. After all, it was Ken
who hired me at Binghamton, so I owe him a lot anyway. Thank you Ken.
My thanks also go to Yaneer Bar-Yam, the President of the New England Complex
Systems Institute (NECSI), where I did my postdoctoral studies (alas, way more than a
decade ago—time flies). I was professionally introduced to the vast field of complex systems by him, and the various research projects I worked on under his guidance helped
me learn many of the materials discussed in this book. He also gave me the opportunity
to teach complex systems modeling at the NECSI Summer/Winter Schools. This ongoing
teaching experience has helped me a lot in the development of the instructional materials
included in this textbook. I would also like to thank my former PhD advisor, Yoshio Oyanagi, former Professor at the University of Tokyo. His ways of valuing both scientific rigor
and intellectual freedom and creativity influenced me greatly, which are still flowing in my
blood.
This textbook uses PyCX, a simple Python-based complex systems simulation framework. Its GUI was developed by Chun Wong, a former undergraduate student at Binghamton University and now an MBA student at the University of Maryland, and Przemysław
Szufel and Bogumił Kamiński, professors at the Warsaw School of Economics, to whom I
owe greatly. If you find PyCX’s GUI useful, you should be grateful to them, not me. Please
send them a thank you note.
I thank Cyril Oberlander, Kate Pitcher, Allison Brown, and all others who have made
this wonderful OpenSUNY textbook program possible. Having this book with open access
to everyone in the world is one of the main reasons why I decided to write it in the first
place. Moreover, I greatly appreciate the two external reviewers, Kris Green, at St. John
Fisher College, and Siddharth G. Chatterjee, at SUNY College of Environmental Science
and Forestry, whose detailed feedback was essential in improving the quality and accuracy of the contents of this book. In particular, Kris Green’s very thorough, constructive,
extremely helpful comments have helped bring the scientific contents of this textbook up
to a whole new level. I truly appreciate his valuable feedback. I also thank Sharon Ryan
for her very careful copy editing for the final version of the manuscript, which greatly improved the quality of the text.
My thanks are also due to my fellow faculty members and graduate students at the
Center for Collective Dynamics of Complex Systems (CoCo) at Binghamton University,
including Shelley Dionne, Fran Yammarino, Andreas Pape, Ken Kurtz, Dave Schaffer, Yu
xiii
Chen, Hal Lewis, Vlad Miskovic, Chun-An Chou, Brandon Gibb, Genki Ichinose, David
Sloan Wilson, Prahalad Rao, Jeff Schmidt, Benjamin James Bush, Xinpei Ma, and Hyobin Kim, as well as other fantastic collaborators I was lucky enough to have outside
the campus, including Thilo Gross, René Doursat, László Barabási, Roberta Sinatra, Junichi Yamanoi, Stephen Uzzo, Catherine Cramer, Lori Sheetz, Mason Porter, Paul Trunfio,
Gene Stanley, Carol Reynolds, Alan Troidl, Hugues Bersini, J. Scott Turner, Lindsay Yazzolino, and many others. Collaboration with these wonderful people has given me lots of
insight and energy to work on various complex systems research and education projects.
I would also like to thank the people who gave me valuable feedback on the draft
versions of this book, including Barry Goldman, Blake Stacey, Ernesto Costa, Ricardo
Alvira, Joe Norman, Navdep Kaur, Dene Farrell, Aming Li, Daniel Goldstein, Stephanie
Smith, Hoang Peter Ta, Nygos Fantastico, Michael Chambers, and Tarun Bist. Needless
to say, I am solely responsible for all typos, errors, or mistakes remaining in this textbook.
I would greatly appreciate any feedback from any of you.
My final thanks go to a non-living object, my Lenovo Yoga 13 laptop, on which I was
able to write the whole textbook anytime, anywhere. It endured the owner’s careless
handling (which caused its touchscreen to crack) and yet worked pretty well to the end.
I hope you enjoy this OpenSUNY textbook and begin an exciting journey into complex
systems.
July 2015
Hiroki Sayama
Binghamton, NY / Natick, MA / Dresden, Germany
Contents
I
Preliminaries
1
1 Introduction
1.1 Complex Systems in a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Topical Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Fundamentals of Modeling
2.1 Models in Science and Engineering
2.2 How to Create a Model . . . . . . .
2.3 Modeling Complex Systems . . . . .
2.4 What Are Good Models? . . . . . . .
2.5 A Historical Perspective . . . . . . .
II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Systems with a Small Number of Variables
3
3
6
11
11
14
19
21
22
27
3 Basics of Dynamical Systems
29
3.1 What Are Dynamical Systems? . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Phase Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 What Can We Learn? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Discrete-Time Models I: Modeling
4.1 Discrete-Time Models with Difference Equations . . . . . .
4.2 Classifications of Model Equations . . . . . . . . . . . . . .
4.3 Simulating Discrete-Time Models with One Variable . . . .
4.4 Simulating Discrete-Time Models with Multiple Variables . .
4.5 Building Your Own Model Equation . . . . . . . . . . . . . .
4.6 Building Your Own Model Equations with Multiple Variables
xv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
35
36
39
46
51
55
xvi
CONTENTS
5 Discrete-Time Models II: Analysis
5.1 Finding Equilibrium Points . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Phase Space Visualization of Continuous-State Discrete-Time Models . . .
5.3 Cobweb Plots for One-Dimensional Iterative Maps . . . . . . . . . . . . . .
5.4 Graph-Based Phase Space Visualization of Discrete-State Discrete-Time
Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Variable Rescaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Asymptotic Behavior of Discrete-Time Linear Dynamical Systems . . . . . .
5.7 Linear Stability Analysis of Discrete-Time Nonlinear Dynamical Systems . .
6 Continuous-Time Models I: Modeling
6.1 Continuous-Time Models with Differential Equations . . . . . . .
6.2 Classifications of Model Equations . . . . . . . . . . . . . . . . .
6.3 Connecting Continuous-Time Models with Discrete-Time Models
6.4 Simulating Continuous-Time Models . . . . . . . . . . . . . . . .
6.5 Building Your Own Model Equation . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
7 Continuous-Time Models II: Analysis
7.1 Finding Equilibrium Points . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Phase Space Visualization . . . . . . . . . . . . . . . . . . . . . . .
7.3 Variable Rescaling . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 Asymptotic Behavior of Continuous-Time Linear Dynamical Systems
7.5 Linear Stability Analysis of Nonlinear Dynamical Systems . . . . . .
8 Bifurcations
8.1 What Are Bifurcations? . . . . . . . . . . . . . . .
8.2 Bifurcations in 1-D Continuous-Time Models . . .
8.3 Hopf Bifurcations in 2-D Continuous-Time Models
8.4 Bifurcations in Discrete-Time Models . . . . . . . .
9 Chaos
9.1 Chaos in Discrete-Time Models . .
9.2 Characteristics of Chaos . . . . . .
9.3 Lyapunov Exponent . . . . . . . .
9.4 Chaos in Continuous-Time Models
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
61
61
62
68
74
77
81
90
.
.
.
.
.
99
99
100
102
104
108
.
.
.
.
.
111
111
112
118
120
125
.
.
.
.
131
131
132
140
144
.
.
.
.
153
153
156
157
162
CONTENTS
III
xvii
Systems with a Large Number of Variables
171
10 Interactive Simulation of Complex Systems
10.1 Simulation of Systems with a Large Number of Variables
10.2 Interactive Simulation with PyCX . . . . . . . . . . . . .
10.3 Interactive Parameter Control in PyCX . . . . . . . . . .
10.4 Simulation without PyCX . . . . . . . . . . . . . . . . . .
.
.
.
.
173
173
174
180
181
.
.
.
.
.
185
185
190
192
200
201
.
.
.
.
209
209
211
215
219
.
.
.
.
.
.
227
227
229
236
241
249
259
.
.
.
.
269
269
273
275
285
11 Cellular Automata I: Modeling
11.1 Definition of Cellular Automata . . . . . . . . . . . .
11.2 Examples of Simple Binary Cellular Automata Rules
11.3 Simulating Cellular Automata . . . . . . . . . . . . .
11.4 Extensions of Cellular Automata . . . . . . . . . . .
11.5 Examples of Biological Cellular Automata Models . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12 Cellular Automata II: Analysis
12.1 Sizes of Rule Space and Phase Space . . . . . . . . . . . . . . . .
12.2 Phase Space Visualization . . . . . . . . . . . . . . . . . . . . . .
12.3 Mean-Field Approximation . . . . . . . . . . . . . . . . . . . . . . .
12.4 Renormalization Group Analysis to Predict Percolation Thresholds
13 Continuous Field Models I: Modeling
13.1 Continuous Field Models with Partial Differential Equations
13.2 Fundamentals of Vector Calculus . . . . . . . . . . . . . . .
13.3 Visualizing Two-Dimensional Scalar and Vector Fields . . .
13.4 Modeling Spatial Movement . . . . . . . . . . . . . . . . . .
13.5 Simulation of Continuous Field Models . . . . . . . . . . . .
13.6 Reaction-Diffusion Systems . . . . . . . . . . . . . . . . . .
14 Continuous Field Models II: Analysis
14.1 Finding Equilibrium States . . . . . . . . . . . . . . . . .
14.2 Variable Rescaling . . . . . . . . . . . . . . . . . . . . .
14.3 Linear Stability Analysis of Continuous Field Models . .
14.4 Linear Stability Analysis of Reaction-Diffusion Systems
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15 Basics of Networks
295
15.1 Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
15.2 Terminologies of Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . 296
xviii
15.3
15.4
15.5
15.6
CONTENTS
Constructing Network Models with NetworkX
Visualizing Networks with NetworkX . . . . .
Importing/Exporting Network Data . . . . . .
Generating Random Graphs . . . . . . . . .
16 Dynamical Networks I: Modeling
16.1 Dynamical Network Models . . . .
16.2 Simulating Dynamics on Networks
16.3 Simulating Dynamics of Networks
16.4 Simulating Adaptive Networks . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17 Dynamical Networks II: Analysis of Network Topologies
17.1 Network Size, Density, and Percolation . . . . . . . . .
17.2 Shortest Path Length . . . . . . . . . . . . . . . . . . .
17.3 Centralities and Coreness . . . . . . . . . . . . . . . .
17.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . .
17.5 Degree Distribution . . . . . . . . . . . . . . . . . . . .
17.6 Assortativity . . . . . . . . . . . . . . . . . . . . . . . .
17.7 Community Structure and Modularity . . . . . . . . . .
18 Dynamical Networks III: Analysis of Network Dynamics
18.1 Dynamics of Continuous-State Networks . . . . . . . .
18.2 Diffusion on Networks . . . . . . . . . . . . . . . . . .
18.3 Synchronizability . . . . . . . . . . . . . . . . . . . . .
18.4 Mean-Field Approximation of Discrete-State Networks
18.5 Mean-Field Approximation on Random Networks . . .
18.6 Mean-Field Approximation on Scale-Free Networks . .
19 Agent-Based Models
19.1 What Are Agent-Based Models? . .
19.2 Building an Agent-Based Model . . .
19.3 Agent-Environment Interaction . . .
19.4 Ecological and Evolutionary Models
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
303
310
314
320
.
.
.
.
325
325
326
348
360
.
.
.
.
.
.
.
371
371
377
380
386
389
396
400
.
.
.
.
.
.
405
405
407
409
416
417
420
.
.
.
.
427
427
431
440
448
Bibliography
465
Index
473
Part I
Preliminaries
1
Chapter 1
Introduction
1.1
Complex Systems in a Nutshell
It may be rather unusual to begin a textbook with an outright definition of a topic, but
anyway, here is what we mean by complex systems in this textbook1 :
Complex systems are networks made of a number of components that interact with
each other, typically in a nonlinear fashion. Complex systems may arise and evolve
through self-organization, such that they are neither completely regular nor completely random, permitting the development of emergent behavior at macroscopic
scales.
These properties can be found in many real-world systems, e.g., gene regulatory networks within a cell, physiological systems of an organism, brains and other neural systems, food webs, the global climate, stock markets, the Internet, social media, national
and international economies, and even human cultures and civilizations.
To better understand what complex systems are, it might help to know what they are
not. One example of systems that are not complex is a collection of independent components, such as an ideal gas (as discussed in thermodynamics) and random coin tosses
(as discussed in probability theory). This class of systems was called “problems of disorganized complexity” by American mathematician and systems scientist Warren Weaver
[2]. Conventional statistics works perfectly when handling such independent entities. Another example, which is at the other extreme, is a collection of strongly coupled compo1
In fact, the first sentence of this definition is just a bit wordier version of Herbert Simon’s famous definition in his 1962 paper [1]: “[A] complex system [is a system] made up of a large number of parts that
interact in a nonsimple way.”
3
4
CHAPTER 1. INTRODUCTION
nents, such as rigid bodies (as discussed in classical mechanics) and fixed coin tosses
(I’m not sure which discipline studies this). Weaver called this class of systems “problems of simplicity” [2]. In this class, the components of a system are tightly coupled to
each other with only a few or no degrees of freedom left within the system, so one can
describe the collection as a single entity with a small number of variables. There are very
well-developed theories and tools available to handle either case. Unfortunately, however,
most real-world systems are somewhere in between.
Complex systems science is a rapidly growing scientific research area that fills the
huge gap between the two traditional views that consider systems made of either completely independent or completely coupled components. This is the gap where what
Weaver called “problems of organized complexity” exist [2]. Complex systems science
develops conceptual, mathematical, and computational tools to describe systems made
of interdependent components. It studies the structural and dynamical properties of various systems to obtain general, cross-disciplinary implications and applications.
Complex systems science has multiple historical roots and topical clusters of concepts,
as illustrated in Fig. 1.1. There are two core concepts that go across almost all subareas
of complex systems: emergence and self-organization.
The idea of emergence was originally discussed in philosophy more than a century
ago. There are many natural phenomena where some property of a system observed
at macroscopic scales simply can’t be reduced to microscopic physical rules that drive
the system’s behavior. For example, you can easily tell that a dog wagging its tail is
alive, but it is extremely difficult to explain what kind of microscopic physical/chemical
processes going on in its body are making this organism “alive.” Another typical example
is your consciousness. You know you are conscious, but it is hard to describe what
kind of neurophysiological processes make you a “conscious” entity. Those macroscopic
properties (livingness, consciousness) are called emergent properties of the systems.
Despite its long history of discussion and debate, there are still a number of different definitions for the concept of emergence in complex systems science. However, the
one thing that is common in most of the proposed definitions is that the emergence is
about the system’s properties at different scales. If you observe a property at a macroscopic scale that is fundamentally different from what you would naturally expect from
microscopic rules, then you are witnessing emergence. More concisely, emergence is a
nontrivial relationship between the system’s properties at different scales. This definition
was proposed by complex systems scientist Yaneer Bar-Yam [4]. I will adopt this definition
since it is simple and consistent with most of the definitions proposed in the literature.
1.1. COMPLEX SYSTEMS IN A NUTSHELL
Figure 1.1: Visual, organizational map of complex systems science broken into seven
topical areas. The three circles on the left (Nonlinear Dynamics, Systems Theory, and
Game Theory) are the historical roots of complex systems science, while the other
four circles (Pattern Formation, Evolution and Adaptation, Networks, and Collective
Behavior) are the more recently studied topical areas. Created by the author and
available from Wikipedia [3].
5
6
CHAPTER 1. INTRODUCTION
Emergence is a nontrivial relationship between the properties of a system at microscopic and macroscopic scales. Macroscopic properties are called emergent when it
is hard to explain them simply from microscopic properties.
Another key idea of complex systems science is self-organization, which is sometimes confused with emergence. Some researchers even use these terms almost interchangeably. One clear distinction, though, is that, while emergence is about scale,
self-organization is about time (in addition to scale). Namely, you call something selforganizing when you observe that the system spontaneously organizes itself to produce
a nontrivial macroscopic structure and/or behavior (or “order,” if you will) as time progresses. In other words, self-organization is a dynamical process that looks as if it were
going against the second law of thermodynamics (which states that entropy of a closed
system increases monotonically over time). Many physical, biological, and social systems show self-organizing behavior, which could appear mysterious when people were
not aware of the possibility of self-organization. Of course, these systems are not truly
going against the law of thermodynamics, because they are open systems that are driven
by energy flow coming from and going to the outside of the system. In a sense, the idea
of self-organization gives a dynamical explanation for emergent properties of complex
systems.
Self-organization is a dynamical process by which a system spontaneously forms
nontrivial macroscopic structures and/or behaviors over time.
Around these two key ideas, there are several topical clusters, which are illustrated in
Fig. 1.1. Let’s quickly review them.
1.2
Topical Clusters
Nonlinear dynamics is probably the topical cluster that has the longest history, at least
from as far back as the 17th century when Isaac Newton and Gottfried Wilhelm Leibniz
invented calculus and differential equations. But it was found only in the 20th century that
systems that include nonlinearity in their dynamics could show some weird behaviors,
such as chaos [5, 6] (which will be discussed later). Here, nonlinearity means that the
outputs of a system are not given by a linear combination of the inputs. In the context
of system behavior, the inputs and outputs can be the current and next states of the
system, and if their relationship is not linear, the system is called a nonlinear system.
1.2. TOPICAL CLUSTERS
7
The possibility of chaotic behavior in such nonlinear systems implies that there will be
no analytical solutions generally available for them. This constitutes one of the several
origins of the idea of complexity.
Systems theory is another important root of complex systems science. It rapidly developed during and after World War II, when there was a huge demand for mathematical
theories to formulate systems that could perform computation, control, and/or communication. This category includes several ground-breaking accomplishments in the last century, such as Alan Turing’s foundational work on theoretical computer science [7], Norbert
Wiener’s cybernetics [8], and Claude Shannon’s information and communication theories
[9]. A common feature shared by those theories is that they all originated from some engineering discipline, where engineers were facing real-world complex problems and had to
come up with tools to meet societal demands. Many innovative ideas of systems thinking
were invented in this field, which still form the key components of today’s complex systems
science.
Game theory also has an interesting societal background. It is a mathematical theory,
established by John von Neumann and Oskar Morgenstern [10], which formulates the
decisions and behaviors of people playing games with each other. It was developed
during the Cold War, when there was a need to seek a balance between the two mega
powers that dominated the world at that time. The rationality of the game players was
typically assumed in many game theory models, which made it possible to formulate the
decision making process as a kind of deterministic dynamical system (in which either
decisions themselves or their probabilities could be modeled deterministically). In this
sense, game theory is linked to nonlinear dynamics. One of the many contributions game
theory has made to science in general is that it demonstrated ways to model and analyze
human behavior with great rigor, which has made huge influences on economics, political
science, psychology, and other areas of social sciences, as well as contributing to ecology
and evolutionary biology.
Later in the 20th century, it became clearly recognized that various innovative ideas
and tools arising in those research areas were all developed to understand the behavior
of systems made of multiple interactive components whose macroscopic behaviors were
often hard to predict from the microscopic rules or laws that govern their dynamics. In the
1980s, those systems began to be the subject of widespread interdisciplinary discussions
under the unified moniker of “complex systems.” The research area of complex systems
science is therefore inherently interdisciplinary, which has remained unchanged since the
inception of the field. The recent developments of complex systems research may be
roughly categorized into four topical clusters: pattern formation, evolution and adaptation,
networks, and collective behavior.
8
CHAPTER 1. INTRODUCTION
Pattern formation is a self-organizing process that involves space as well as time. A
system is made of a large number of components that are distributed over a spatial domain, and their interactions (typically local ones) create an interesting spatial pattern over
time. Cellular automata, developed by John von Neumann and Stanisław Ulam in the
1940s [11], are a well-known example of mathematical models that address pattern formation. Another modeling framework is partial differential equations (PDEs) that describe
spatial changes of functions in addition to their temporal changes. We will discuss these
modeling frameworks later in this textbook.
Evolution and adaptation have been discussed in several different contexts. One context is obviously evolutionary biology, which can be traced back to Charles Darwin’s evolutionary theory. But another, which is often discussed more closely to complex systems,
is developed in the “complex adaptive systems” context, which involves evolutionary computation, artificial neural networks, and other frameworks of man-made adaptive systems
that are inspired by biological and neurological processes. Called soft computing, machine learning, or computational intelligence, nowadays, these frameworks began their
rapid development in the 1980s, at the same time when complex systems science was
about to arise, and thus they were strongly coupled—conceptually as well as in the literature. In complex systems science, evolution and adaptation are often considered to
be general mechanisms that can not only explain biological processes, but also create
non-biological processes that have dynamic learning and creative abilities. This goes well
beyond what a typical biological study covers.
Finally, networks and collective behavior are probably the most current research fronts
of complex systems science (as of 2015). Each has a relatively long history of its own. In
particular, the study of networks was long known as graph theory in mathematics, which
was started by Leonhard Euler back in the 18th century. In the meantime, the recent boom
of network and collective behavior research has been largely driven by the availability of
increasingly large amounts of data. This is obviously caused by the explosion of the Internet and the WWW, and especially the rise of mobile phones and social media over the
last decade. With these information technology infrastructures, researchers are now able
to obtain high-resolution, high-throughput data about how people are connected to each
other, how they are communicating with each other, how they are moving geographically,
what they are interested in, what they buy, how they form opinions or preferences, how
they respond to disastrous events, and the list goes on and on. This allows scientists
to analyze the structure of networks at multiple scales and also to develop dynamical
models of how the collectives behave. Similar data-driven movements are also seen in
biology and medicine (e.g., behavioral ecology, systems biology, epidemiology), neuroscience (e.g., the Human Connectome Project [12]), and other areas. It is expected that
1.2. TOPICAL CLUSTERS
9
these topical areas will expand further in the coming decades as the understanding of
the collective dynamics of complex systems will increase their relevance in our everyday
lives.
Here, I should note that these seven topical clusters are based on my own view of
the field, and they are by no means well defined or well accepted by the community.
There must be many other ways to categorize diverse complex systems related topics.
These clusters are more or less categorized based on research communities and subject
areas, while the methodologies of modeling and analysis traverse across many of those
clusters. Therefore, the following chapters of this textbook are organized based on the
methodologies of modeling and analysis, and they are not based on specific subjects
to be modeled or analyzed. In this way, I hope you will be able to learn the “how-to”
skills systematically in the most generalizable way, so that you can apply them to various
subjects of your own interest.
Exercise 1.1 Choose a few concepts of your own interest from Fig. 1.1. Do
a quick online literature search for those words, using Google Scholar (http:
//scholar.google.com/), arXiv (http://arxiv.org/), etc., to find out more about
their meaning, when and how frequently they are used in the literature, and in what
context.
Exercise 1.2 Conduct an online search to find visual examples or illustrations of
some of the concepts shown in Fig. 1.1. Discuss which example(s) and/or illustration(s) are most effective in conveying the key idea of each concept. Then create
a short presentation of complex systems science using the visual materials you
selected.
Exercise 1.3 Think of other ways to organize the concepts shown in Fig. 1.1 (and
any other relevant concepts you want to include). Then create your own version of
a map of complex systems science.
Now we are ready to move on. Let’s begin our journey of complex systems modeling
and analysis.
Chapter 2
Fundamentals of Modeling
2.1
Models in Science and Engineering
Science is an endeavor to try to understand the world around us by discovering fundamental laws that describe how it works. Such laws include Newton’s law of motion, the
ideal gas law, Ohm’s law in electrical circuits, the conservation law of energy, and so on,
some of which you may have learned already.
A typical cycle of scientific effort by which scientists discover these fundamental laws
may look something like this:
1. Observe nature.
2. Develop a hypothesis that could explain your observations.
3. From your hypothesis, make some predictions that are testable through an experiment.
4. Carry out the experiment to see if your predictions are actually true.
• Yes → Your hypothesis is proven, congratulations. Uncork a champagne bottle
and publish a paper.
• No → Your hypothesis was wrong, unfortunately. Go back to the lab or the field,
get more data, and develop another hypothesis.
Many people think this is how science works. But there is at least one thing that is not
quite right in the list above. What is it? Can you figure it out?
11
12
CHAPTER 2. FUNDAMENTALS OF MODELING
As some of you may know already, the problem exists in the last part, i.e., when the
experiment produced a result that matched your predictions. Let’s do some logic to better
understand what the problem really is. Assume that you observed a phenomenon P in
nature and came up with a hypothesis H that can explain P . This means that a logical
statement H → P is always true (because you chose H that way). To prove H, you also
derived a prediction Q from H, i.e., another logical statement H → Q is always true, too.
Then you conduct experiments to see if Q can be actually observed. What if Q is actually
observed? Or, what if “not Q” is observed instead?
If “not Q” is observed, things are easy. Logically speaking, (H → Q) is equivalent to
(not Q → not H) because they are contrapositions of each other, i.e., logically identical
statements that can be converted from one to another by negating both the condition and
the consequence and then flipping their order. This means that, if not Q is true, then it
logically proves that not H is also true, i.e., your hypothesis is wrong. This argument is
clear, and there is no problem with it (aside from the fact that you will probably have to
redo your hypothesis building and testing).
The real problem occurs when your experiment gives you the desired result, Q. Logically speaking, “(H → Q) and Q” doesn’t tell you anything about whether H is true or not!
There are many ways your hypothesis could be wrong or insufficient even if the predicted
outcome was obtained in the experiment. For example, maybe another alternative hypothesis R could be the right one (R → P , R → Q), or maybe H would need an additional
condition K to predict P and Q (H and K → P , H and K → Q) but you were not aware
of the existence of K.
Let me give you a concrete example. One morning, you looked outside and found
that your lawn was wet (observation P ). You hypothesized that it must have rained while
you were asleep (hypothesis H), which perfectly explains your observation (H → P ).
Then you predicted that, if it rained overnight, the driveway next door must also be wet
(prediction Q that satisfies H → Q). You went out to look and, indeed, it was also wet
(if not, H would be clearly wrong). Now, think about whether this new observation really
proves your hypothesis that it rained overnight. If you think critically, you should be able to
come up with other scenarios in which both your lawn and the driveway next door could
be wet without having a rainy night. Maybe the humidity in the air was unusually high,
so the condensation in the early morning made the ground wet everywhere. Or maybe a
fire hydrant by the street got hit by a car early that morning and it burst open, wetting the
nearby area. There could be many other potential explanations for your observation.
In sum, obtaining supportive evidence from experiments doesn’t prove your hypothesis in a logical sense. It only means that you have failed to disprove your hypothesis.
However, many people still believe that science can prove things in an absolute way. It
2.1. MODELS IN SCIENCE AND ENGINEERING
13
can’t. There is no logical way for us to reach the ground truth of nature1 .
This means that all the “laws of nature,” including those listed previously, are no more
than well-tested hypotheses at best. Scientists have repeatedly failed to disprove them,
so we give them more credibility than we do to other hypotheses. But there is absolutely
no guarantee of their universal, permanent correctness. There is always room for other
alternative theories to better explain nature.
In this sense, all science can do is just build models of nature. All of the laws of nature
mentioned earlier are also models, not scientific facts, strictly speaking. This is something
every single person working on scientific research should always keep in mind.
I have used the word “model” many times already in this book without giving it a definition. So here is an informal definition:
A model is a simplified representation of a system. It can be conceptual, verbal,
diagrammatic, physical, or formal (mathematical).
As a cognitive entity interacting with the external world, you are always creating a
model of something in your mind. For example, at this very moment as you are reading
this textbook, you are probably creating a model of what is written in this book. Modeling
is a fundamental part of our daily cognition and decision making; it is not limited only to
science.
With this understanding of models in mind, we can say that science is an endless effort
to create models of nature, because, after all, modeling is the one and only rational approach to the unreachable reality. And similarly, engineering is an endless effort to control
or influence nature to make something desirable happen, by creating and controlling its
models. Therefore, modeling occupies the most essential part in any endeavor in science
and engineering.
Exercise 2.1 In the “wet lawn” scenario discussed above, come up with a few
more alternative hypotheses that could explain both the wet lawn and the wet
driveway without assuming that it rained. Then think of ways to find out which
hypothesis is most likely to be the real cause.
1
This fact is deeply related to the impossibility of general system identification, including the identification
of computational processes.
14
CHAPTER 2. FUNDAMENTALS OF MODELING
Exercise 2.2 Name a couple of scientific models that are extensively used in
today’s scientific/engineering fields. Then investigate the following:
• How were they developed?
• What made them more useful than earlier models?
• How could they possibly be wrong?
2.2
How to Create a Model
There are a number of approaches for scientific model building. My favorite way of classifying various kinds of modeling approaches is to put them into the following two major
families:
Descriptive modeling In this approach, researchers try to specify the actual state
of a system at a given time point (or at multiple time points) in a descriptive
manner. Taking a picture, creating a miniature (this is literally a “model” in the
usual sense of the word), and writing a biography of someone, all belong to
this family of modeling effort. This can also be done using quantitative methods (e.g., equations, statistics, computational algorithms), such as regression
analysis and pattern recognition. They all try to capture “what the system looks
like.”
Rule-based modeling In this approach, researchers try to come up with dynamical rules that can explain the observed behavior of a system. This allows researchers to make predictions of its possible (e.g., future) states. Dynamical
equations, theories, and first principles, which describe how the system will
change and evolve over time, all belong to this family of modeling effort. This
is usually done using quantitative methods, but it can also be achieved at conceptual levels as well (e.g., Charles Darwin’s evolutionary theory). They all try
to capture “how the system will behave.”
Both modeling approaches are equally important in science and engineering. For
example, observation of planetary movement using telescopes in the early 17th century
generated a lot of descriptive information about how they actually moved. This information
was already a model of nature because it constituted a simplified representation of reality.
2.2. HOW TO CREATE A MODEL
15
In the meantime, Newton derived the law of motion to make sense out of observational
information, which was a rule-based modeling approach that allowed people to make
predictions about how the planets would/could move in the future or in a hypothetical
scenario. In other words, descriptive modeling is a process in which descriptions of a
system are produced and accumulated, while rule-based modeling is a process in which
underlying dynamical explanations are built for those descriptions. These two approaches
take turns and form a single cycle of the scientific modeling effort.
In this textbook, we will focus on the latter, the rule-based modeling approach. This is
because rule-based modeling plays a particularly important role in complex systems science. More specifically, developing a rule-based model at microscopic scales and studying its macroscopic behaviors through computer simulation and/or mathematical analysis
is almost a necessity to understand emergence and self-organization of complex systems. We will discuss how to develop rule-based models and what the challenges are
throughout this textbook.
A typical cycle of rule-based modeling effort goes through the following steps (which
are similar to the cycle of scientific discoveries we discussed above):
1. Observe the system of your interest.
2. Reflect on the possible rules that might cause the system’s characteristics that were
seen in the observation.
3. Derive predictions from those rules and compare them with reality.
4. Repeat the above steps to modify the rules until you are satisfied with the model (or
you run out of time or funding).
This seems okay, and it doesn’t contain the logical problem of “proving a hypothesis”
that we had before, because I loosened the termination criteria to be your satisfaction
as a researcher. However, there is still one particular step that is fundamentally difficult.
Which step do you think it is?
Of course, each of the four steps has its own unique challenges, but as an educator
who has been teaching complex systems modeling for many years, I find that the second
step (“Reflect on possible rules that might cause the system’s characteristics seen in
the observation.”) is particularly challenging to modelers. This is because this step is
so deeply interwoven with the modeler’s knowledge, experience, and everyday cognitive
processes. It is based on who you are, what you know, and how you see the world—it
is, ultimately, a personal thinking process, which is very difficult to teach or to learn in a
structured way.
16
CHAPTER 2. FUNDAMENTALS OF MODELING
Let me give you some examples to illustrate my point. The following figure shows
an observation of a system over time. Can you create a mathematical model of this
observation?
Some quantity
Time
Figure 2.1: Observation example 1.
This one should be quite easy, because the observed data show that nothing changed
over time. The description “no change” is already a valid model written in English, but if
you prefer writing it in mathematical form, you may want to write it as
(2.1)
x(t) = C
or, if you use a differential equation,
dx
= 0.
dt
(2.2)
Coming up with these models is a no brainer, because we have seen this kind of behavior
many times in our daily lives.
Here is another example. Can you create a mathematical model of this observation?
Some quantity
Time
Figure 2.2: Observation example 2.
2.2. HOW TO CREATE A MODEL
17
Now we see some changes. It seems the quantity monotonically increased over time.
Then your brain must be searching your past memories for a pattern that looks like this
curve you are looking at, and you may already have come up with a phrase like “exponential growth,” or more mathematically, equations like
x(t) = aebt
(2.3)
dx
= bx.
dt
(2.4)
or
This may be easy or hard, depending on how much knowledge you have about such
exponential growth models.
In the meantime, if you show the same curve to middle school students, they may
proudly say that this must be the right half of a flattened parabola that they just learned
about last week. And there is nothing fundamentally wrong with that idea. It could be a
right half of a parabola, indeed. We never know for sure until we see what the entire curve
looks like for −∞ < t < ∞. Let’s move on to a more difficult example. Create a mathematical model of the following observation. Some quantity Time Figure 2.3: Observation example 3. It is getting harder. Unless you have seen this kind of dynamic behavior before, you will have a hard time coming up with any concise explanation of it. An engineer might say, “This is a sawtooth wave,” or a computer scientist might say, “This is time mod something.” Or, an even more brilliant answer could come from an elementary school kid, saying, “This must be months in a calendar!” (which is equivalent to what the computer scientist said, by the way). In either case, people tend to map a new observation to something they already know in their mind when they create a model. 18 CHAPTER 2. FUNDAMENTALS OF MODELING This last example is the toughest. Create a mathematical model of the following observation. Some quantity Time Figure 2.4: Observation example 4. Did you come up with any ideas? I have seen only a few people who were able to make reasonable models of this observation throughout my career. The reason why this example is so hard to model is because we don’t see this kind of behavior often in our lives. We are simply not experienced with it. We don’t have a good mental template to use to capture the essence of this pattern2 . I hope that these examples have made my point clear by now. Coming up with a model is inherently a personal process, which depends on your own knowledge, experience, and worldview. There is no single algorithm or procedure you can follow to develop a good model. The modeling process is a full-scale interaction between the external world and your whole, intellectual self. To become a good modeler, you will need to gain diverse knowledge and experience and develop rich worldviews. This is why I said it would be very difficult to be taught. Exercise 2.3 Create a few different models for each of the examples shown above. Discuss how those models differ from each other, and what you should do to determine which model is more appropriate as an explanation of the observed behavior. 2 For those who are curious—this kind of curve could be generated by raising a sine or cosine function of time to an odd number (e.g., sin3 (t), cos5 (t)), but I am not sure if knowing this would ever help you in your future career. 2.3. MODELING COMPLEX SYSTEMS 2.3 19 Modeling Complex Systems The challenge in developing a model becomes particularly tough when it comes to the modeling of complex systems, because their unique properties (networks, nonlinearity, emergence, self-organization, etc.) are not what we are familiar with. We usually think about things on a single scale in a step-by-step, linear chain of reasoning, in which causes and effects are clearly distinguished and discussed sequentially. But this approach is not suitable for understanding complex systems where a massive amount of components are interacting with each other interdependently to generate patterns over a broad range of scales. Therefore, the behavior of complex systems often appears to contradict our everyday experiences. As illustrated in the examples above, it is extremely difficult for us to come up with a reasonable model when we are facing something unfamiliar. And it is even more difficult to come up with a reasonable set of microscopic rules that could explain the observed macroscopic properties of a system. Most of us are simply not experienced enough to make logical connections between things at multiple different scales. How can we improve our abilities to model complex systems? The answer might be as simple as this: We need to become experienced and familiar with various dynamics of complex systems to become a good modeler of them. How can we become experienced? This is a tricky question, but thanks to the availability of the computers around us, computational modeling and simulation is becoming a reasonable, practical method for this purpose. You can construct your own model with full details of microscopic rules coded into your computer, and then let it actually show the macroscopic behavior arising from those rules. Such computational modeling and simulation is a very powerful tool that allows you to gain interactive, intuitive (simulated) experiences of various possible dynamics that help you make mental connections between micro- and macroscopic scales. I would say there are virtually no better tools available for studying the dynamics of complex systems in general. There are a number of pre-built tools available for complex systems modeling and simulation, including NetLogo [13], Repast [14], MASON [15], Golly [16], and so on. You could also build your own model by using general-purpose computer programming languages, including C, C++, Java, Python, R, Mathematica, MATLAB, etc. In this textbook, we choose Python as our modeling tool, specifically Python 2.7, and use PyCX [17] to build interactive dynamic simulation models3 . Python is free and widely used in scien3 For those who are new to Python programming, see Python’s online tutorial at https://docs.python. org/2/tutorial/index.html. Several pre-packaged Python distributions are available for free, such as Anaconda (available from http://continuum.io/downloads) and Enthought Canopy (available from 20 CHAPTER 2. FUNDAMENTALS OF MODELING tific computing as well as in the information technology industries. More details of the rationale for this choice can be found in [17]. When you create a model of a complex system, you typically need to think about the following: 1. What are the key questions you want to address? 2. To answer those key questions, at what scale should you describe the behaviors of the system’s components? These components will be the “microscopic” components of the system, and you will define dynamical rules for their behaviors. 3. How is the system structured? This includes what those microscopic components are, and how they will be interacting with each other. 4. What are the possible states of the system? This means describing what kind of dynamical states each component can take. 5. How does the state of the system change over time? This includes defining the dynamical rules by which the components’ states will change over time via their mutual interaction, as well as defining how the interactions among the components will change over time. Figuring out the “right” choices for these questions is by no means a trivial task. You will likely need to loop through these questions several times until your model successfully produces behaviors that mimic key aspects of the system you are trying to model. We will practice many examples of these steps throughout this textbook. Exercise 2.4 Create a schematic model of some real-world system of your choice that is made of many interacting components. Which scale do you choose to describe the microscopic components? What are those components? What states can they take? How are those components connected? How do their states change over time? After answering all of these questions, make a mental prediction about what kind of macroscopic behaviors would arise if you ran a computational simulation of your model. https://enthought.com/products/canopy/). A recommended environment is Anaconda’s Python code editor named “Spyder.” 2.4. WHAT ARE GOOD MODELS? 2.4 21 What Are Good Models? You can create various kinds of models for a system, but useful ones have several important properties. Here is a very brief summary of what a good model should look like: A good model is simple, valid, and robust. Simplicity of a model is really the key essence of what modeling is all about. The main reason why we want to build a model is that we want to have a shorter, simpler description of reality. As the famous principle of Occam’s razor says, if you have two models with equal predictive power, you should choose the simpler one. This is not a theorem or any logically proven fact, but it is a commonly accepted practice in science. Parsimony is good because it is economical (e.g., we can store more models within the limited capacity of our brain if they are simpler) and also insightful (e.g., we may find useful patterns or applications in the models if they are simple). If you can eliminate any parameters, variables, or assumptions from your model without losing its characteristic behavior, you should. Validity of a model is how closely the model’s prediction agrees with the observed reality. This is of utmost importance from a practical viewpoint. If your model’s prediction doesn’t reasonably match the observation, the model is not representing reality and is probably useless. It is also very important to check the validity of not only the predictions of the model but also the assumptions it uses, i.e., whether each of the assumptions used in your model makes sense at its face value, in view of the existing knowledge as well as our common sense. Sometimes this “face validity” is more important in complex systems modeling, because there are many situations where we simply can’t conduct a quantitative comparison between the model prediction and the observational data. Even if this is the case, you should at least check the face validity of your model assumptions based on your understanding about the system and/or the phenomena. Note that there is often a trade-off between trying to achieve simplicity and validity of a model. If you increase the model complexity, you may be able to achieve a better fit to the observed data, but the model’s simplicity is lost and you also have the risk of overfitting— that is, the model prediction may become adjusted too closely to a specific observation at the cost of generalizability to other cases. You need to strike the right balance between those two criteria. Finally, robustness of a model is how insensitive the model’s prediction is to minor variations of model assumptions and/or parameter settings. This is important because there are always errors when we create assumptions about, or measure parameter values from, 22 CHAPTER 2. FUNDAMENTALS OF MODELING the real world. If the prediction made by your model is sensitive to their minor variations, then the conclusion derived from it is probably not reliable. But if your model is robust, the conclusion will hold under minor variations of model assumptions and parameters, therefore it will more likely apply to reality, and we can put more trust in it. Exercise 2.5 Humanity has created a number of models of the solar system in its history. Some of them are summarized below: • Ptolemy’s geocentric model (which assumes that the Sun and other planets are revolving around the Earth) • Copernicus’ heliocentric model (which assumes that the Earth and other planets are revolving around the Sun in concentric circular orbits) • Kepler’s laws of planetary motion (which assumes that the Earth and other planets are revolving in elliptic orbits, at one of whose foci is the Sun, and that the area swept by a line connecting a planet and the Sun during a unit time period is always the same) • Newton’s law of gravity (which assumes that a gravitational force between two objects is proportional to their masses and inversely proportional to their distance squared) Investigate these models, and compare them in terms of simplicity, validity and robustness. 2.5 A Historical Perspective As the final section in this chapter, I would like to present some historical perspective of how people have been developing modeling methodologies over time, especially those for complex systems (Fig. 2.5). Humans have been creating descriptive models (diagrams, pictures, physical models, texts, etc.) and some conceptual rule-based models since ancient times. More quantitative modeling approaches arose as more advanced mathematical tools became available. In the descriptive modeling family, descriptive statistics is among such quantitative modeling approaches. In the rule-based modeling family, dynamical equations (e.g., differential equations, difference equations) began to be used to quantitatively formulate theories that had remained at conceptual levels before. During the second half of the 20th century, computational tools became available to researchers, which opened up a whole new area of computational modeling approaches 2.5. A HISTORICAL PERSPECTIVE 23 rule-based descriptive theories diagrams pictures dynamical equations agent-based models statistics physical models texts network models cellular automata Figure 2.5: Schematic illustration of how modeling methodologies have developed historically. 24 CHAPTER 2. FUNDAMENTALS OF MODELING for complex systems modeling. The first of this kind was cellular automata, a massive number of identical finite-state machines that are arranged in a regular grid structure and update their states dynamically according to their own and their neighbors’ states. Cellular automata were developed by John von Neumann and Stanisław Ulam in the 1940s, initially as a theoretical medium to implement self-reproducing machines [11], but later they became a very popular modeling framework for simulating various interesting emergent behaviors and also for more serious scientific modeling of spatio-temporal dynamics [18]. Cellular automata are a special case of dynamical networks whose topologies are limited to regular grids and whose nodes are usually assumed to be homogeneous and identical. Dynamical networks formed the next wave of complex systems modeling in the 1970s and 1980s. Their inspiration came from artificial neural network research by Warren McCulloch and Walter Pitts [19] as well as by John Hopfield [20, 21], and also from theoretical gene regulatory network research by Stuart Kauffman [22]. In this modeling framework, the topologies of systems are no longer constrained to regular grids, and the components and their connections can be heterogeneous with different rules and weights. Therefore, dynamical networks include cellular automata as a special case within them. Dynamical networks have recently merged with another thread of research on topological analysis that originated in graph theory, statistical physics, social sciences, and computational science, to form a new interdisciplinary field of network science [23, 24, 25]. Finally, further generalization was achieved by removing the requirement of explicit network topologies from the models, which is now called agent-based modeling (ABM). In ABM, the only requirement is that the system is made of multiple discrete “agents” that interact with each other (and possibly with the environment), whether they are structured into a network or not. Therefore ABM includes network models and cellular automata as its special cases. The use of ABM became gradually popular during the 1980s, 1990s, and 2000s. One of the primary driving forces for it was the application of complex systems modeling to ecological, social, economic, and political processes, in fields like game theory and microeconomics. The surge of genetic algorithms and other population-based search/optimization algorithms in computer science also took place at about the same time, which also had synergistic effects on the rise of ABM. I must be clear that the historical overview presented above is my own personal view, and it hasn’t been rigorously evaluated or validated by any science historians (therefore this may not be a valid model!). But I hope that this perspective is useful in putting various modeling frameworks into a unified, chronological picture. The following chapters of this textbook roughly follow the historical path of the models illustrated in this perspective. 2.5. A HISTORICAL PERSPECTIVE 25 Exercise 2.6 Do a quick online literature search to find a few scientific articles that develop or use mathematical/computational models. Read the articles to learn more about their models, and map them to the appropriate locations in Fig. 2.5. Part II Systems with a Small Number of Variables 27 Chapter 3 Basics of Dynamical Systems 3.1 What Are Dynamical Systems? Dynamical systems theory is the very foundation of almost any kind of rule-based models of complex systems. It considers how systems change over time, not just static properties of observations. A dynamical system can be informally defined as follows1 : A dynamical system is a system whose state is uniquely specified by a set of variables and whose behavior is described by predefined rules. Examples of dynamical systems include population growth, a swinging pendulum, the motions of celestial bodies, and the behavior of “rational” individuals playing a negotiation game, to name a few. The first three examples sound legitimate, as those are systems that typically appear in physics textbooks. But what about the last example? Could human behavior be modeled as a deterministic dynamical system? The answer depends on how you formulate the model using relevant assumptions. If you assume that individuals make decisions always perfectly rationally, then the decision making process becomes deterministic, and therefore the interactions among them may be modeled as a deterministic dynamical system. Of course, this doesn’t guarantee whether it is a good model or not; the assumption has to be critically evaluated based on the criteria discussed in the previous chapter. Anyway, dynamical systems can be described over either discrete time steps or a continuous time line. Their general mathematical formulations are as follows: 1 A traditional definition of dynamical systems considers deterministic systems only, but stochastic (i.e., probabilistic) behaviors can also be modeled in a dynamical system by, for example, representing the probability distribution of the system’s states as a meta-level state. 29 30 CHAPTER 3. BASICS OF DYNAMICAL SYSTEMS Discrete-time dynamical system xt = F (xt−1 , t) (3.1) This type of model is called a difference equation, a recurrence equation, or an iterative map (if there is no t on the right hand side). Continuous-time dynamical system dx = F (x, t) dt (3.2) This type of model is called a differential equation. In either case, xt or x is the state variable of the system at time t, which may take a scalar or vector value. F is a function that determines the rules by which the system changes its state over time. The formulas given above are first-order versions of dynamical systems (i.e., the equations don’t involve xt−2 , xt−3 , . . ., or d2 x/dt2 , d3 x/dt3 , . . .). But these first-order forms are general enough to cover all sorts of dynamics that are possible in dynamical systems, as we will discuss later. Exercise 3.1 Have you learned of any models in the natural or social sciences that are formulated as either discrete-time or continuous-time dynamical systems as shown above? If so, what are they? What are the assumptions behind those models? Exercise 3.2 What are some appropriate choices for state variables in the following systems? • population growth • swinging pendulum • motions of celestial bodies • behavior of “rational” individuals playing a negotiation game 3.2. PHASE SPACE 3.2 31 Phase Space Behaviors of a dynamical system can be studied by using the concept of a phase space, which is informally defined as follows: A phase space of a dynamical system is a theoretical space where every state of the system is mapped to a unique spatial location. The number of state variables needed to uniquely specify the system’s state is called the degrees of freedom in the system. You can build a phase space of a system by having an axis for each degree of freedom, i.e., by taking each state variable as one of the orthogonal axes. Therefore, the degrees of freedom of a system equal the dimensions of its phase space. For example, describing the behavior of a ball thrown upward in a frictionless vertical tube can be specified with two scalar variables, the ball’s position and velocity, at least until it hits the bottom again. You can thus create its phase space in two dimensions, as shown in Fig. 3.1. Position x Velocity v Velocity v Position x Figure 3.1: A ball thrown upward in a vertical tube (left) and a schematic illustration of its phase space (right). The dynamic behavior of the ball can be visualized as a static trajectory in the phase space (red arrows). One of the benefits of drawing a phase space is that it allows you to visually represent the dynamically changing behavior of a system as a static trajectory in it. This provides a lot of intuitive, geometrical insight into the system’s dynamics, which would be hard to infer if you were just looking at algebraic equations. 32 CHAPTER 3. BASICS OF DYNAMICAL SYSTEMS Exercise 3.3 In the example above, when the ball hits the floor in the vertical tube, its kinetic energy is quickly converted into elastic energy (i.e., deformation of the ball), and then it is converted back into kinetic energy again (i.e., upward velocity). Think about how you can illustrate this process in the phase space. Are the two dimensions enough or do you need to introduce an additional dimension? Then try to illustrate the trajectory of the system going through a bouncing event in the phase space. 3.3 What Can We Learn? There are several important things you can learn from phase space visualizations. First, you can tell from the phase space what will eventually happen to a system’s state in the long run. For a deterministic dynamical system, its future state is uniquely determined by its current state (hence, the name “deterministic”). Trajectories of a deterministic dynamical system will never branch off in its phase space (though they could merge), because if they did, that would mean that multiple future states were possible, which would violate the deterministic nature of the system. No branching means that, once you specify an initial state of the system, the trajectory that follows is uniquely determined too. You can visually inspect where the trajectories are going in the phase space visualization. They may diverge to infinity, converge to a certain point, or remain dynamically changing yet stay in a confined region in the phase space from which no outgoing trajectories are running out. Such a converging point or a region is called an attractor. The concept of attractors is particularly important for understanding the self-organization of complex systems. Even if it may look magical and mysterious, self-organization of complex systems can be understood as a process whereby the system is simply falling into one of the attractors in a high-dimensional phase space. Second, you can learn how a system’s fate depends on its initial state. For each attractor, you can find the set of all the initial states from which you will eventually end up falling into that attractor. This set is called the basin of attraction of that attractor. If you have more than one attractor in the phase space (and/or if the phase space also shows divergence to infinity), you can divide the phase space into several different regions. Such a “map” drawn on the phase space reveals how sensitive the system is to its initial conditions. If one region is dominating in the phase space, the system’s fate doesn’t depend much on its initial condition. But if there are several regions that are equally represented in the phase space, the system’s fate sensitively depends on its initial condition. 3.3. WHAT CAN WE LEARN? 33 Another thing you can learn from phase space visualizations is the stability of the system’s states. If you see that trajectories are converging to a certain point or area in the phase space, that means the system’s state is stable in that area. But if you see trajectories are diverging from a certain point or area, that means the system’s state is unstable in that area. Knowing system stability is often extremely important to understand, design, and/or control systems in real-world applications. The following chapters will put a particular emphasis on this stability issue. Exercise 3.4 Where are the attractor(s) in the phase space of the bouncing ball example created in Exercise 3.3? Assume that every time the ball bounces it loses a bit of its kinetic energy. Exercise 3.5 of attraction. For each attractor obtained in Exercise 3.4 above, identify its basin Exercise 3.6 For each of the phase spaces shown below, identify the following: • attractor(s) • basin of attraction for each attractor • stability of the system’s state at several locations in the phase space Exercise 3.7 Consider a market where two equally good products, A and B, are competing with each other for market share. There is a customer review website 34 CHAPTER 3. BASICS OF DYNAMICAL SYSTEMS where users of each product submit their ratings. Since there is no actual difference in the product quality, the average rating scores are about the same between the two products, but the customers can also see the total number of submitted ratings for each product, which shows how popular the product is in the market. Customers tend to adopt a more popular choice. Answer the following questions: • What would the phase space of this system look like? • Are there any attractors? Are there any basins of attraction? • How does the system’s fate depend on its initial state? • If you were in charge of marketing product A, what would you do? Chapter 4 Discrete-Time Models I: Modeling 4.1 Discrete-Time Models with Difference Equations Discrete-time models are easy to understand, develop and simulate. They are easily implementable for stepwise computer simulations, and they are often suitable for modeling experimental data that are almost always already discrete. Moreover, they can represent abrupt changes in the system’s states, and possibly chaotic dynamics, using fewer variables than their continuous-time counterparts (this will be discussed more in Chapter 9). The discrete-time models of dynamical systems are often called difference equations, because you can rewrite any first-order discrete-time dynamical system with a state variable x (Eq. (3.1)), i.e., (4.1) xt = F (xt−1 , t) into a “difference” form ∆x = xt − xt−1 = F (xt−1 , t) − xt−1 , (4.2) which is mathematically more similar to differential equations. But in this book, we mostly stick to the original form that directly specifies the next value of x, which is more straightforward and easier to understand. Note that Eq. (4.1) can also be written as (4.3) xt+1 = F (xt , t), which is mathematically equivalent to Eq. (4.1) and perhaps more commonly used in the literature. But we will use the notation with xt , xt−1 , xt−2 , etc., in this textbook, because 35 36 CHAPTER 4. DISCRETE-TIME MODELS I: MODELING this notation makes it easier to see how many previous steps are needed to calculate the next step (e.g., if the right hand side contains xt−1 and xt−2 , that means you will need to know the system’s state in previous two steps to determine its next state). From a difference equation, you can produce a series of values of the state variable x over time, starting with initial condition x0 : {x0 , x1 , x2 , x3 , . . .} (4.4) This is called time series. In this case, it is a prediction made using the difference equation model, but in other contexts, time series also means sequential values obtained by empirical observation of real-world systems as well. Here is a very simple example of a discrete-time, discrete-state dynamical system. The system is made of two interacting components: A and B. Each component takes one of two possible states: Blue or red. Their behaviors are determined by the following rules: • A tries to stay the same color as B. • B tries to be the opposite color of A. These rules are applied to their states simultaneously in discrete time steps. Exercise 4.1 Write the state transition functions FA (sA , sB ) and FB (sA , sB ) for this system, where sA and sB are the states of A and B, respectively. Exercise 4.2 Produce a time series of (sA , sB ) starting with an initial condition with both components in blue, using the model you created. What kind of behavior will arise? 4.2 Classifications of Model Equations There are some technical terminologies I need to introduce before moving on to further discussions: Linear system A dynamical equation whose rules involve just a linear combination of state variables (a constant times a variable, a constant, or their sum). 4.2. CLASSIFICATIONS OF MODEL EQUATIONS 37 Nonlinear system Anything else (e.g., equation involving squares, cubes, radicals, trigonometric functions, etc., of state variables). First-order system A difference equation whose rules involve state variables of the immediate past (at time t − 1) onlya . Higher-order system Anything else. a Note that the meaning of “order” in this context is different from the order of terms in polynomials. Autonomous system A dynamical equation whose rules don’t explicitly include time t or any other external variables. Non-autonomous system A dynamical equation whose rules do include time t or other external variables explicitly. Exercise 4.3 Decide whether each of the following examples is (1) linear or nonlinear, (2) first-order or higher-order, and (3) autonomous or non-autonomous. 1. xt = axt−1 + b 2. xt = axt−1 + bxt−2 + cxt−3 3. xt = axt−1 (1 − xt−1 ) √ 4. xt = axt−1 + bxt − 22 + c xt−1 xt−3 5. xt = axt−1 xt−2 + bxt−3 + sin t 6. xt = axt−1 + byt−1 , yt = cxt−1 + dyt−1 Also, there are some useful things that you should know about these classifications: Non-autonomous, higher-order difference equations can always be converted into autonomous, first-order forms, by introducing additional state variables. For example, the second-order difference equation xt = xt−1 + xt−2 (4.5) 38 CHAPTER 4. DISCRETE-TIME MODELS I: MODELING (which is called the Fibonacci sequence) can be converted into a first-order form by introducing a “memory” variable y as follows: (4.6) yt = xt−1 Using this, xt−2 can be rewritten as yt−1 . Therefore the equation can be rewritten as follows: xt = xt−1 + yt−1 (4.7) yt = xt−1 (4.8) This is now first-order. This conversion technique works for third-order or any higherorder equations as well, as long as the historical dependency is finite. Similarly, a nonautonomous equation (4.9) xt = xt−1 + t can be converted into an autonomous form by introducing a “clock” variable z as follows: zt = zt−1 + 1, z0 = 1 (4.10) This definition guarantees zt−1 = t. Using this, the equation can be rewritten as xt = xt−1 + zt−1 , (4.11) which is now autonomous. These mathematical tricks might look like some kind of cheating, but they really aren’t. The take-home message on this is that autonomous first-order equations can cover all the dynamics of any non-autonomous, higher-order equations. This gives us confidence that we can safely focus on autonomous first-order equations without missing anything fundamental. This is probably why autonomous first-order difference equations are called by a particular name: iterative maps. Exercise 4.4 Convert the following difference equations into an autonomous, first-order form. 1. xt = xt−1 (1 − xt−1 ) sin t 2. xt = xt−1 + xt−2 − xt−3 Another important thing about dynamical equations is the following distinction between linear and nonlinear systems: 4.3. SIMULATING DISCRETE-TIME MODELS WITH ONE VARIABLE 39 Linear equations are always analytically solvable, while nonlinear equations don’t have analytical solutions in general. Here, an analytical solution means a solution written in the form of xt = f (t) without using state variables on the right hand side. This kind of solution is also called a closedform solution because the right hand side is “closed,” i.e., it only needs t and doesn’t need x. Obtaining a closed-form solution is helpful because it gives you a way to calculate (i.e., predict) the system’s state directly from t at any point in time in the future, without actually simulating the whole history of its behavior. Unfortunately this is not possible for nonlinear systems in most cases. 4.3 Simulating Discrete-Time Models with One Variable Now is the time to do our very first exercise of computer simulation of discrete-time models in Python. Let’s begin with this very simple linear difference equation model of a scalar variable x: xt = axt−1 (4.12) Here, a is a model parameter that specifies the ratio between the current state and the next state. Our objective is to find out what kind of behavior this model will show through computer simulation. When you want to conduct a computer simulation of any sort, there are at least three essential things you will need to program, as follows: Three essential components of computer simulation Initialize. You will need to set up the initial values for all the state variables of the system. Observe. You will need to define how you are going to monitor the state of the system. This could be done by just printing out some variables, collecting measurements in a list structure, or visualizing the state of the system. Update. You will need to define how you are going to update the values of those state variables in every time step. This part will be defined as a function, and it will be executed repeatedly. 40 CHAPTER 4. DISCRETE-TIME MODELS I: MODELING We will keep using this three-part architecture of simulation codes throughout this textbook.... Purchase answer to see full attachment Tags: public opinion Political Ideologies Complex Systems Democrat ideologies dynamical equations User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.