神
神童
if someone would like to translate the following into Chinese,I will be very glad to discuss the concerned plots with him or her.
It’s a small world
James J. Colllins and Carson C. Chow
The concept of six degrees of separation has been formalized in so-called ‘small-world networks’. The principles involved could be of use in settings as diverse as improving networks of cellular phones and understanding the spread of infections.
A few years ago, on American campuses, it was popular to play six degrees of Kevin Bacon. In this game, participants attempt to link the actor Kevin Bacon to any other actor through as few common film and co-stars as possible. Links are formed directly between Bacon and another actor if they appeared in the same film or indirectly through a chain of co-stars in different films (Fig.1)
In the world of mathematics, a similar amusement involves assessing one’s Erdos number, which measurers the number of links needed to connect one to the prolific mathematician Paul Erdos through jointly authored papers. For example, individuals have an Erdos number of 1 if they co-authored a paper with Erdos. If one of their co-authors wrote a paper with Erdos, then they have an Erdos number of 2, and so forth. It has been pointed out that Dan Kleitman has a combined Erdos/Bacon number of 3 because he wrote a paper with Erdos and appeared in Good Will Hunting with Minnie Driver, who appeared with Bacon in Sleepers.
These games are related to the popular concept of six degrees of separation, which is based on the notion that everyone in the world is connected to everyone else through a chain of at most six mutual acquaintances. If two people have one mutual acquaintance, then they have one degree of separation. The estimate of six degrees of separation, which is related to the small-world phenomenon, arises from pioneering empirical work by Milgram and can be understood heuristically from a somewhat unrealistic assumption of random connectivity. That is, if each person knows about one hundred individuals, and given that there are about a billion people on the Earth, then seven connection or six degrees of separation are enough to link everyone together.
On page 440 of this issue, Watts and Strogatz formalize this idea in what they call small-world networks. They demonstrate through numerical simulations that a network need not be very random to get this small-world effect. They consider a connected network with nodes and links. In the friendship analogy, each node represents a person and each link represents a single connection to an acquaintance. They then define two measures. The first is a characteristic path length. This is the smallest number of links it takes to connect one node to another, averaged over all pairs of nodes in the network. The second measure is the clustering coefficient. This measures the amount of cliquishness of the network, that is, the fraction of neighboring nodes that are also connected to one another. For example, in an all-to-all connected network, the clustering coefficient is one.
An example of a large-world network is one that is regularly and locally connected like a crystalline lattice. Such a network is highly clustered and the characteristic path length is large, scaling with the typical linear dimension of the network. On the other hand, a completely random network is poorly clustered and the characteristic path length is short, scaling logarithmically with the size of the network.
What Watts and Strogatz do is to shift gradually from a regular network to a random network by increasing the probability of making random connections from 0 to 1(see Fig. 1, page 441). They then measure the characteristic path length and the amount of clustering of the network as a function of the amount of randomness. They find that path length and clustering depend differently on the amount of randomness in the network. The characteristic path length drops quickly, whereas the amount of clustering drops rather slowly. This leads to a small-word network in which the amount of clustering is high and the characteristic path length is short. So a small world can exist even when the cliquishness is imperceptibly different from that of large world.
The explanation for this effect is that it only takes a few short cuts between cliques to turn a large world into a small world. In the friendship analogy, it only takes a small number of well-connected people to make a world small. The interesting and surprising thing is that it is impossible to determine whether or not you live in a small world or a large world from local information alone. The average person (node) is not directly associated with the key people (the clique-linkers).
Small-world connectivity has consequences that could be good or bad, depending on the system and circumstances. In a simple model of disease spreading, for example, Watts and Strogatz show that the time for global infection behaves much like the characteristic path length. So it takes only a few short cuts to increase the spreading of disease significantly. Clearly, in this case, small-world coupling is problematic.
The findings of Watts and Strogatz could be put to good use, however, particularly in the case of existing networks. For instance, it may be possible to improve the performance of cellular-phone networks by deliberately introducing a few random connections between cells (nods). Such a change could improve traffic flow around the network, without requiring the creation of an entirely new set of relay stations. Similar dynamics could also be exploited to improve the flow of information throughout the Internet. Although we are not in a position to re-design the Internet from scratch, it is possible to introduce a few random links between nodes along the backbone of the Internet. These small-world modifications could substantially reduce the time needed to send a message by electronic mail or find a particular Web site, as well as improve the reliability of the overall network. Strategies for determining and achieving optimal small-world connectivity remain to be developed.
It’s a small world
James J. Colllins and Carson C. Chow
The concept of six degrees of separation has been formalized in so-called ‘small-world networks’. The principles involved could be of use in settings as diverse as improving networks of cellular phones and understanding the spread of infections.
A few years ago, on American campuses, it was popular to play six degrees of Kevin Bacon. In this game, participants attempt to link the actor Kevin Bacon to any other actor through as few common film and co-stars as possible. Links are formed directly between Bacon and another actor if they appeared in the same film or indirectly through a chain of co-stars in different films (Fig.1)
In the world of mathematics, a similar amusement involves assessing one’s Erdos number, which measurers the number of links needed to connect one to the prolific mathematician Paul Erdos through jointly authored papers. For example, individuals have an Erdos number of 1 if they co-authored a paper with Erdos. If one of their co-authors wrote a paper with Erdos, then they have an Erdos number of 2, and so forth. It has been pointed out that Dan Kleitman has a combined Erdos/Bacon number of 3 because he wrote a paper with Erdos and appeared in Good Will Hunting with Minnie Driver, who appeared with Bacon in Sleepers.
These games are related to the popular concept of six degrees of separation, which is based on the notion that everyone in the world is connected to everyone else through a chain of at most six mutual acquaintances. If two people have one mutual acquaintance, then they have one degree of separation. The estimate of six degrees of separation, which is related to the small-world phenomenon, arises from pioneering empirical work by Milgram and can be understood heuristically from a somewhat unrealistic assumption of random connectivity. That is, if each person knows about one hundred individuals, and given that there are about a billion people on the Earth, then seven connection or six degrees of separation are enough to link everyone together.
On page 440 of this issue, Watts and Strogatz formalize this idea in what they call small-world networks. They demonstrate through numerical simulations that a network need not be very random to get this small-world effect. They consider a connected network with nodes and links. In the friendship analogy, each node represents a person and each link represents a single connection to an acquaintance. They then define two measures. The first is a characteristic path length. This is the smallest number of links it takes to connect one node to another, averaged over all pairs of nodes in the network. The second measure is the clustering coefficient. This measures the amount of cliquishness of the network, that is, the fraction of neighboring nodes that are also connected to one another. For example, in an all-to-all connected network, the clustering coefficient is one.
An example of a large-world network is one that is regularly and locally connected like a crystalline lattice. Such a network is highly clustered and the characteristic path length is large, scaling with the typical linear dimension of the network. On the other hand, a completely random network is poorly clustered and the characteristic path length is short, scaling logarithmically with the size of the network.
What Watts and Strogatz do is to shift gradually from a regular network to a random network by increasing the probability of making random connections from 0 to 1(see Fig. 1, page 441). They then measure the characteristic path length and the amount of clustering of the network as a function of the amount of randomness. They find that path length and clustering depend differently on the amount of randomness in the network. The characteristic path length drops quickly, whereas the amount of clustering drops rather slowly. This leads to a small-word network in which the amount of clustering is high and the characteristic path length is short. So a small world can exist even when the cliquishness is imperceptibly different from that of large world.
The explanation for this effect is that it only takes a few short cuts between cliques to turn a large world into a small world. In the friendship analogy, it only takes a small number of well-connected people to make a world small. The interesting and surprising thing is that it is impossible to determine whether or not you live in a small world or a large world from local information alone. The average person (node) is not directly associated with the key people (the clique-linkers).
Small-world connectivity has consequences that could be good or bad, depending on the system and circumstances. In a simple model of disease spreading, for example, Watts and Strogatz show that the time for global infection behaves much like the characteristic path length. So it takes only a few short cuts to increase the spreading of disease significantly. Clearly, in this case, small-world coupling is problematic.
The findings of Watts and Strogatz could be put to good use, however, particularly in the case of existing networks. For instance, it may be possible to improve the performance of cellular-phone networks by deliberately introducing a few random connections between cells (nods). Such a change could improve traffic flow around the network, without requiring the creation of an entirely new set of relay stations. Similar dynamics could also be exploited to improve the flow of information throughout the Internet. Although we are not in a position to re-design the Internet from scratch, it is possible to introduce a few random links between nodes along the backbone of the Internet. These small-world modifications could substantially reduce the time needed to send a message by electronic mail or find a particular Web site, as well as improve the reliability of the overall network. Strategies for determining and achieving optimal small-world connectivity remain to be developed.