Think Complexity - Green Tea Press

1 Think ComplexityVersion ComplexityVersion B. DowneyGreen Tea PressNeedham, MassachusettsCopyright 2012 Allen B. history:Fall 2008:First 2011:Second Tea Press9 Washburn AveNeedham MA 02492 Permission is granted to copy, distribute, transmit and adapt this work under a Creative Com-mons Attribution-NonCommercial-ShareAlike Unported License: nc- you are interested in distributing a commercial version of this work, please contact Allen original form of this book is LATEX source code. Compiling this LATEX source has the effect ofgenerating a device-independent representation of the book, which can be converted to other formatsand LATEX source for this book is available book was typeset using LATEX. The illustrations were drawn in cover photo is courtesy ofblmurch, and is available under a free license Why I wrote this bookThis book is inspired by boredom and fascination: boredom with the usual presentation ofdata structures and algorithms, and fascination with complex systems.

2 The problem withdata structures is that they are often taught without a motivating context; the problem withcomplexity science is that it is usually not taught at 2005 I developed a new class at Olin College where students read about topics in com-plexity, implement experiments in Python, and learn about algorithms and data wrote the first draft of this book when I taught the class again in the third offering, in 2011, I prepared the book for publication and invited the studentsto submit their work, in the form of case studies, for inclusion in the book. I recruited 9professors at Olin to serve as a program committee and choose the reports that were readyfor publication. The case studies that met the standard are included in this book. For thenext edition, we invite additional submissions from readers (see Appendix A). Suggestions for teachersThis book is intended as a scaffold for an intermediate-level college class in Python pro-gramming and algorithms.

3 My class uses the following structure:ReadingComplexity science is a collection of diverse topics. There are many intercon-nections, but it takes time to see them. To help students see the big picture, I givethem readings from popular presentations of work in the field. My reading list, andsuggestions on how to use it, are in Appendix book presents a series of exercises; many of them ask students to reimple-ment seminal experiments and extend them. One of the attractions of Complexity isthat the research frontier is accessible with moderate programming skills and under-graduate topics in this book raise questions in the philosophy of science; these top-ics lend themselves to further reading and classroom 0. PrefaceCase studiesIn my class, we spend almost half the semester on case studies. Studentsparticipate in an idea generation process, form teams, and work for 6-7 weeks on aseries of experiments, then present them in the form of a publishable 4-6 page outline of the course and my notes are available Suggestions for autodidactsIn 2009-10 I was a Visiting Scientist at Google, working in their Cambridge office.

4 One ofthe things that impressed me about the software engineers I worked with was their broadintellectual curiosity and drive to expand their knowledge and hope this book helps people like them explore a set of topics and ideas they might notencounter otherwise, practice programming skills in Python, and learn more about datastructures and algorithms (or review material that might have been less engaging the firsttime around).Some features of this book intended for autodidacts are:Technical depthThere are many books about complex systems, but most are written fora popular audience. They usually skip the technical details, which is frustrating forpeople who can handle it. This book presents the mathematics and other technicalcontent you need to really understand this readingThroughout the book, I include pointers to further reading, includingoriginal papers (most of which are available electronically) and related articles fromWikipedia1and other and (some) solutionsFor many of the exercises, I provide code to get youstarted, and solutions if you get stuck or want to compare your code to to contributeIf you explore a topic not covered in this book, reimplementan interesting experiment, or perform one of your own, I invite you to submit a casestudy for possible inclusion in the next edition of the book.

5 See Appendix A book will continue to be a work in progress. You can read about ongoing develop-ments B. DowneyProfessor of Computer ScienceOlin College of EngineeringNeedham, MA1 Some professors have an allergic reaction to Wikipedia, on the grounds that students depend too heavily onan unreliable source. Since many of my references are Wikipedia articles, I want to explain my thinking. First, thearticles on Complexity science and related topics tend to be very good; second, they are written at a level that isaccessible after you have read this book (but sometimes not before); and finally, they are freely available to readersall over the world. If there is a danger in sending readers to these references, it is not that they are unreliable, butthat the readers won t come back! ( ). Suggestions for autodidactsviiContributor ListIf you have a suggestion or correction, please send email If Imake a change based on your feedback, I will add you to the contributor list (unless youask to be omitted).

6 If you include at least part of the sentence the error appears in, that makes it easy for me tosearch. Page and section numbers are fine, too, but not quite as easy to work with. Thanks! Richard Hollands pointed out several typos. John Harley, Jeff Stanton, Colden Rouleau and Keerthik Omanakuttan are ComputationalModeling students who pointed out typos. Muhammad Najmi bin Ahmad Zabidi caught some typos. Phillip Loh, Corey Dolphin, Noam Rubin and Julian Ceipek found typos and made helpfulsuggestions. Jose Oscar Mur-Miranda found several typos. I am grateful to the program committee that read and selected the case studies included inthis book: Sarah Spence Adams, John Geddes, Stephen Holt, Vincent Manno, Robert Martello,Amon Millner, Jos Oscar Mur-Miranda, Mark Somerville, and Ursula Wolz. Sebastian Sch ner sent two pages of typos! Jonathan Harford found a code error. Philipp Marek sent a number of corrections. Alex Hantman found a missing 0.

7 I wrote this book .. for teachers .. for autodidacts ..vi1 Complexity is this book about? .. new kind of science .. shift? .. axes of scientific models .. new kind of model .. new kind of engineering .. new kind of thinking ..72 s a graph? .. graphs .. graphs .. graphs .. Erd os: peripatetic mathematician, speed freak ..17xContents3 Analysis of of growth .. of basic Python operations .. of search algorithms .. lists .. comprehensions ..314 Small world of graph algorithms .. implementation .. Milgram .. and Strogatz .. kind of explanation isthat? ..385 Scale-free s Law .. distributions .. distributions .. distributions .. si and Albert .. , Pareto and power laws .. models ..496 Cellular Wolfram .. CAs .. CAs .. is this a model of? ..647 Game of Life .. patterns .. s conjecture ..738 CAs ..789 Self-organized piles.

8 Density .. Fourier Transform .. noise .. and Holism .. , causation and prediction ..8810 Agent-based Schelling .. models .. jams .. s Dilemma .. will ..9811 Case study: Original Sugarscape .. Occupy movement .. New Take on Sugarscape .. and the Leave Behind .. Gini coefficient .. With Taxation .. 10512 Case study: Ant .. Overview .. design .. matrices .. 11113 Case study: Directed graphs and Graphs .. knots .. in Wikipedia .. 11614 Case study: The Volunteer s prairie dog s dilemma .. Norms Game .. the chances .. 121 ContentsxiiiA Call for submissions123B Reading list125xivContentsChapter 1 Complexity What is this book about?This book is about data structures and algorithms, intermediate programming in Python,computational modeling and the philosophy of science:Data structures and algorithms:A data structure is a collection of data elements orga-nized in a way that supports particular operations.

9 For example, a Python dictionaryorganizes key-value pairs in a way that provides fast mapping from keys to values,but mapping from values to keys is algorithm is a mechanical process for performing a computation. Designing effi-cient programs often involves the co-evolution of data structures and the algorithmsthat use them. For example, in the first few chapters I present graphs, data structuresthat implement graphs, and graph algorithms based on those data programming:This book picks up whereThink Pythonleaves off. I assume thatyou have read that book or have equivalent knowledge of Python. I try to emphasizefundamental ideas that apply to programming in many languages, but along the wayyou will learn some useful features that are specific to modeling:A model is a simplified description of a system used for simu-lation or analysis. Computational models are designed to take advantage of cheap,fast of science:The experiments and results in this book raise questions relevantto the philosophy of science, including the nature of scientific laws, theory choice,realism and instrumentalism, holism and reductionism, and book is also aboutcomplexity science, which is an interdisciplinary field at the in-tersection of mathematics, computer science and natural science that focuses on discretemodels of physical systems.

10 In particular, it focuses oncomplex systems, which are sys-tems with many interacting 1. Complexity ScienceComplex systems include networks and graphs, cellular automata, agent-based modelsand swarms, fractals and self-organizing systems, chaotic systems and cybernetic terms might not mean much to you at this point. We will get to them soon, but youcan get a preview A new kind of scienceIn 2002 Stephen Wolfram publishedA New Kind of Sciencewhere he presents his and oth-ers work on cellular automata and describes a scientific approach to the study of compu-tational systems. We ll get back to Wolfram in Chapter 6, but I want to borrow his title forsomething a little Think Complexity is a new kind of science not because it applies the tools of scienceto a new subject, but because it uses different tools, allows different kinds of work, andultimately changes what we mean by science. To demonstrate the difference, I ll start with an example of classical science: suppose some-one asked you why planetary orbits are elliptical.