I don't see why the graph has to be unknown. You can download wikipedia and have all of the nodes and edges. The current image is an 18GB xml file, nothing intractable.
Printable View
I don't see why the graph has to be unknown. You can download wikipedia and have all of the nodes and edges. The current image is an 18GB xml file, nothing intractable.
infact... I don't get this o.o
Finding Hitler everywhere is only a little suprising, but Matt Damon o.O Why does he have anything to do with anything?
Make two lists. Put every article in list 1. Now move 'Hitler to list 2 and mark its distance as 0.
Run wikipedias 'what links here on every article in list 2. Mark each result that is in list 1 with a 1 adn move it to list 2. Run WLH on every article in list 2 with a distance of 1. mark all results in list 1 with a 2 and move it to list 2, repeat until there are no more articles in list 1.
Worse case scenario is O^2/2 assuming only 1 article is moved each time or O^(1+1/N)/2 for an average of N links per page.
Six degrees of separation...
but the answer is, obviously, any and all orphaned pages. I win.
It was originally Kevin Bacon. Now in 2009 I wouldn't be surprised if Matt Damon is the centre of the co-star graph.
The Oracle of Bacon
mmmm, bacon, now im hungry
Kevin Bacon's success is obviously based on his name, it just soudns yummy, oh wait that sounded kind of gay...
Yes, this is related to Six Degrees of Kevin Bacon
That is, finding the minimum number of movie hops required to find where one given actor is related to another. There was a search engine to do just that... usually between any two people there was some maximum number... and it was surprisingly small, like 6 or so. As I recall, that search engine was phenomenally fast. I don't recall whether their algorithm was ever published.
There was also a contest to find two actors who were maximally distanced. Perhaps that number was 11 or so. I forget exactly.
But back to Wikipedia... a more interesting question might be - what is the minimum number of clicks (links) to get from a Wiki entry to your name? Obviously if there is a Wiki page that's specifically about you it is disqualified. In other words, I guess it boils down to: did you ever contribute something authoritative on the internet.