You may have heard the phrase "six degrees of separation"; referring to the theory that any two people in the world are on average only six mutual acquaintances apart. You may have heard something like: "Oh I know him; my friend's mum's sisters' husband is his best mate". What you may not have heard of is the niche subclass of this theory, whereby the target acquaintance is fixed to a specific individual: Hollywood actor Kevin Bacon.
If you watch much TV you will be pretty familiar with Kevin Bacon, along with the latest deals EE has to offer. At times it can feel as though he is everywhere. It isn't just us who's lives he seems to have pervaded; it turns out he is also deeply ingrained within the Hollywood social network. Observe the network diagram above, the bacon represents Kevin, the other nodes represent fellow actors, and the connections between these individuals represents the fact that they were in a film together. Now, we can ask what is the average number of connections between Bacon and any other actor?
This problem was originally considered in 1996 by some American college students, with their work resulting in the creation of a website where you can calculate the minimum number of connections, or as they term it the Bacon Number, for any actor (providing a connection exists). Check out the website here. In their analysis they found that of those actors who have a some string of connections to Bacon, the average Bacon Number is 3.153. So it turns out it is really "three degrees of Kevin Bacon".
For each starting person there could be one of two outcomes; the packet made it to the target or it was discarded at some intermediate step. In one particular study with J. Travers [2] it was found that of the instances in which the packet made it to the target the average number of intermediate acquaintances was 5.2. The distribution of the length of these chains can be seen above, taken from [2]. One can clearly see here that the modal value is 6. Other experiments also found mean averages closer to 6. These results are what led to the turn of phrase we hear today.
It must be considered, however, that in Travers and Milgram's study only 64 out of 296 packets made it to the target, which makes inference more complicated, since we don't know what happened to the other 235 packets. It could be that the starting person did actually have a chain of acquaintances, albeit a large one, but the process was cut short since the relation to the target person was so large that some intermediate person felt they knew no potential acquaintances. If this data had been collected it could have dragged up the average.
This is an example of a statistical analysis of a network. I intend to post about this topic again soon, looking into some of the specific statistical models which are used to make inference on networks. I hope this will provide a nice contrast to my previous posts on network flows, where problems were tackled from a optimisation perspective.
You may have heard the phrase "six degrees of separation"; referring to the theory that any two people in the world are on average only six mutual acquaintances apart. You may have heard something like: "Oh I know him; my friend's mum's sisters' husband is his best mate". What you may not have heard of is the niche subclass of this theory, whereby the target acquaintance is fixed to a specific individual: Hollywood actor Kevin Bacon.
If you watch much TV you will be pretty familiar with Kevin Bacon, along with the latest deals EE has to offer. At times it can feel as though he is everywhere. It isn't just us who's lives he seems to have pervaded; it turns out he is also deeply ingrained within the Hollywood social network. Observe the network diagram above, the bacon represents Kevin, the other nodes represent fellow actors, and the connections between these individuals represents the fact that they were in a film together. Now, we can ask what is the average number of connections between Bacon and any other actor?
This problem was originally considered in 1996 by some American college students, with their work resulting in the creation of a website where you can calculate the minimum number of connections, or as they term it the Bacon Number, for any actor (providing a connection exists). Check out the website here. In their analysis they found that of those actors who have a some string of connections to Bacon, the average Bacon Number is 3.153. So it turns out it is really "three degrees of Kevin Bacon".
Small World Problem
Though this example is a trivial one it is a good illustrative example of the so-called "Small World" problem, first stated by S. Milgram in 1967. This considered the following questions:- Given two randomly chosen people; what is the probability they know each other?
- If they don't know each other, do they share a mutual acquaintance?
- If they don't share a mutual acquaintance how many intermediate acquaintances are there?
To answer these Milgram and others conducted a series of experiments. In each of these experiments they randomly selected some starting persons from a given city, they then randomly selected some target person in another city. The starting persons were sent a packet containing information on the target person, if they knew that person on a first name basis then they were to send the package onto them, otherwise they were to send it to an acquaintance they felt were likely to know them. They were also instructed to inform the experimenter of whom the packet had been sent to, so a chain of acquaintances could be constructed, as in the bacon network above.
It must be considered, however, that in Travers and Milgram's study only 64 out of 296 packets made it to the target, which makes inference more complicated, since we don't know what happened to the other 235 packets. It could be that the starting person did actually have a chain of acquaintances, albeit a large one, but the process was cut short since the relation to the target person was so large that some intermediate person felt they knew no potential acquaintances. If this data had been collected it could have dragged up the average.
This is an example of a statistical analysis of a network. I intend to post about this topic again soon, looking into some of the specific statistical models which are used to make inference on networks. I hope this will provide a nice contrast to my previous posts on network flows, where problems were tackled from a optimisation perspective.
Comments
Post a Comment