24 июля 2012 в 12:21

Карта Интернета

Привет всем!

Хочу представить вам Карту Интернета или результат кластеризации более чем 350 тысяч сайтов в соответствии с переходами пользователей между ними. Размер круга определяется посещаемостью сайта, цвет – национальной принадлежностью, а положение на карте – его связями с другими сайтами. Если два сайта имеют стабильный поток пользователей между ними, то они будут «стараться» расположиться ближе друг к другу. После завершения работы алгоритма, на карте можно наблюдать скопления сайтов (кластеры) объединенные общими пользователями.

image

Например, если ввести в поиск habrahabr.ru, то можно увидеть, что dirty.ru и leprosorium.ru в том же «созвездии», а еще подальше livejournal.ru. Это говорит о том, что тот, кто сейчас читает этот текст, также с высокой вероятностью посещает эти сайты (относительно усредненного пользователя Рунета конечно).

Еще более интересный пример кластеризации можно увидеть внизу карты, между фиолетовой Японией и желтоватой Бразилией: там расположилась целая порнострана по размерам сопоставимая со всем Евронетом. Интересно, что будучи достаточно компетентным в рассматриваемом вопросе, внутри большого порнокластера можно различить тематические подкластеры меньшего размера.

Тем, кого интересует краткое техническое описание – добро пожаловать под кат


Инженерная часть


Весь проект написан на языке C# и состоит из трех частей: программа кластеризации, программа генерации тайлов и веб-сайт. Каждая часть заслуживает отдельного рассмотрения и, если будет интерес, я бы мог потом рассказать о них подробнее.

image

Исходные данные были взяты у Алексы, они представляют собой записи о посещаемости, upstream и downstream переходах юзеров (upstream – откуда пришли, downstream – куда ушли). После нормализации мы получаем взвешенный ненаправленный граф с 350 тысячами вершин и более 2 млн. ребер.

Обсчет такого графа – сложная вычислительная задача, поэтому был написан специальный модуль для GPU, но к счастью он не понадобился. После хитрых оптимизаций весь обсчет занял несколько недель непрерывной работы мощного, но все-таки бытового железа.

Если говорить упрощенно, то работа алгоритма заключалась в пошаговом перемещении сайтов на карте в соответствии с силами действующими на них. Много переходов пользователей – сильная сила старается сблизить сайты; если сайты расположились слишком близко, то начинает работать сила отталкивания и т.д. Подробнее можно посмотреть в этой работе reports-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf

Основная проблема заключалась в колоссальной вычислительной сложности подобного алгоритма. Ведь при решении задачи «в лоб», на каждом шаге нужно вычислять суперпозицию сил для каждого сайта, т.е. вычислять силы для каждой пары сайтов, а таких пар около 122 млрд. (неплохо для одного шага, правда?). Поэтому была проведена жесткая оптимизация алгоритма и полное распараллеливание вычислений. К счастью платформа .net оказалась на удивление хорошей для подобного рода забав.

Вторым этапом идет генерация тайлов. Тайл – это маленькая картинка 256х256 пикселей из которых состоит изображение карты на google maps, yandex и других сервисах. В общем-то, ничего сложного – сгенерил большую картинку, разрезал ее на квадраты нужного размера, делов-то. Но таких картинок оказалось почти 30 млн. Даже просто скопировать или удалить каталог с тайлами в windows занимает два дня. А залить их на хостинг отдельная проблема.

Третий этап – прикрутить движок google maps, собрать все воедино и заставить его показывать карту. Здесь в общем-то нет ничего сложного, хотя были некоторые сложности с проекциями и позиционированием карты.

Последний этап – выбор хостинга и релиз. Здесь тоже не обошлось без приключений. Сейчас все вертится в облаке Амазона и это оказалось гораздо проще и дешевле, чем я себе представлял.

В общем, у меня накопился некоторый опыт, и я буду рад поделится им с уважаемым сообществом. Конечно в целом ничего особенного, на Хабре бывают действительно интересные проекты и нетривиальные решения, но все же, я думаю, многим это может быть интересно.

Также я буду рад любым идеям, отзывам, критике – любому фидбеку!

Спасибо всем за теплые слова! Для меня было очень важно получить поддержку от профессионального сообщества, от людей, которые не только видят результат, но понимают какая огромная работа была проделана для его достижения. Также спасибо Хабру за то, что в Рунете есть площадка объединяющая всех нас!

Продолжение: Веб архитектура Карты Интернета
+210
5040
386
irriss 29,0

Комментарии (146)

+6
namikiri, #
Очень интересная вещь.
Поразила мизерность vk.com, мне всегда казалось, что это огромнейший сайт.
+6
irriss, #
данные старые, vkontakte.ru, еще не переехал
+2
pewpew, #
А меня, например, поразила значимость и весомость yahoo.com, т.к. понятия не имею, для чего он мне мог бы быть полезен.
+1
AEinsam, #
По-моему у многих американцев почта как раз у Yahoo.
+2
namikiri, #
Японцы пользуются Yahoo. У них это как у нас Яндекс.
0
karellen, #
Да много кто в Азии. Гонконгцы те же, а у них там проникновение интернета почти 100%.
0
DimaV83, #
В Великобритании очень много людей им пользуются. Как почтой, так и финансами, плюс новости смотрят.
+1
Ronin, #
Интересно, что ютуб ближе к фейсбуку, чем к гуглу.
+1
Halt, #
Ну так логично. «Прикольные видео» как правило выкладывают у себя на страничках, нежели целенаправленно гуглят.
0
NoMore, #
Данные брались из забугорной Алексы, которая распространена в основном в США. Следовательно, данные для России будут сильно искажены.
+1
netp, #
Очень красиво, наглядно и полезно! Большое спасибо!
–1
Ualde, #
Забавно, но не совсем понял из описания — как часто обновляется (синхронизируется с Алексой) информация?
0
xtile, #
вы прочитали статью?

насколько я понял, расчеты были одноразовыми ( раз уж одна итерация занимает несколько недель )
–1
Ualde, #
Прочитал (ваш вопрос как-то уж очень провокационный, не дело), и именно поэтому задал вопрос, никто ж не мешает фоново (допустим с тем же интервалом в несколько несколько недель) повторять обсчеты.
0
skyblade, #
Каждые несколько недель будет означать постоянную загрузку определенной машины только этими обсчетами. Но вот хотя бы раз в год можно было бы и обновлять без особых издержек…
+1
xtile, #
да, раз в год было бы достаточно.

все же это достаточно медленно меняющиеся данные
+4
morozko, #
Если делать срез данных несколько лет подряд, то очень интересно будет посмотреть, как меняются созвездия: изменения размеров звёзд, блуждания относительно друг друга, колебания окраса «звёздной карты».

Если добавить немного цифр (размер звезды, т.е. посещаемость), то получится очень интересная и красивая инфографика.
0
artch, #
А если обновлять раз в месяц и добиться того, чтобы основные полюсы находились в одних и тех же местах, то можно сделать очень красивую анимацию потом.
+16
FakeFactFelis, #
image

Вы находитесь ↑ здесь.
+18
ertaquo, #
Откуда вы узнали?! Вы следите за мной!
0
wersoo, #
а как рядом расположились тематические медиа и футурико
+4
wersoo, #
текст поста не читай
@
сразу отвечай
+2
ffffffffff, #
У вас «О проекте»:
тело имеющее массу, отдельный пользователь это квант массы ― тот самый [пока] не найденный бозон Хигса, а акт перехода пользователя между сайтами это квант гравитации — гипотетическая частица гравитон.

Вроде нашли же уже)
+2
NickLion, #
Пока ещё нет. Нашли частицу, которая может оказаться бозоном Хиггса. Только сначала ещё хотя бы спин надо определить. Но даже этого не будет достаточно.
+2
mikhailian, #
А можно объяснить цвета?
+1
insekt, #
Насколько я понял цвета связаны с доменными зонами.
0
formatko, #
Доля расизма присутствует.
+1
Kemanorel, #
Тогда непонятно это, например:
image

И попалась пара синих .ru.
+3
formatko, #
Поэтому и написал, что доля. Желтые китайцы, красные русские
0
Kemanorel, #
Так то ж не Вам коммент-то был, а insekt.
0
irriss, #
каждая страна получает свой цвет. Причем страна это не доменная зона, Алекса видимо определяет по whois, я точно не знаю
+2
mihaild, #
Нельзя ли сделать появление надписей на немного меньшем масштабе?
И перерисовка подтормаживает.
+1
skyblade, #
Надписи увеличиваются вместе с масштабом… Видимо они прямо на картинках и без перегенерации тайлов их «появление» не отрегулируешь… Ну это мне так кажется… Автору виднее как там что.
0
irriss, #
именно так
0
Gol, #
А может сделать показ названия в отдельном текстовом поле (где-нибудь рядом с полем поиска) и показывать при наведении мышки на круг
+26
arseny_sokolnikov, #
Только у меня поиск не работает? :(
+6
startsevdenis, #
Вы меня опередили, с вопросом, попробовал в хроме, фаерфоксе и опере, нигде поиск не работает
0
artch, #
Он работает, просто тормозит сильно.
+6
CGS, #
Блин, хоть бы отобразили как нибудь что поиск идёт вообще.
+1
startsevdenis, #
Сколько по времени примерно ждать? Попробовал к примеру найти google.com, уже пару минут никакого ответа.
+1
artch, #
Видимо, уже умерло окончательно.
+2
YouHim, #
Похоже уже совсем не работает.
+1
arseny_sokolnikov, #
Я конечно допускаю, что он сильно тормозит, но 25 минут искать 2eng.ru это по-моему долговато даже для такой системы…
–6
Isopropil, #
Нет. Не только у вас. Поиск долго думает, потом возвращает 500 ошибку. Микрософт ботНЕТ, что с него взять…
+6
ha2bj, #
Вы не узнали? Это же mr. Habraeffect ;-)
0
irriss, #
Прошу меня извинить, не рассчитал нагрузку. База умер ):
+24
pa100r, #
image
+9
usgleb, #
Я бы полетал гуглом :)
–5
VoVanJinn, #
Улыбнуло )
+1
VoVanJinn, #
«Нельзя просто так взять..» (с) и выразить свои чувства на Хабре )
+1
EvilPartisan, #
>>Интересно, что будучи достаточно компетентным в рассматриваемом вопросе, внутри большого порнокластера можно различить тематические подкластеры меньшего размера.
Ну и как? Удалось найти детское порно?
+3
Ocelot, #
Оно же всё в википедии :)
+3
irriss, #
если внимательно присмотреться, то можно разглядеть то самое лобби
0
McGrady, #
Много гуглов у меня выводит)
+5
EvilPartisan, #
Гугл настолько массивен, что вызывает сингулярные флуктуации во многомерном пространстве и проявляется по всей карте в виде виртуальных частиц.
+1
artch, #
Шикарно, спасибо.

Почему-то напомнило карту из EVE Online.
+7
xtile, #
Очень познавательно, спасибо.

Польские энторнеты живут на обочине немецких, а украинские и (тем более) белорусские — внутри российских.

livejournal & liveinternet — полюса, rutracker соседствует с kinopoisk & afisha, а еще с kino-govno, filmz и lostfilm (бгг, намекаю на разумные поглощения :) )

аудитории ixbt, ferra, overclockers и thg — совпадают ( намекаю рекламодателям )

все групоны — на одной орбите гугла (хз на что намекнуть )

спорт-экспресс выбился из своего кластера

и т.д. и т.п.

захватывающе.

планируете ли продолжать тему?

на базе этой инфы можно на самом деле немало платной аналитики делать
0
irriss, #
спасибо. Пока не знаю, идей много инвесторов мало
0
xtile, #
а можно ли собрать данные для того же набора сайтов, но для другой аудитории?

например, для русскоязычной или из России? Этот анализ будет иметь уже весьма практический уклон
+2
irriss, #
я думаю, самое интересное в региональном плане это обработать сообщения/комменты пользователей друг другу на каком нибудь хорошем масштабе (ЖЖ, ВКонтакт), тогда и видно будет где живут политические тролли, кто за бабло, кто за идею, а то сейчас не разобрать все говорят на оппонентов что они покупные
+4
Asmody, #
какое интересное созвездие: awesomescreenshot.com/0d0bav71f
+2
SLY_G, #
У меня поиск не работает, ничего не происходит :(
+3
INCWADRA, #
Поиск работал, а теперь сломался(
НЛО прилетело и опубликовало эту надпись здесь
0
Ronin, #
google.ru — ниже и левее большой livejournal.com — чуть ниже и немного левее, самый крупный недалеко от ЖЖ, habrahabr.ru
0
nojoke, #
Интересна доля поисковиков в зоне Ru. Думал картинка сравнения Yandex,Google,Mail,Rambler совсем другая будет.
Получается, что «Аналитические отчеты» про доли поисковиков мягко говоря лгут.
+1
SemenOk2, #
Это же данные Alexa Rank, а в ней мало русских, лучше всего она работает для штатов.
+1
cblp, #
Ага, и в том числе Алекса, данные которой лежат в основе этой карты.
0
irriss, #
сложно судить о репрезентативности данных Алексы. Я думаю региональные источники дают более точную информацию
НЛО прилетело и опубликовало эту надпись здесь
+2
Phaker, #
Как человек, разбирающийся в вопросе, из бесплатного и для всего мира, включая Россию, рекомендую www.google.com/adplanner/ — это на порядок лучше Alexa. Если есть возможность приобрести платную подписку (десятки тысяч долларов), то посмотрите comScore.
+2
artch, #
Как-то Википедия сильно в еврокосмос уползла. Европейцы ее больше американцев любят что ли?
+1
metya, #
Очень красиво.
0
Sartor, #
Работа прекрасного качества! Мысленно плюсую.
0
Fragster, #
В огнелисе поиск не работает :(
+1
kriptomen, #
Chrome 20, тоже не работает поиск.
+1
sp4rk, #
Там просто выпадает 500-я ошибка. Либо сервис перегружен(хабраэффект), либо там на живую что-то правят.
0
Cynic_spb, #
Еще ни одного комментария про порно-созвездия
+1
INCWADRA, #
0
VasG, #
Кстати, получается, что blogspot.com — в основном для китайцев, иранцев и бразильцев.
А японцы по-прежнему отдают предпочтение Yahoo?
А files.wordpress.com юзают в основном одни индусы. Ну и тайванцы чуть-чуть.
И википедия с last.fm сильно к России смещены.
+4
under_construction, #
круто получилось!

вопросы:
— используется СУБД, если да, то какая?
— сколько в итоге в месяц платите aws?
— почему aws, а не windows Azure?
+2
irriss, #
Спасибо,

-MS SQL Server Express
-после сегодняшнего боюсь разорится
-у Амазона была доступна физическая заливка файлов на хостинг в Сингапуре

постараюсь раскрыть тему в следующих статьях
+1
INCWADRA, #
Казнет такой маленький, весь окружен большим красным Рунетом
0
diwms, #
Ого какая красотища!

Я о многих сайтах узнаю. Спасибо!
0
VladSavitsky, #
Красиво и увлекательно.
yandex.ru не ищет.
wordpress.com вообще на отшибе.
–2
DaleMartinWatson, #
У меня поиск не работает :( Браузер Chrome.
+1
DaleMartinWatson, #
О, заработал!
–2
Eddy_Em, #
Забавно. Только поиск не работает.
–1
antyrat, #
Круто. Мне еще понравилась реализация карты рунета в виде черного квадрата. rukv.ru
0
irriss, #
да, видел, интересно
0
Voenniy, #
Странная реализация.
Сайт habrahabr.ru не найден

Но яндекс нашел, да.

+3
Ocelot, #
Цитата из описания:
Затем сайты начинают перемещаться под действием приложенных сил и через некоторое время останавливаются — силы притяжения стали равны силам отталкивания, система достигла динамического равновесия.

Это вполне статическое равновесие. Динамическое было бы, если бы сайты продолжали двигаться, но их распределение в среднем оставалось постоянным.
–1
irriss, #
Спасибо, поправлю. Конечно же статическое
+3
Nomad1, #
Классно, но очень не хватает перехода на сайт по клику
+1
irriss, #
спасибо, много чего не хватает. Это, несомненно, самая востребованная фича
+1
Halt, #
Было бы неплохо еще давать подсказку или принудительно отображать кликабельный урл при наведении на кружок.

А вообще, сама концепция карты интересна в том плане, что позволяет искать родственные ресурсы. Скажем, если нравится наприемер хабр или оверклокеры то прогулявшись по окресностям можно найти сайты которые с большой вероятностью будут интересны.
0
Morozov, #
Очень интересно. Жаль поиск слег. По Украине очень много сайтов отмечены не тем цветом, например:
ukrinform.ua — синий
mob.ua — красный
cv.ua — красный
0
Morozov, #
Еще длинные названия не влазят на круги. Было бы удобно Всплывающие подсказки при помощи Title в теге map.
+2
MaRio, #
меня очень смущает вот этот логотип new.positivecommunications.ru/wp-content/uploads/2012/06/Logo1.jpg (на positivecommunications.ru/ )
0
irriss, #
Почему он вас смущает? Проект некоммерческий, никакой материальной выгоды нет, одни расходы к сожалению. Эта компания помогла мне, когда я пришел с прототипом на 1000 сайтов и сейчас оказывает информационную поддержку. То что сайт есть и работает в немалой степени заслуга Positive PR
+1
MaRio, #
Логотип отличный, но они зачем-то пытаются уместить 4724×2362 пикселей в 249×125 пикселей
0
gaploid, #
Я вот знал что у многих чиновников почта на меил ру, но судя по этой карте похоже у них у всех почта на меил ру:)
+1
gaploid, #
Картинка не присоеденилась:( вот ссылка img.leprosorium.com/1517635
+1
limon_spb, #
Интересно, почему wordpress.com на отшибе таком?
(слева вверху его можно найти голубым кружком, если у кого поиск не работает)
0
irriss, #
Я думаю сайты такие как go.com и wordpress.com вдалеке, потому что они не несут семантической нагрузки. Т.е. посещаемость большая но отовсюду
+3
Komzpa, #
А почему был использован движок Google Maps? Тот же openlayers.org позволил бы сходу давать постоянные ссылки на места на карте.
0
irriss, #
я не знал про него, спасибо, посмотрю
0
CyrruS, #
Это охуенно.
Спасибо.
0
vanxant, #
И все же надо было европу поднять «на север», а чинанет на её место. Было бы логичнее с точки зрения географии.
+1
irriss, #
неможно ничего поднимать и география здесь особенная. Они так сами расположились
+1
Athari, #
Гыгыгы, вокруг фейсбука вертится всё: GitHub, jQuery, deviantART, Drupal, ASP, ASUS, Joomla, CodePlex, CentOS, RedHat, phpBB, Epson, IANA, HP… Это ж чёрная дыра какая-то.
0
Jedi_Knight, #
А на гиперсфере слабо такое сделать?
0
xtile, #
можете привести пример подобной визуализации?
0
Jedi_Knight, #
В таком контекте — не видел ещё.
Я и сам не знаю как это сделать, но можно попробовать :)

www.roguetemple.com/z/hyper.php — вот такое видел.
0
irriss, #
а зачем?
0
Jedi_Knight, #
С Евклидовой метрикой мало объектов помещается в шар.
0
Aloner, #
А почему wordpress.com оказался таким одиноким? Возле него только две микроскопические блохи.
–1
Shustrik, #
Почему поиск не работает?
–1
Dimchansky, #
Исходные данные были взяты у Алексы

Не могли бы уточнить, кто/что это и дать ссылку?
+1
ork_ne, #
0
irriss, #
Извиняюсь, конечно надо было ссылку сделать alexa.com
0
Dimchansky, #
Спасибо, ничего страшного.
Но не поздно это сделать сейчас (в статье). :)
Не планируете рассказать об алгоритме, его оптимизациях более подробно?
0
cronfy, #
Очень интересная визуализация. А какой минимальный должен быть рейтинг/трафик у сайта, чтобы попасть на карту?

Кстати, не все сайты подписаны. Например, справа от гугла есть красная козявочка parsian-film.net. А выше него козявочка еще меньше, и нет подписи.
НЛО прилетело и опубликовало эту надпись здесь
+1
Fragster, #
счас вообще ни для чего не работает :(
+23
vinnipuhin, #
Ребята! Самое важное тут:

0
41terMann, #
Замечательный проект!
Кстати, было бы интересно посмотреть на эту карту в динамике… Скажем с шагом, периодичностью в пару месяцев. С другой стороны, подобное исследование динамики может показать о стационарном состоянии системы, при отсутствии изменений в пределах нескольких лет.
0
leventov, #
А их и не будет практически
0
41terMann, #
Ну не скажите, откуда вам знать? Сейчас появляется много новых интересных проектов, которые со временем перетянут на себя часть аудитории, и карта изменится. Анализ динамических изменений — не менее интересная тема для размышлений, и сравнений с другими природными системами.
+4
DmitryBabokin, #
Было бы здорово, если можно было бы ввести несколько сайтов, которые ты посещаешь, и они бы одновременно подсвечивались (или соединялись в созвездие линиями). Можно было бы наглядно посмотреть на свой «ареал обитания» на этой карте.
0
leventov, #
Очень круто!
Есть 2 минуса:
1) Данные Алексы о пользовательских потоках могут заметно отличаться от реальных, потому что львиная доля среза Алексы — это жителей США. Например, если жители США часто «переходят» с thesun.co.uk на gov.ru и обратно, это вовсе не означает, что так поступает большинство посетителей gov.ru, которые живут, очевидно, в России.
2) Двумерное пространство ограничивает информативность. Судя по всему, хорошо выявляется макроструктура (страны + порно) и микроструктура — группы непосредственно соседствующих сайтов. «Средний» уровень соседства вряд ли о что-то означает.
0
spycom, #
That is really awesome, but internet is not 2D! let's think how we can add some dimensions…
0
AlexanderG, #
Как-то раз присутствовал при обсуждении подобной задачи, но для бизнеса: нарисовать карту отношений компаний и холдингов, чем больше взаимный оборот, тем ближе. Пришли к тому, что для нормальной визуализации потребовалось бы четыре измерения…
+4
Yakiv_Gluck, #
Если не вдаваться в практическую сторону, сама идея и её исполнение силами одного человека… завораживает. Спасибо вам и тем, кто хоть как-то помог.

Хотел, кстати, тоже написать, что сразу же начал грезить о таком в 3D. Правда, я сходу не пойму, как тут можно глубину использовать.
0
Stas911, #
А gephy не смотрели? Он вроде тоже так умеет рисовать
+2
webhamster, #
Большой респект создателю этого проекта. Все сделано на уровне — и идея, и техническая реализация.

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

–2
phillzz, #
Если прикрутить ещё и поиск по кейвордам, то будет айс.
0
Cynic_spb, #
Мне еще показалось интересным, что Спортс.ру как-то совсем далеко от чемпионата и соккера.
Выходит у них разная аудитория не только по субъективным ощущениям.

Прикольно наблюдать как с чемпионатом соседствует фратрия, ибо всегда казалось, что чемпионат слишком мясной. Теперь этому есть официальное подтверждение.
+1
spacediver, #
Не хватает всплывающей подсказки с названием сайта по наведению курсора на малый кружочек.
–2
mr_jok, #
ещё вариант — www.rukv.ru/ (Чёрный квадрат Рунета)
0
pletinsky, #
Иран на удивление большой. На уровне крупнейших европейских стран.
0
Santehnik, #
Забавно! Форум по мобильной связи в окружении банков и почт. Сразу палит что народ на сайте очень активно торгует :) а вот «мир транспортников» практически отсутствует, есть только парочка крупнейших сайтов, и те не сильно рядом :(
+1
yans, #
Отличная карта, с удовольствием донатнул.
Хотелось бы двух вещиц — чуть более ускоренной прорисовки карты и более свежей картинки 2012ого года.
0
irriss, #
Спасибо! CloudFront старается как может. В новой, свежей версии все будет лучше
0
XMLshop, #
irriss, блестящая работа. Респекты и всяческия уважения.
0
irriss, #
Спасибо!

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.