Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Six Degrees of Wikipedia

sixdegreesofwikipedia.com

Post reply on HN
Print view View original

121–130 of 354 posts

Re: Show HN: Six Degrees of Wikipedia

#121

Post by jwngr »

sinaa wrote: post #108
jwngr wrote: post #13

Creator here. Six Degrees of Wikipedia is a side project I've been sporadically hacking on over the past few years. It was an interesting technical challenge and it's fun to play with the end result. Here's the tech stack: * Frontend: React (Create React App) * Backend: Python Flask * Database: SQLite * Web (frontend) hosting: Firebase Hosting * Server (backend) hosting: Google Compute Engine (it runs fine on a tiny…

Great work! Do you simply do a BFS to find the shortest paths? If so, are you doing any tricks to avoid the path explosion problem?

Thanks! I'm glad you asked. I actually do what I call a bi-directional breadth first search[1]. The gist of it is that instead of just doing a BFS from the source node until I reach the target node, I do a reverse BFS from the target node as well and wait until the two searches overlap. That helps with the exploding path problem, although that still becomes an issue for longer paths (>= 5 degrees generally). I also pre-compute all the incoming and outgoing links for each page when I create the database[2] so I don't need to do that upon every search, which resulted in a huge performance boost.

[1] https://github.com/jwngr/sdow/blob/a2699dc95d884ec64a4641630... [2] https://github.com/jwngr/sdow/blob/a2699dc95d884ec64a4641630...

Re: Show HN: Six Degrees of Wikipedia

#122

Post by jcranmer »

jwngr wrote: post #107
dbranes wrote: post #75

Earlier quoted context omitted.

Well that question only makes sense for connected graphs, we don't really know whether this is connected. So in general a version of this question that makes sense is, among all the connected components of the wikipedia graph, what is the largest diameter.

This is an interesting question that I'd like to answer now that I have all the data. I am curious to see how long it will take to find a solution as I believe even the most efficient algorithms for this have a high runtime complexity. And yes, the graph is not connected (there are both nodes with no outgoing links and with no incoming links), but over 99% of the pages are connected, so the answer would still be inte…

Floyd-Warshall solves the all-pairs shortest path in time O(V^3). Running a BFS search rooted from every node would find the shortest path in an unweighted graph in O(V*(V + E)).

Re: Show HN: Six Degrees of Wikipedia

#123

Post by fapjacks »

Actually, interestingly, I've been introducing this concept as a "party game" with other nerds at RL gatherings for some years now. The goal is to start on a random page and find the shortest path to another random page by only clicking links in the articles. It can be quite a lot of fun, despite what you're thinking! And anybody can understand the challenge and compete and have fun. It's not just something for geeks.

Re: Show HN: Six Degrees of Wikipedia

#124

Post by fishtoaster »

jwngr wrote: post #107
dbranes wrote: post #75

Earlier quoted context omitted.

Well that question only makes sense for connected graphs, we don't really know whether this is connected. So in general a version of this question that makes sense is, among all the connected components of the wikipedia graph, what is the largest diameter.

This is an interesting question that I'd like to answer now that I have all the data. I am curious to see how long it will take to find a solution as I believe even the most efficient algorithms for this have a high runtime complexity. And yes, the graph is not connected (there are both nodes with no outgoing links and with no incoming links), but over 99% of the pages are connected, so the answer would still be inte…

Another interesting question would be what the largest graphs are that are disconnected from the "main" one. Are there any larger than 1 or 2 nodes? Is there some set of pages on some obscure topic that only link within themselves?

Re: Show HN: Six Degrees of Wikipedia

#125

Post by wldcordeiro »

fapjacks wrote: post #123

Actually, interestingly, I've been introducing this concept as a "party game" with other nerds at RL gatherings for some years now. The goal is to start on a random page and find the shortest path to another random page by only clicking links in the articles. It can be quite a lot of fun, despite what you're thinking! And anybody can understand the challenge and compete and have fun. It's not just something for geeks…

I had run into it with specifically how many links to get to the page for Hitler.

Re: Show HN: Six Degrees of Wikipedia

#126

Post by kazinator »

Please make it Ctrl+Scroll to zoom (a UI standard obeyed in umpteen applications!), and leave Scroll alone for scrolling through the page.

Nobody wants to have to click outside the graph view to change the state of the UI so that Scroll scrolls the page.

(Of course, Ctrl+Scroll is already taken for browser zoom; but hijacking browser zoom in this situation is more acceptable than hijacking vertical scroll).

Re: Show HN: Six Degrees of Wikipedia

#127

Post by stirner »

jwngr wrote: post #100
vanderZwan wrote: post #90

Earlier quoted context omitted.

I had a conversation with a friend a few weeks ago that surely this already exists, and if not that someone should make this. Any plans to filter by mutual paths?

I'm definitely not the first to think of it or build a tool for it (lots of similar projects gave me inspiration), but I think I'm the first to make it really fast and with a nice usable UI. And to actually open source the code so others can build it themselves. Can you tell me more about what you mean by filtering by mutual paths?

I implemented this pretty naively a while back [1]. I was interested in how yours was so fast. I expected some sort of complex heuristic; cool to see that your solution is straightforward!

[1] https://github.com/wwalexander/wikipath

Re: Show HN: Six Degrees of Wikipedia

#128

Post by jwngr »

bluetwo wrote: post #99
jwngr wrote: post #13

Creator here. Six Degrees of Wikipedia is a side project I've been sporadically hacking on over the past few years. It was an interesting technical challenge and it's fun to play with the end result. Here's the tech stack: * Frontend: React (Create React App) * Backend: Python Flask * Database: SQLite * Web (frontend) hosting: Firebase Hosting * Server (backend) hosting: Google Compute Engine (it runs fine on a tiny…

I would like to hear a little more on how you organized the search and what you are pre-processing and what you calculate on-the-fly. Thanks.

The database creation script[1] has a lot of Unix junk in it, but reading through the comments and echo statements should give you an idea of what it does. The end result is a SQLite database with a size of about 9 GB which has four tables, the schema of which are described in the README[2]. The big things that are precomputed are redirects are "auto-followed" to reduce the total graph size and all incoming and outgoing links are stored in a |-separated string for each page (in the `links` table).

Every time a query is made, a bi-directional breadth-first search[3] is run which uses the |-separated incoming and outgoing links and runs a fairly standard BFS algorithm. A lot of the hard work was precomputed, which minimizes the number of required database queries and makes each search respond fairly quickly.

[1] https://github.com/jwngr/sdow/blob/master/database/buildData... [2] https://github.com/jwngr/sdow#database-creation-process [3] https://github.com/jwngr/sdow/blob/master/sdow/breadth_first...

Re: Show HN: Six Degrees of Wikipedia

#129

Post by [deleted] »

jwngr wrote: post #93
turc1656 wrote: post #78

Not sure if you deliberately designed it this way, but I noticed when spot checking some results that it includes the bibliography section links as connections. This seems like it may not be desirable. Example, I did a search that went from the Crusades to Buzz Aldrin and I noticed that Routledge was the first hop from the Crusades. It strikes me as odd that Routledge (a publishing company) would be mentioned on the…

Yeah unfortunately I don't know of any way to differentiate the different types of links. Wikipedia's pagelinks database doesn't different them. I agree it's undesireable but I just cannot figure out how to cull them.

[deleted]

Re: Show HN: Six Degrees of Wikipedia

#130

Post by prophesi »

mung wrote: post #113
ng-user wrote: post #92

Earlier quoted context omitted.

'Please' and 'thank you' go a long when requesting additional features for an OSS project.

It's a suggestion, not a request and a good one at that. So who should be saying 'thank you' here (if anyone)?

Tact.
Post reply on HN