On the Solvability of the Six Degrees of Kevin Bacon Game: A Faster Graph Diameter and Radius Computation Method

摘要

In this paper, we will propose a new algorithm that computes the radius and the diameter of a graph G = (V, E), by finding bounds through heuristics and improving them until exact values can be guaranteed. Although the worst-case running time is (O)(|V| · |E|), we will experimentally show that, in the case of real-world networks, it performs much better, finding the correct radius and diameter value after 10-100 BFSes instead of |V| BFSes (independent of the value of |V|), and thus having running time (O)(|E|). Apart from efficiency, compared to other similar methods, the one proposed in this paper has three other advantages. It is more robust (even in the worst cases, the number of BFSes performed is not very high), it is able to simultaneously compute radius and diameter (halving the total running time whenever both values are needed), and it works both on directed and undirected graphs with very few modifications. As an application example, we use our new algorithm in order to determine the solvability over time of the "six degrees of Kevin Bacon" game.