Been meaning to post for a bit. This isn't really it. However, it amused me.
This comes from a fairly low level paper of interconnected networks. If you can worry through the verbiage you'll find there's actually always an answer to the Kevin Bacon game. It also appears that other papers have been written about this!
The ultimate small-world graph is the so-called Kevin Bacon graph (KBG), in which the nodes represent actors who have appeared (any time, anywhere) in one or more feature films in which pairs of vertices are connected by an edge whenever the corresponding actors have appeared together in at least one feature film. Watts lists a number of factors that make the KBG worthy of serious study [3]. For one thing, the data are reliable. The entire history of motion pictures has resulted in the creation of only about 150,000 feature films, with a combined cast of about 300,000 actors, all of which are listed in a single searchable database (at www.us.imdb.com). Moreover, about 90% of the actors listed are part of a single connected component KBG of the graph that includes about 225,000 actors in about 110,000 films. Strictly speaking, Watts and Strogatz’s analysis of the KBG applies only to KBG, since only connected graphs are of interest in the present line of inquiry.
KBG is sufficiently large (n = 225,226) and sparse (k ≈ 61) that L could conceivably vary over several orders of magnitude, while C might lie almost anywhere in the unit interval. Yet the graph is not so large that it cannot be stored and manipulated by a (suitably powerful) computer. Specifically, if n were even a single order of magnitude larger, it would be difficult to find any computer that could hold the connected component in memory at one time, as must be done to compute statistics like L and C with reasonable dispatch. The KBG is so named because (a) every actor who has ever appeared in an American-made film is connected to Bacon by a path of length four or less, and (b) every actor in the entire graph - whatever his or her nationality - is connected to him by a path of length at most eight. It is almost anticlimactic to learn that the decidedly more accomplished Rod Steiger has an even shorter average path length than Bacon to other members of KBG.
From: http://www.siam.org/siamnews/11-01/networks.pdf
This comes from a fairly low level paper of interconnected networks. If you can worry through the verbiage you'll find there's actually always an answer to the Kevin Bacon game. It also appears that other papers have been written about this!
The ultimate small-world graph is the so-called Kevin Bacon graph (KBG), in which the nodes represent actors who have appeared (any time, anywhere) in one or more feature films in which pairs of vertices are connected by an edge whenever the corresponding actors have appeared together in at least one feature film. Watts lists a number of factors that make the KBG worthy of serious study [3]. For one thing, the data are reliable. The entire history of motion pictures has resulted in the creation of only about 150,000 feature films, with a combined cast of about 300,000 actors, all of which are listed in a single searchable database (at www.us.imdb.com). Moreover, about 90% of the actors listed are part of a single connected component KBG of the graph that includes about 225,000 actors in about 110,000 films. Strictly speaking, Watts and Strogatz’s analysis of the KBG applies only to KBG, since only connected graphs are of interest in the present line of inquiry.
KBG is sufficiently large (n = 225,226) and sparse (k ≈ 61) that L could conceivably vary over several orders of magnitude, while C might lie almost anywhere in the unit interval. Yet the graph is not so large that it cannot be stored and manipulated by a (suitably powerful) computer. Specifically, if n were even a single order of magnitude larger, it would be difficult to find any computer that could hold the connected component in memory at one time, as must be done to compute statistics like L and C with reasonable dispatch. The KBG is so named because (a) every actor who has ever appeared in an American-made film is connected to Bacon by a path of length four or less, and (b) every actor in the entire graph - whatever his or her nationality - is connected to him by a path of length at most eight. It is almost anticlimactic to learn that the decidedly more accomplished Rod Steiger has an even shorter average path length than Bacon to other members of KBG.
From: http://www.siam.org/siamnews/11-01/networks.pdf
Tags: