Small World Networks
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.