Привет всем!
Хочу представить вам Карту Интернета или результат кластеризации более чем 350 тысяч сайтов в соответствии с переходами пользователей между ними. Размер круга определяется посещаемостью сайта, цвет – национальной принадлежностью, а положение на карте – его связями с другими сайтами. Если два сайта имеют стабильный поток пользователей между ними, то они будут «стараться» расположиться ближе друг к другу. После завершения работы алгоритма, на карте можно наблюдать скопления сайтов (кластеры) объединенные общими пользователями.
Например, если ввести в поиск habrahabr.ru, то можно увидеть, что dirty.ru и leprosorium.ru в том же «созвездии», а еще подальше livejournal.ru. Это говорит о том, что тот, кто сейчас читает этот текст, также с высокой вероятностью посещает эти сайты (относительно усредненного пользователя Рунета конечно).
Еще более интересный пример кластеризации можно увидеть внизу карты, между фиолетовой Японией и желтоватой Бразилией: там расположилась целая порнострана по размерам сопоставимая со всем Евронетом. Интересно, что будучи достаточно компетентным в рассматриваемом вопросе, внутри большого порнокластера можно различить тематические подкластеры меньшего размера.
Тем, кого интересует краткое техническое описание – добро пожаловать под кат
Инженерная часть
Весь проект написан на языке C# и состоит из трех частей: программа кластеризации, программа генерации тайлов и веб-сайт. Каждая часть заслуживает отдельного рассмотрения и, если будет интерес, я бы мог потом рассказать о них подробнее.
Исходные данные были взяты у Алексы, они представляют из себя записи о посещаемости, 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, собрать все воедино и заставить его показывать карту. Здесь в общем-то нет ничего сложного, хотя были некоторые сложности с проекциями и позиционированием карты.
Последний этап – выбор и релиз. Здесь тоже не обошлось без приключений. Сейчас все вертится в облаке Амазона и это оказалось гораздо проще и дешевле, чем я себе представлял.
В общем, у меня накопился некоторый опыт, и я буду рад поделится им с уважаемым сообществом. Конечно в целом ничего особенного, на Хабре бывают действительно интересные проекты и нетривиальные решения, но все же, я думаю, многим это может быть интересно.
Также я буду рад любым идеям, отзывам, критике – любому фидбеку!
Автор: irriss
