Small Worlds
Princeton University Press (Verlag)
978-0-691-11704-1 (ISBN)
Everyone knows the small-world phenomenon: soon after meeting a stranger, we are surprised to discover that we have a mutual friend, or we are connected through a short chain of acquaintances. In his book, Duncan Watts uses this intriguing phenomenon--colloquially called "six degrees of separation"--as a prelude to a more general exploration: under what conditions can a small world arise in any kind of network? The networks of this story are everywhere: the brain is a network of neurons; organisations are people networks; the global economy is a network of national economies, which are networks of markets, which are in turn networks of interacting producers and consumers. Food webs, ecosystems, and the Internet can all be represented as networks, as can strategies for solving a problem, topics in a conversation, and even words in a language. Many of these networks, the author claims, will turn out to be small worlds. How do such networks matter? Simply put, local actions can have global consequences, and the relationship between local and global dynamics depends critically on the network's structure.
Watts illustrates the subtleties of this relationship using a variety of simple models---the spread of infectious disease through a structured population; the evolution of cooperation in game theory; the computational capacity of cellular automata; and the sychronisation of coupled phase-oscillators. Watts's novel approach is relevant to many problems that deal with network connectivity and complex systems' behaviour in general: How do diseases (or rumours) spread through social networks? How does cooperation evolve in large groups? How do cascading failures propagate through large power grids, or financial systems? What is the most efficient architecture for an organisation, or for a communications network? This fascinating exploration will be fruitful in a remarkable variety of fields, including physics and mathematics, as well as sociology, economics, and biology.
Duncan J. Watts, is Associate Professor of Sociology at Columbia University and an external faculty member of the Santa Fe Institute. He holds a Ph.D. in theoretical and applied mechanics from Cornell University and is the author of "Six Degrees: The Science of A Connected Age". He lives in New York City.
PREFACE xiii 1 Kevin Bacon, the Small World, and Why It All Matters 3 PART I STRUCTURE 9 2 An Overview of the Small-World Phenomenon 11 2.1 Social Networks and the Small World 11 2.1.1 A Brief History of the Small World 12 2.1.2 Difficulties with the Real World 20 2.1.3 Reframing the Question to Consider All Worlds 24 2.2 Background on the Theory of Graphs 25 2.2.1 Basic Definitions 25 2.2.2 Length and Length Scaling 27 2.2.3 Neighbourhoods and Distribution Sequences 31 2.2.4 Clustering 32 2.2.5 "Lattice Graphs" and Random Graphs 33 2.2.6 Dimension and Embedding of Graphs 39 3 Big Worlds and Small Worlds: Models of Graphs 41 3.1 Relational Graphs 42 3.1.1 a-Graphs 42 3.1.2 A Stripped-Down Model: B-Graphs 66 3.1.3 Shortcuts and Contractions: Model Invariance 70 3.1.4 Lies, Damned Lies, and (More) Statistics 87 3.2 Spatial Graphs 91 3.2.1 Uniform Spatial Graphs 93 3.2.2 Gaussian Spatial Graphs 98 3.3 Main Points in Review 100 4 Explanations and Ruminations 101 4.1 Going to Extremes 101 4.1.1 The Connected-Caveman World 102 4.1.2 Moore Graphs as Approximate Random Graphs 109 4.2 Transitions in Relational Graphs 114 4.2.1 Local and Global Length Scales 114 4.2.2 Length and Length Scaling 116 4.2.3 Clustering Coefficient 117 4.2.4 Contractions 118 4.2.5 Results and Comparisons with B-Model 120 4.3 Transitions in Spatial Graphs 127 4.3.1 Spatial Length versus Graph Length 127 4.3.2 Length and Length Scaling 128 4.3.3 Clustering 130 4.3.4 Results and Comparisons 132 4.4 Variations on Spatial and Relational Graphs 133 4.5 Main Points in Review 136 5 "It's a Small World after All": Three Real Graphs 138 5.1 Making Bacon 140 5.1.1 Examining the Graph 141 5.1.2 Comparisons 143 5.2 The Power of Networks 147 5.2.1 Examining the System 147 5.2.2 Comparisons 150 5.3 A Worm's Eye View 153 5.3.1 Examining the System 154 5.3.2 Comparisons 156 5.4 Other Systems 159 5.5 Main Points in Review 161 PART II DYNAMICS 163 6 The Spread of Infectious Disease in Structured Populations 165 6.1 A Brief Review of Disease Spreading 166 6.2 Analysis and Results 168 6.2.1 Introduction of the Problem 168 6.2.2 Permanent-Removal Dynamics 169 6.2.3 Temporary-Removal Dynamics 176 6.3 Main Points in Review 180 7 Global Computation in Cellular Automata 181 7.1 Background 181 7.1.1 Global Computation 184 7.2 Cellular Automata on Graphs 187 7.2.1 Density Classification 187 7.2.2 Synchronisation 195 7.3 Main Points in Review 198 8 Cooperation in a Small World: Games on Graphs 199 8.1 Background 199 8.1.1 The Prisoner's Dilemma 200 8.1.2 Spatial Prisoner's Dilemma 204 8.1.3 N-Player Prisoner's Dilemma 206 8.1.4 Evolution of Strategies 207 8.2 Emergence of Cooperation in a Homogeneous Population 208 8.2.1 Generalised Tit-for-Tat 209 8.2.2 Win-Stay, Lose-Shift 214 8.3 Evolution of Cooperation in a Heterogeneous Population 219 8.4 Main Points in Review 221 9 Global Synchrony in Populations of Coupled Phase Oscillators 223 9.1 Background 223 9.2 Kuramoto Oscillators on Graphs 228 9.3 Main Points in Review 238 10 Conclusions 240 NOTES 243 BIBLIOGRAPHY 249 INDEX 257
| Erscheint lt. Verlag | 14.12.2003 |
|---|---|
| Reihe/Serie | Princeton Studies in Complexity |
| Zusatzinfo | 144 line illus. 7 tables. |
| Verlagsort | New Jersey |
| Sprache | englisch |
| Maße | 152 x 235 mm |
| Gewicht | 397 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Angewandte Mathematik |
| Mathematik / Informatik ► Mathematik ► Graphentheorie | |
| ISBN-10 | 0-691-11704-7 / 0691117047 |
| ISBN-13 | 978-0-691-11704-1 / 9780691117041 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
