Skip to main content



Strongly Connected Component of Web – Wikipedia

There is this game that I played with my friend called : wikipedia race. The screenshot of the Wikipedia Race is presented below.

Wikipedia Race

Urban Dictionary defines and gives an example of Wikipedia Race as the following:

A fun little game to play, where two or more people set a starting page and an ending page, both of which are titles of articles onĀ Wikipedia. Then, using only the links within the text of the article, the goal is to find a way to the ending page before your competitor(s).

A sample Wikipedia race:
Start: Roger Federer
End: Internet

One way is: Roger Federer, to Switzerland, to Europe, to North America, to United States, to Culture of the United States, to Internet!

It can be played alone or with as many people as you want to get from one Wikipedia article to another. The players can only move from one article to the other by clicking the links provided in the current article you are reading. How long it takes, it is very likely that you will find your way to the final article.

Wikipedia articles could possibly be an example of a strongly connected component of web. From Chapter 13 of the text,

We say that a strongly connected component (SCC) in a directed graph is a

subset of the nodes such that: (i) every node in the subset has a path to every

other; and (ii) the subset is not part of some larger set with the property that

every node can reach every other.

The first requirement for strongly connected component (SCC) is that every node in the subset has a path to every other. That is the whole idea behind the Wikipedia Race! You are using the pointers in the articles to move from one node to the other until you get to the ending node. There are over 20 million articles in Wikipedia and each articles have more than one link that points to other Wikipedia articles.

The second requirement for SCC says that the subset is not part of some larger set with the property that every node can reach every other. This is hard to prove, but there is a high chance that Wikipedia articles do not fulfill this requirement to be considered a SCC. Wikipedia has links that points out of Wikipedia for the sources of the articles. These days, Wikipedia is used so widely that it is very easy to find links points into an article of Wikipedia. However, for the purpose of the Wikipedia Race, you are swimming in the pool of 20 million Wikipedia articles until you find the ending article.

Comments

Leave a Reply

Blogging Calendar

November 2011
M T W T F S S
« Oct   Aug »
 123456
78910111213
14151617181920
21222324252627
282930  

Archives