Wikipedia as a Graph Through Human History

Breadth-first search (left) | Depth-first search (right)
bool Finder::find_hitler_recursive(int n, Page *page, string path[]){    
// There are sort of 2 base cases here
if(n > MAX) return false;
if(page->name == goal_page){
path[n+1] = goal_page;
return true;
}
// Breadth search
for(size_t i = 0; i < page->links.size(); i++){
if(page->links[i].get_title() == goal_page){
path[n+1] = page->links[i].get_title();
return true;
}
}

Page* nextPage;
if(n != MAX){
for(size_t i = 0; i < page->links.size(); i++){
nextPage = page->get_sub_page(page->links[i]);
// Depth search
if(find_hitler_recursive(n+1, nextPage, path)){
path[n+1] = page->links[i].get_title();
return true;
}
}
}
return false;
}
  • 99.580% of all Wikipedia pages can reach Hitler in at least 3 clicks
  • 96.875% required 3 clicks
  • 2.9490% required 2 clicks
  • 0.1756% required 1 click
  • There were 2,961 unique connections to Hitler
A 2D representation of all 56,935 unique paths to the Adolf Hitler path. An interactive version can be found here.
  • If the target could be reached from multiple paths, only the first path will be returned (which may not be the shortest path).
  • It takes SIGNIFICANTLY longer to determine that it is not possible to reach the target page. This causes the data to be misleading. Because of this, this algorithm will, by nature, find more true paths than negative results.

--

--

--

Computer Science student at The University Of Tennessee Knoxville.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Land use simulation in urban areas

screenshot of LanduseSim software

Types Of Measurements

The Future of White Papers

What Can We Learn From Electricity Consumption in Victoria during Covid-19 Pandemic?

The Benefits of Mobile Sample on Multicultural Research

On the grid: Estimating population density for anywhere on earth

My Salesforce Journey

Generating Tweets Using GPT-2

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Landon Harris

Landon Harris

Computer Science student at The University Of Tennessee Knoxville.

More from Medium

The Shot in the Arm: Improving the Effectiveness of the COVID-19 Vaccination Campaigns

Big Data and Machine Learning Use Cases in the Power Sector

Can you read this title with your peripheral vision?

Is Data Mining Ethical?