Когда я был студентом, Википедия оказалась одним из самых недооцененных бесплатных инструментов. Часто это лучший результат для любого поискового запроса Google, и на то есть веская причина: он предоставляет удобное краткое изложение выбранной темы, а также всесторонний анализ. По совпадению, страница всегда содержит чрезмерное количество ссылок, ссылающихся на любые упомянутые страницы или понятия (даже не обязательно релевантные). В результате существует множество интересных игр, в которые можно играть, но меня очаровала так называемая вики-игра.
Вики-игра
Мотивация для этого проекта возникла, когда я работал над отчетом, и мой друг упомянул игру, в которую можно играть в Википедии. Он объяснил игру так: вы начинаете со случайной ссылки на статью в Википедии и, нажимая только на ссылки в теле статьи (и последующих статей), вы можете перейти на страницу Адольф Гитлер за 3 клика. На первый взгляд, это правда! (Если вы обдуманно и стратегически подходите к ссылкам, которые вы выбираете).
После того, как последние несколько часов я был завален написанием, я решил сделать перерыв и немного изучить эту тему. Я, что интересно, не нашел данных по этой так называемой игре, поэтому решил изучить ее сам (а почему бы и нет!). Я называю это:
Сетевой картограф Википедии
Этот проект фокусируется на идее, что можно попасть на особенно распространенную страницу Википедии с любой другой страницы Википедии. Я начал этот проект с идеи использования рекурсии, но в итоге реализовал гибрид между алгоритмами Поиск в ширину и Поиск в глубину.
Чтобы решить эту… «Проблему Гитлера», алгоритм начинается со страницы «Случайная статья» в Википедии. Он перебирает все ссылки на этой странице, проверяя, соответствуют ли они заголовку целевой страницы, если нет, он начинает с первой ссылки и повторяет процесс поиска заголовков ссылок, а затем нажимает на первую ссылку. Эта программа будет переходить только на максимальную глубину, указанную перед сбоем, в результате чего алгоритм начнет поиск страницы со следующей ссылки предыдущего уровня (в стиле поиска в ширину).
Код
Вот упрощенный фрагмент рекурсивного цикла, выполняющего фактический поиск в реализации C++:
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;
}
Полный набор кода можно найти в репозитории github по адресу https://github.com/lharri73/wikipediaProject.
Результаты
То, что я нашел из этого, было, честно говоря, довольно удивительным (но может ввести в заблуждение и будет рассмотрено позже). Необработанные данные из моих выводов можно найти в этом CSV-файле (он большой, и вам придется скачать его, чтобы просмотреть, так как Github не сможет показать вам предварительный просмотр). Вот некоторые из основных моментов:
- 99,580% всех страниц Википедии можно найти Гитлера как минимум за 3 клика.
- 96,875% требуется 3 клика
- 2,9490% требуется 2 клика
- 0,1756% требуется 1 клик
- С Гитлером была связана 2 961 уникальная связь.
С необработанными данными вы можете начать с первого столбца, перейти на эту страницу Википедии и найти ссылку во втором столбце. Обратите внимание, что файл CSV содержит название страницы в том виде, в каком оно отображается в заголовке, а не текст ссылки (ссылка Английский может указывать на страницу Английский язык, поэтому Английский язык появится в файле csv, а не английский). Продолжайте, пока не дойдете до целевой страницы, в данном случае Адольф Гитлер.
Я решил пойти дальше. Смотреть на необработанные данные в виде электронной таблицы может быть очень весело, поэтому следующим очевидным шагом было создание графика. Простого бинарного дерева было недостаточно, поэтому я остановился на сети, где каждый узел может иметь n соединений, а размер узла прямо пропорционален n. Я создал 2 графика, один из которых представляет собой простое изображение, показывающее общую архитектуру графика в 2D, а другой — интерактивный 3D-график. Интерактивный график можно найти по адресу https://lharri73.github.io/wikipediaProject/.
Ограничения
Из-за подхода, который эта программа использует для решения проблемы Гитлера, у алгоритма есть несколько ограничений, а также нюансы, которые коррелируют с некоторой предвзятостью.
- Если цель может быть достигнута несколькими путями, будет возвращен только первый путь (который может не быть кратчайшим путем.
- Требуется ЗНАЧИТЕЛЬНО больше времени, чтобы определить, что доступ к целевой странице невозможен.
- Это приводит к тому, что данные вводят в заблуждение. Из-за этого этот алгоритм по своей природе находит больше истинных путей, чем отрицательных результатов.
Заключение
Во-первых: нет, я не одержим Гитлером, и это не отражает моих политических взглядов, это просто вывод довольно интересного набора данных.
На самом деле не так уж и удивительно, что Адольф Гитлер так распространен среди доменов Википедии. Причина, по которой так легко попасть на эту страницу, кроется в том влиянии, которое он оказывал на людей на протяжении всей истории. На странице Вики-игры на самом деле есть вариант, в котором вместо перехода на страницу Адольфа Гитлера за 3 клика, страница Иисуса Христа открывается за 5 кликов (что является интересным наблюдением, учитывая, что Гитлера можно легко достичь за 3 клика). ). В целом, я считаю, что можно достичь любого исторически значимого человека, события или места таким же образом, как Адольф Гитлер, и, возможно, даже с той же частотой, это просто потребует дальнейшего изучения. На данный момент, однако, я считал эту простую игру тщательно изученной.
