Small Worlds: The Dynamics of Networks between Order and Randomness
280
Small Worlds: The Dynamics of Networks between Order and Randomness
280eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
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.
Product Details
| ISBN-13: | 9780691188331 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 06/05/2018 |
| Series: | Princeton Studies in Complexity , #36 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 280 |
| File size: | 5 MB |
About the Author
Table of Contents
| 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 |
| 2.2.7 | Alternative Definition of Clustering Coefficient | 40 |
| 3 | Big Worlds and Small Worlds: Models of Graphs | 41 |
| 3.1 | Relational Graphs | 42 |
| 3.1.1 | [alpha]-Graphs | 42 |
| 3.1.2 | A Stripped-Down Model: [beta]-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 [beta]-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 |
What People are Saying About This
Theoretical research on social networks has been hampered by a lack of models which capture the essential properties of large numbers of graphs with only a few key parameters. All the dyads, triads and acyclic mappings which fill the social network literature lead merely to a long enumeration of special cases. The random graph models introduced by Watts provide a rich foundation for future analytical and empirical research. The applications to dynamics in part 2 illustrate the richness of these models and promise even more exciting work to come.
— Larry Blume, Cornell University
If you are a postgraduate looking to make your name or a seasoned researcher looking for new challenges, this book offers something rare: a chance to get in at the ground floor of a whole new area of research whose variety of exciting applications is exceeded only by their abundance.
— Robert A. J. Matthews, Aston University, U.K.
Duncan Watts's and Steve Strogatz's 1998 Nature paper on 'The collective dynamics of small-world networks' reinvigorated interest in the small-world phenomenon. Now, in Small Worlds, Watts follows up on this work with a detailed but accessible account of small-world networks that will appeal to both scientists and nonscientists. With examples ranging from the Kevin Bacon Game to models for the spread of diseases, Watts provides a clear description of how the structure of small-world networks can be characterized and a sense of how the interconnectivity of such networks can lead to intriguing dynamics. Be sure to tell your friends and their friends about this book.
This is a remarkably novel analysis, with implications for a broad range of scientific disciplines, including neurobiology, sociology, ecology, economics, and epidemiology. . . . The results are potentially profoundly important.
— Simon A. Levin, Department of Ecology and Evolutionary Biology, Princeton University
Small Worlds is outstanding. Watts begins with a simple observation: clustered networks, networks characterized by a large fraction of short ties and a small fraction of 'shortcuts' linking clusters with one another, appear in diverse settings and more frequently than might be expected. Watts then demonstrates that the dynamical behavior of these networks is highly sensitive to structure. The book is must reading, although not easy reading, for social scientists interested in networks, decision-making, and organizational design.(In other words, this is a high-investment, high-payoff book.)
Duncan Watts's and Steve Strogatz's 1998 Nature paper on 'The collective dynamics of small-world networks' reinvigorated interest in the small-world phenomenon. Now, in Small Worlds, Watts follows up on this work with a detailed but accessible account of small-world networks that will appeal to both scientists and nonscientists. With examples ranging from the Kevin Bacon Game to models for the spread of diseases, Watts provides a clear description of how the structure of small-world networks can be characterized and a sense of how the interconnectivity of such networks can lead to intriguing dynamics. Be sure to tell your friends and their friends about this book.
— J. J. Collins, Center for BioDynamics and Department of Biomedical Engineering, Boston University
Duncan Watts has created that rarity of rarities: a book with enough fascinating facts and stories to keep the casual reader turning the pages coupled with enough engaging detail to satisfy the most technically sophisticated reader. Thus, whether you are just curious about the world around you or eager to begin your own small-world research, this is the definitive guide to the fascinating and profound world of small-world networks.
— William L. Ditto, Applied Chaos Laboratory, Georgia Institute of Technology
"Duncan Watts has created that rarity of rarities: a book with enough fascinating facts and stories to keep the casual reader turning the pages coupled with enough engaging detail to satisfy the most technically sophisticated reader. Thus, whether you are just curious about the world around you or eager to begin your own small-world research, this is the definitive guide to the fascinating and profound world of small-world networks."—William L. Ditto, Applied Chaos Laboratory, Georgia Institute of Technology"A good book on a fascinating topic—why two widely separated people are often connected by a small number of steps from friend to friend. We do indeed live in a 'small world.' When something happens so often there must be a reason—Duncan Watts is looking for it."—Gilbert Strang, Department of Mathematics, Massachusetts Institute of Technology"Duncan Watts's and Steve Strogatz's 1998 Nature paper on 'The collective dynamics of small-world networks' reinvigorated interest in the small-world phenomenon. Now, in Small Worlds, Watts follows up on this work with a detailed but accessible account of small-world networks that will appeal to both scientists and nonscientists. With examples ranging from the Kevin Bacon Game to models for the spread of diseases, Watts provides a clear description of how the structure of small-world networks can be characterized and a sense of how the interconnectivity of such networks can lead to intriguing dynamics. Be sure to tell your friends and their friends about this book."—J. J. Collins, Center for BioDynamics and Department of Biomedical Engineering, Boston University"Enchanting! A voyage of exploration with fascinating byroads that yet brings the reader to powerful and useable conclusions. This work is worthy of Stanley Milgram exactly because Watts goes well beyond the original visualization while retaining its transparency."—Harrison White, Department of Sociology, Columbia University"If you are a postgraduate looking to make your name or a seasoned researcher looking for new challenges, this book offers something rare: a chance to get in at the ground floor of a whole new area of research whose variety of exciting applications is exceeded only by their abundance."—Robert A. J. Matthews, Aston University, U.K."Small Worlds is outstanding. Watts begins with a simple observation: clustered networks, networks characterized by a large fraction of short ties and a small fraction of 'shortcuts' linking clusters with one another, appear in diverse settings and more frequently than might be expected. Watts then demonstrates that the dynamical behavior of these networks is highly sensitive to structure. The book is must reading, although not easy reading, for social scientists interested in networks, decision-making, and organizational design.(In other words, this is a high-investment, high-payoff book.)"—Marshall W. Meyer, The Wharton School, University of Pennsylvania"This is a remarkably novel analysis, with implications for a broad range of scientific disciplines, including neurobiology, sociology, ecology, economics, and epidemiology. . . . The results are potentially profoundly important."—Simon A. Levin, Department of Ecology and Evolutionary Biology, Princeton University"Theoretical research on social networks has been hampered by a lack of models which capture the essential properties of large numbers of graphs with only a few key parameters. All the dyads, triads and acyclic mappings which fill the social network literature lead merely to a long enumeration of special cases. The random graph models introduced by Watts provide a rich foundation for future analytical and empirical research. The applications to dynamics in part 2 illustrate the richness of these models and promise even more exciting work to come."—Larry Blume, Cornell University
Enchanting! A voyage of exploration with fascinating byroads that yet brings the reader to powerful and useable conclusions. This work is worthy of Stanley Milgram exactly because Watts goes well beyond the original visualization while retaining its transparency.
— Harrison White, Department of Sociology, Columbia University
If you are a postgraduate looking to make your name or a seasoned researcher looking for new challenges, this book offers something rare: a chance to get in at the ground floor of a whole new area of research whose variety of exciting applications is exceeded only by their abundance.
— Robert A. J. Matthews, Aston University, U.K.
A good book on a fascinating topic—why two widely separated people are often connected by a small number of steps from friend to friend. We do indeed live in a 'small world.' When something happens so often there must be a reason—Duncan Watts is looking for it.
— Gilbert Strang, Department of Mathematics, Massachusetts Institute of Technology
Small Worlds is outstanding. Watts begins with a simple observation: clustered networks, networks characterized by a large fraction of short ties and a small fraction of 'shortcuts' linking clusters with one another, appear in diverse settings and more frequently than might be expected. Watts then demonstrates that the dynamical behavior of these networks is highly sensitive to structure. The book is must reading, although not easy reading, for social scientists interested in networks, decision-making, and organizational design.(In other words, this is a high-investment, high-payoff book.)
— Marshall W. Meyer, The Wharton School, University of Pennsylvania