LINUX.ORG.RU
ФорумTalks

Карта википедии

 , ,


2

3

Тут, наверное, пару недель назад кто-то сказал, что было бы интересно взглянуть на карту русской википедии по ссылкам внутри статей. Заюзав все свои 4 гб оперативы и сутки времени, я закодил и сгенерил таковую карту (в качестве helloworld, просто хотел освоить python).

Характеристики:

1 пиксель может содержать от 1 до 4 статей. Чем больше статей в пикселе, тем он светлее. Пиксели без статей чёрные.

Оттенок пикселя определяется средним количеством исходящих и входящих ссылок данной статьи таким образом:

1-33: голубой
34-66: зелёный
67-99: жёлтый

99: красный

Очевидно, красные пиксели — классификаторы разного рода: по датам, по направлениям и т.п, а голубые и зелёные — обыкновенные статьи среднего размера.

На карте видно:

  • Ядро энциклопедии, статья «Россия», а также статьи о других странах (маленький красный кружок в центре)
  • 9 сравнительно независимых участков энциклопедии
  • сотни статей, не связанных с остальными (плавают вокруг основной области связности)
  • 8 основных веток классификаторов, простирающихся от ядра

Следует отметить, что мне чуть-чуть не хватило RAM, чтобы распарсить всю русскую википедию, так что карта построена по половине ссылок (порядка 600 000) и половине связей (около 16 млн). На днях собираюсь докупить рамы и сгенерировать полную карту, включая попиксельную расшифровку, чтобы добавить интерактивности.

Ссылка
Зеркало

★★★

Последнее исправление: Klymedy (всего исправлений: 3)
Ответ на: комментарий от Sadler

веса связей ещё по 4 байта - это всё копейки. карта алгоритма и pixelmap - ну я не знаю каких оно размеров, но я не думаю что вылезет ещё за пару десятков метров.

самые большие раходы на хранение данных об ухлах и url'ах, они-то в хэш таблице хранятся, для быстрого определения уже найденных и обработанных страниц), но этот оверхед не может вылиться ещё в 3 гига...

invy ★★★★★
()
Ответ на: комментарий от Sadler

Я знаю, там и кластеризацию можно наглядную провести. Только вот средствами домашнего писюка такие объемы данных обработать не получится. А в сыром виде этот граф будет выглядеть не намного понятнее полного.

segfault ★★★★★
()
Ответ на: комментарий от Sadler

Ну дурное дело не хитрое, благо там 100М интернеты и много памяти, так что я уже запустил текущий вариант. Но если что, с удовольствием помогу запустить другие варианты.

silw ★★★★★
()
Ответ на: комментарий от segfault

Ну, я не зря выбрал формат карты вершин, по сути примитивная кластеризация и проводится. Граф в классическом варианте действительно на таких объёмах бесполезен.

Sadler ★★★
() автор топика
Ответ на: комментарий от silw

Ну дурное дело не хитрое, благо там 100М интернеты и много памяти, так что я уже запустил текущий вариант. Но если что, с удовольствием помогу запустить другие варианты.

Тот скрипт, что я скинул на pastebin? Там только генерация таблицы рёбер. По ней потом придётся пройтись алгоритмом укладки.

Вот, например, мой код: http://pastebin.com/BryK8Nw7 . Там, правда, для раскраски графа используется файлик indexes.csv и никуда не пишется файлик для сопоставления координат и текста.

Вообще было бы здорово довести до ума это дело.

Sadler ★★★
() автор топика
Ответ на: комментарий от Sadler

да, действительно, только ребра. а про indexes.csv можно поподробнее? что мне сделать чтобы его сгенерировать?

silw ★★★★★
()
Ответ на: комментарий от silw

Вот так я генерил индексы:

http://pastebin.com/h7Y5xnTd

По сути оно просто считает, сколько раз встречаются разные статьи по ссылкам и выводит: index \t title \t count \n , где index — порядковый номер. Сделано для того, чтобы не держать в памяти имена статей во время последнего этапа.

Как список рёбер отработает, можно запускать этот скрипт. на выходе будет mygraph3.csv , его можно переименовать в indexes.csv , а затем запускать саму укладку.

В укладке я поставил 1000 итераций максимум, должно хватить для нахождения устойчивого состояния. Результат, ссылка на котором в оригинальном посте, получился всего за 100 итераций.

Sadler ★★★
() автор топика
Последнее исправление: Sadler (всего исправлений: 1)
Ответ на: комментарий от Sadler

получилось ~ 33 млн ребер и ~ 3.8 млн вершин в indexes.csv

запустил 1000 итераций. О результате, видимо, отпишу уже завтра)

silw ★★★★★
()
Ответ на: комментарий от silw

Отлично. Вершин много потому, что учитываются даже «красные» ссылки википедии. С этим бы тоже бороться, но тут я вижу лишь один простой способ: удалить все статьи без исходящих рёбер. Ну да ладно, эти статьи на внешний вид повлияют мало, будут болтаться где-нить на границе.

Sadler ★★★
() автор топика

А позиция пикселя на карте чем определяется?

Nxx ★★★★★
()
Ответ на: комментарий от Nxx

Почему не использовал спец. софт (Tulip)?

Использовал Graphviz и Gephi. Оба не осилили. Первый не подошёл потому, что формат хранения данных у него дурацкий, входные данные заняли бы десятки гигабайт (и потребление памяти, соответственно, выросло бы) и он вообще неинтерактивный. Второй не имеет достаточно быстрых алгоритмов для таких графов.

Sadler ★★★
() автор топика
Ответ на: комментарий от silw

200 итераций

Хорошо получилось. И тот самый красный кластер куда-то влился в основную часть. Без вывода попиксельных данных, правда, итерации эти малополезны.

Я дописал скрипт, чтобы он выводил попиксельные данные: http://pastebin.com/7hj8nxuP . Если можешь, запусти его, а когда отработает, слей куда-нибудь output_image, indexes и pixelmap. Я попробую сделать из этого веб-сервис, чтоб ткнул мышкой — тебе показало, какая тут статья и какие в окрестностях.

Sadler ★★★
() автор топика
Ответ на: комментарий от silw

Гуд. В обновлённом я, кстати, закомментировал кусочек, отвечающий за прореживание графа. Думаю, так красивее будет смотреться, когда все точки близко прилегают друг к другу.

Sadler ★★★
() автор топика
Ответ на: комментарий от silw

Но какие-то пертурбации внутри все равно происходят.

Да, ещё не совсем устаканилось. Ну, последи, как остановится (либо как надоест, скинь результат, индексы и pixelmap). Полностью остановиться оно не должно, ибо в алгоритме есть рандом на 5 пикселей в сторону, но должно замедлиться достаточно.

Sadler ★★★
() автор топика
Ответ на: комментарий от Sadler

мне не сложно) оно висит себе и считается. Так что, видимо завтра, когда досчитается вся 1000 итераций выгружу куда-нибудь все выходные файлы.

silw ★★★★★
()
Ответ на: комментарий от Komintern

айпи твой на вики не забанили из-за огромного кол-ва запросов?

А ни единого запроса не было. Я просто выкачал базу википедии с их официального сайта http://dumps.wikimedia.org/

Sadler ★★★
() автор топика
Ответ на: комментарий от i-rinat

а, не знал за такую возможность =) интересно, базу ЛОРа так скачать можно?

Komintern ★★★★★
()
Последнее исправление: Komintern (всего исправлений: 1)

Посчиталось. Сочинил торрент. Там правда абсолютно все, так что ненужные файлы, вроде карты ребер и прочего можно отключить. Если в таком виде неудобно, могу пожать только необходимые файлы.

silw ★★★★★
()
Ответ на: комментарий от Sadler

Ночью падало питание во всем корпусе, так что машинка отключалась. Вернул обратно на раздачу. Если что - джаббер в профиле.

silw ★★★★★
()
Ответ на: комментарий от silw

Да, вроде, всё скачалось. Ща думаю, как аккуратнее веб-версию карты состряпать и куда вывесить.

Sadler ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.