Data is generated using English wikipedia dumps (20110526). You may remember similar efforts from 2007. Technical details and source code are available at github page.
| Year | 2007 | 2011 |
|---|---|---|
| Articles | 2301486 | 3673935 |
| Article links (AL) | 55550003 | 224968403 |
| Categories | 712744 | |
| Category links (CL) | 15082844 | |
| All nodes | 4386679 |
To give an example, this non-existing article "Penny Can" (shown below) has 3 outgoing article links (AL) and 2 category links (CL). Former are directed whereas latter are undirected, individually they create two different graphs. Each article and category is represented as a node.
PageRank is probability that surfer of will be located at a particular article, following ALs randomly. For technical reasons, links from one article to another are counted just once.
| Component size | How many? |
|---|
| 3464433 articles | 1 |
| 376 articles | 1 |
| 64 articles | 1 |
| 61 articles | 1 |
| 53 articles | 1 |
| 45 articles | 1 |
| 34 articles | 1 |
| 25 articles | 2 |
| 23 articles | 1 |
| 21 articles | 1 |
| 20 articles | 3 |
| 18 articles | 1 |
| 17 articles | 2 |
| 16 articles | 1 |
| 15 articles | 5 |
| 14 articles | 2 |
| 13 articles | 1 |
| 12 articles | 3 |
| 11 articles | 8 |
| 10 articles | 11 |
| 9 articles | 5 |
| 8 articles | 8 |
| 7 articles | 11 |
| 6 articles | 27 |
| 5 articles | 50 |
| 4 articles | 112 |
| 3 articles | 448 |
| 2 articles | 3059 |
| 1 articles | 199789 |
Compared to reports from 2007, now we see more a lot more of non-trivial small components.
| 2007 | 2011 | |
|---|---|---|
| Average min-distance (clicks) | 4.573 | 4.470 |
| Average reachable articles | 3463657.0 |
| Nodes | Average distance |
|---|
If we try to eliminate some obvious listings, you are left with:
| United_States | (3.469) |
| QI_(G_series) | (3.474) |
| History_of_Western_civilization | (3.474) |
| London | (3.487) |
| Never_Ending_Tour | (3.487) |
Link is formed when one node (article/category) is declared to be in a category (see example at the top of the page). CLs are undirected, i.e. node belongs to another category and category has nodes in it.
In order to keep results relevant, all nodes that are members of hidden categories and stub categories are stripped-off (nothing links with them). This way hidden and stub categories do not affect these results. Perhaps, I should have treated disambiguation pages same way.
| Average min-distance | 6.492 |
|---|---|
| Average reachable nodes | 4315292.8 |
| Nodes | Average distance |
|---|
| Component size | How many? |
|---|
| 4350840 nodes | 1 |
| 32 nodes | 1 |
| 15 nodes | 1 |
| 9 nodes | 1 |
| 5 nodes | 2 |
| 4 nodes | 2 |
| 3 nodes | 2 |
| 2 nodes | 11 |
| 1 nodes | 35737 |
These results are a bit distorted, since hidden categories and stub categories are considered as nodes with no connections to other nodes (Component size = 1 node).
Here is a pic of a lab that was used. Computers were booted into linux over the network and dataset resided in RAM, this way I didn't have to touch the hard drives with whatever is installed on them.
To complete this report, it takes 100 hours of distributed processing on 19 nodes [AMD Phenom 2.3 GHZ Quad-Core with 2GB RAM]. In addition there is a controller [Intel Pentinum 1.86Ghz Dual-Core with 2GB RAM]. Controller also did some pre and post processing, about 4 hours. Biggest issue with controller was that I had only 2GB of RAM.
To be completely honest, I had to repeat some parts of computation. After getting first results, I realized that Hidden and Stub categories are going to be a problem, so I excluded them, but this meant that entire CLs graph is modified and some previous results are now invalid.
Even though average number of article links per one article has increased, average distance today is similar when compared to 2007. This might indicate that additional links contribute to create highly connected clusters of nodes. Within one group of articles distances are quite small but distance to other groups is larger. Running SCC algorithm did reveal only a few of such components, whereas majority are still in one giant bundle of nodes. Resolving this issue would mean clustering nodes into significantly smaller but relevant groups. This could be a topic of further investigation (suggestions are welcome).
Graph with CL is a new concept that was not done before. It is dominated by Category:Living_People and has slightly larger average distance despite being bidirectional.
I don't like the modern research methodology where nobody else will ever be able to reproduce/recheck results that original researcher found. You can download source of this project in either zip or tar formats. Read more technical details. You can also clone the project with Git by running:
$ git clone git://github.co m/emiraga/wikigraph
