| According to folklore, everyone is connected to everyone else through a short chain of acquaintances. Sociologists call this the Small World Phenomenon. The phenomenon, if true, is surprising because the social network is large (billions of people), sparsely connected (each person has, at most, thousands of friends), and highly clustered (one's friends tend also to be friends of each other). We explore this phenomenon using models of graphs whose structural characteristics can be tuned, via a single parameter, anywhere between a one-dimensional lattice and a random graph. These models divide naturally into two classes: relational graphs, in which the probability that two vertices will be connected depends only upon pre-existing connections, and spatial graphs, in which the corresponding probability depends upon the Euclidean distance between the vertices. We introduce two graph statistics, which quantify the characteristic path length and the clustering coefficient, and compute these numerically as functions of the respective model parameters. Using a heuristic construction, we then generate analytical fits to the numerical data and explain the observed length-scaling properties of relational and spatial graphs. We determine that the Small World Phenomenon arises from the presence of a small fraction of edges whose range is comparable to the characteristic path length of the entire graph. Such edges occur readily in relational graphs but are not admitted by spatial graphs if the defining probability distribution has a finite cutoff. We then test this analytical framework against the computed statistics of three real networks: the collaboration graph of actors in feature films; the electrical power grid of the western United States, and the neural network of the worm C. elegans. Finally, we extend the approach to four kinds of distributed dynamical systems coupled via an underlying graph: disease spreading, cellular automata, multi-player prisoner's dilemma, and coupled oscillators. The interaction of structure and dynamics is subtle, but some dynamical properties are strongly correlated with the corresponding structural statistics. Our main result is that the characteristic length of networks can be altered dramatically by a tiny amount of "random rewiring" and that this can have an equally dramatic impact upon the dynamics of a correspondingly-coupled dynamical system. |
