Printable View
find an article on Wikipedia that doesn't lead to Adolf Hitler within 8 links
Post failures as well as successes
example:
http://en.wikipedia.org/wiki/Chertsey_Lock
http://en.wikipedia.org/wiki/City_of_London
http://en.wikipedia.org/wiki/World_War_II
http://en.wikipedia.org/wiki/Adolf_Hitler
Its called the Matt Damon effect, all things link to Matt Damon (or Adolf Hitler) within 6 links.
Hitler is too easy, as anything you can connect to europe is automatically connected to hitler within 2 links (ww2, hitler) and by extension you can connect europe via continent, which connects to any other country which connects to anythign that hapened or exists in that country, so 6 links to hitler max.
Rice Pudding
Rice
China
WW2
Hitler
Matt Damon
Movies
Television
Hitler
Doesn't that mean that "Hitler" is difficult, since the aim of the game is to "find an article on Wikipedia that doesn't lead to Adolf Hitler within 8 links"?Quote:
Originally Posted by abachler
Perhaps he meant that too easy to find = too hard not to find.Quote:
Originally Posted by laserlight
This problem isn't interesting enough. What I want is for somebody to describe an algorithm which tries to find the shortest path between any pair of articles. A solution to that automatically solves the original problem, and might tell us something informative about Wikipedia.
Crap! I hate these NP-Complete kind of problems ;)
Wikipedia is a graph G where each article is a node and each internal link constitutes a directed edge to another node. Dijkstra's algorithm finds the shortest paths from a given node to every other node in the graph. Thus, finding the shortest path for any pair of nodes is fairly simple: for each node n in G, call Dijkstra(G, n).Quote:
What I want is for somebody to describe an algorithm which tries to find the shortest path between any pair of articles.
As Wikipedia isn't exactly sparse, Disjkstra has a running time of O(|V|^2 + |E|), where V is the set of nodes/vertices/articles and E is the set of edges. Note that |E| is smaller than |V|^2 in this case (|E|==|V|^2 if every article contains a link to every other article), so we can safely omit the |E| in our analysis. As we're calling Dijkstra as many times as there are nodes in G (i.e. |V| times), the overall complexity is O(|V|^3).
This is far from being NP-complete, although I wouldn't want to compute it for the approximately 2.8 million English Wikipedia articles.
Greets,
Philip
Shortest path problems aren't NP-complete. Wikipedia has 2.8 million articles, and as a rough guess, 50 links per article on average. That's quite doable. For finding the shortest path between any single given pair of articles, you use Dijkstra's Shortest Path algorithm, which for a non-sparse graph (and Wikipedia definitely isn't sparse) has a worst case complexity of O(|V|² + |E|) == O(|V|²).
Edit: Meh. Snafuist beat me to it. Anyway, 2.8 million² == 7,84x10^12 (7.84 trillion) operations. Heh. Will take a while, I suppose.
Well, we all know algorithms to find shortest paths. The problem is that we don't have access to the complete graph structure of Wikipedia. We can only go to a page, see the links there, and click on them.Quote:
Originally Posted by CornedBee
So, working on the assumption that you do NOT know the edges from a node until you actually visit that node, what kind of heuristic could be used to navigate the graph to any arbitrary node? What method would a human use?
Is it a requirement to know the entire graph in order to use Dijkstra's algorithm? I had the impression that it can work even if the information about the next node's next nodes is not available until the next node is visited.Quote:
Originally Posted by brewbuck
...which you don't have to know in order to use Dijkstra (you probably meant what you said plus "do not know that a node exists until you've been there")...Quote:
Originally Posted by brewbuck
Brute force, i.e. BFS or DFS.Quote:
, what kind of heuristic could be used to navigate the graph to any arbitrary node?
What do you want to achieve? Start at a random node and minimize the hops to "Hitler" without full knowledge about the graph?
There are two possibilities:
1)
either the distance between any two nodes is < infinity. Then applying Dijkstra to one node reveals all other nodes (and you can call Dijkstra recursively on those to get all shortest paths between any two nodes)
2)
or the distance between two nodes equals infinity, i.e. the graph consists of subgraphs which are not connected with each other. Then the problem of finding all shortest paths can't be solved without knowing all nodes in advance, but at least any node outside of the "Hitler" subgraph satisfies the conditions from the OP
Greets,
Philip
Downloading and parsing the entire Wikipedia is linear, though. :) Sloooooooooow linear, probably.
Another approach to solve the original problem: Wikipedia features backlinks (i.e. for every article, it's possible to find out the articles that link to it). So going to the "Hitler" page, viewing its backlinks, visiting all these pages, viewing their back links and so on 8 times will reveal all articles that refer to "Hitler" in 8 hops. Every other article doesn't.
Greets,
Philip
I'd argue that Wikipedia is very sparse! According to one site, there are "2,301,486 articles with 55,550,003 links between them". There are a maximum of 5,296,835,506,710 links with that many articles, or you have .001048% of the total possible links. (Ask yourself: Does any given article link to most other articles? No.) Given that number though, it's pretty amazing how quickly you can prove Godwin right.Quote:
As Wikipedia isn't exactly sparse
Additionally, why not use BFS? BFS should find the shortest path, and in better running time too! Although you'll probably need quite a bit of mem memory for the queue & the visited list. (although you'll still need memory with Dijkstra...)
I don't think BFS or DFS would be good choices for such a problem. It's better to use a smart search when possible.
(PS My NP-Complete joke was just that...a joke).
Anyways, the best choice for the job would be the "Learning Real-time A* Algorithm" (not regular A* which is similar to Dijkstra's).
Learning Real-time A* works under the assumption that the entire graph isn't really "known"...and it finds the same solution as A* or Dijkstra's would in a few more iterations of the algorithm.
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.
Orphaned pages are ones that aren't linked to, they can still link to Hitler (I have encountered 3 that did)Quote:
Originally Posted by whiteflags
It was originally Kevin Bacon. Now in 2009 I wouldn't be surprised if Matt Damon is the centre of the co-star graph.Quote:
Originally Posted by Akkernight
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.
nopeQuote:
Originally Posted by nonoob