Small World Networks
Submitted by stan on Tue, 2005-04-05 17:47.
For the moment,
imagine a world in which everyone was friends with only those people
who lived within a 5 mile radius. How would this change the degrees of
separation? It is clear that people living 1000 miles away from each
other will have at least 100 degrees of separation. (Of course, those
on different continents or islands would be completely unreachable.)
This strange example shows the importance of outlying
connections.
Figure 1 shows a graph which is similar to our imaginary world. Each node is connected to its four nearest neighbors. To reach a node on the other side of circle requires many hops.
However,
in the real world we have friends who live very far away and who come
from different cliques. Figure 2 shows a graph where just a few nodes
were given edges at random. These 3 extra edges are enough to cut the
average degrees of separation in half. In the social world, it is these
"long-range" edges that can connect a kebab
owner in Berlin with Marlon Brando.
This graph is highly ordered, and yet any node can be reached with just a few "hops." These are the characteristic properties of small world networks. It turns out that these networks are found everywhere in nature: In friend networks, power grids, predator-prey networks, and even neural networks of the brain. Formal study of these networks began with Watts and Strogatz in their seminal paper "Collective dynamics of 'small-world' networks." (Nature. 1998 Jun 4;393(6684):409-10)
As a member of this network, you want your network of trusted sources to be as large as possible. After all, you never know when you'll encounter something or someone new that you would like to hear about from a trusted source. So you might extend your trust to friends-of-friends or even friends-of-friends-of-friends. But with each new hop, you open yourself to risk. The kebab owner mentioned above is not only connected to Marlon Brando by few hops, but also to con men, theives, and murderers! This is the balancing act that everyone performs. (There are additional constraints too: human memory is limited, and so is our ability to get information from others.)
To see how small-world properties can be used for ensuring the integrity of a trust network, first consider the case of diseases. These networks were immediately influential in the study of how contagions spread. (Zanette, 2001) [Get exact reference] For example, from a small-world perspective it is clear that these long-range hops are important for stopping the spread of a disease. In the case of HIV, this would mean trying to identify and educate people with many partners and especially people with partners from different social circles. During the SARS epidemic in 2001, some airports were closed to prevent the spread of the disease via physical long-range hops.
Now imagine that your trust is like a disease: you want it to spread as far as possible so as to increase your sources of information, but you don't want to "infect" people who would harm you in some way. The strategy of Outfoxed is the same one used in fighting the diseases: find and eliminate the long-range edges. But rather than trying to get rid of all long range edges, try to elminate those edges that lead to untrustworthy sources. And how do you decide who is untrustworthy? You allow all the people who are more trusted to make the cuts.
Overview of Small World Networks
Everyone is familiar with the "small world" phenomena, in which every person on earth is connected to every other by at most 6 degrees of separation.For the moment,
imagine a world in which everyone was friends with only those people
who lived within a 5 mile radius. How would this change the degrees of
separation? It is clear that people living 1000 miles away from each
other will have at least 100 degrees of separation. (Of course, those
on different continents or islands would be completely unreachable.)
This strange example shows the importance of outlying
connections. Figure 1 shows a graph which is similar to our imaginary world. Each node is connected to its four nearest neighbors. To reach a node on the other side of circle requires many hops.
However,
in the real world we have friends who live very far away and who come
from different cliques. Figure 2 shows a graph where just a few nodes
were given edges at random. These 3 extra edges are enough to cut the
average degrees of separation in half. In the social world, it is these
"long-range" edges that can connect a kebab
owner in Berlin with Marlon Brando.
This graph is highly ordered, and yet any node can be reached with just a few "hops." These are the characteristic properties of small world networks. It turns out that these networks are found everywhere in nature: In friend networks, power grids, predator-prey networks, and even neural networks of the brain. Formal study of these networks began with Watts and Strogatz in their seminal paper "Collective dynamics of 'small-world' networks." (Nature. 1998 Jun 4;393(6684):409-10)
Trust in a Small World
If you were able to graph people's trust, what you would see would also be a small world network. (Goldbeck 2003, viualization) (Of course, there are many types of trust, but we'll start with the colloquial version.) It would look a lot like a network of social connections, but would also include some connections to non-persons. For example, many people trust the recommendations of Consumer Reports. And you would also expect to see that trust is often communative. If A trusts B and B trusts C, there's a good chance that A also trusts C. In many cases, A may have never encountered C, but trusts C based only on B's reccomendation.As a member of this network, you want your network of trusted sources to be as large as possible. After all, you never know when you'll encounter something or someone new that you would like to hear about from a trusted source. So you might extend your trust to friends-of-friends or even friends-of-friends-of-friends. But with each new hop, you open yourself to risk. The kebab owner mentioned above is not only connected to Marlon Brando by few hops, but also to con men, theives, and murderers! This is the balancing act that everyone performs. (There are additional constraints too: human memory is limited, and so is our ability to get information from others.)
To see how small-world properties can be used for ensuring the integrity of a trust network, first consider the case of diseases. These networks were immediately influential in the study of how contagions spread. (Zanette, 2001) [Get exact reference] For example, from a small-world perspective it is clear that these long-range hops are important for stopping the spread of a disease. In the case of HIV, this would mean trying to identify and educate people with many partners and especially people with partners from different social circles. During the SARS epidemic in 2001, some airports were closed to prevent the spread of the disease via physical long-range hops.
Now imagine that your trust is like a disease: you want it to spread as far as possible so as to increase your sources of information, but you don't want to "infect" people who would harm you in some way. The strategy of Outfoxed is the same one used in fighting the diseases: find and eliminate the long-range edges. But rather than trying to get rid of all long range edges, try to elminate those edges that lead to untrustworthy sources. And how do you decide who is untrustworthy? You allow all the people who are more trusted to make the cuts.