Карта Интернета, или результат кластеризации ...

[ Версия для печати ]
Добавить в Telegram Добавить в Twitter Добавить в Вконтакте Добавить в Одноклассники
Страницы: (3) [1] 2 3   К последнему непрочитанному [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]
elektroangel
24.07.2012 - 12:19
Статус: Offline


Шутник

Регистрация: 27.05.11
Сообщений: 41
89
Взято отсюда
Привет всем!

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

Карта Интернета
 
[^]
Yap
[x]



Продам слона

Регистрация: 10.12.04
Сообщений: 1488
 
[^]
elektroangel
24.07.2012 - 12:20
Статус: Offline


Шутник

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

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

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


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


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

Это сообщение отредактировал elektroangel - 24.07.2012 - 12:22

Карта Интернета
 
[^]
elektroangel
24.07.2012 - 12:20
Статус: Offline


Шутник

Регистрация: 27.05.11
Сообщений: 41
Исходные данные были взяты у Алексы, они представляют из себя записи о посещаемости, 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, собрать все воедино и заставить его показывать карту. Здесь в общем-то нет ничего сложного, хотя были некоторые сложности с проекциями и позиционированием карты.

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

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

Также я буду рад любым идеям, отзывам, критике – любому фидбеку!
 
[^]
asucorp
24.07.2012 - 12:20
2
Статус: Offline


Змей Пердун

Регистрация: 25.03.12
Сообщений: 324
А Вконтакт где?
Нашел...
Кстати:

Это сообщение отредактировал asucorp - 24.07.2012 - 12:50

Карта Интернета
 
[^]
bokun
24.07.2012 - 12:22
5
Статус: Offline


Ярила

Регистрация: 27.10.09
Сообщений: 1090
ЯП где?
 
[^]
труътер
24.07.2012 - 12:22
1
Статус: Offline


十三

Регистрация: 19.07.12
Сообщений: 36
asucorp , в параллельной вселенной


bokun, а яп-он везде

Это сообщение отредактировал труътер - 24.07.2012 - 12:23
 
[^]
Ю888
24.07.2012 - 12:23
0
Статус: Online


молодой чемодан

Регистрация: 25.12.08
Сообщений: 2563
где упячка?
 
[^]
XRAY26
24.07.2012 - 12:23
24
Статус: Offline


алко-самец

Регистрация: 1.09.11
Сообщений: 439
где порносайты я спрашиваю?!?!?!
 
[^]
eph1r
24.07.2012 - 12:24
10
Статус: Offline


Ярила

Регистрация: 24.12.08
Сообщений: 2735
Цитата (asucorp @ 24.07.2012 - 15:20)
А Вконтакт где?

в трэше lol.gif
 
[^]
Тюменский
24.07.2012 - 12:29
-3
Статус: Offline


Юморист

Регистрация: 17.06.12
Сообщений: 494
Надо пикчу побольше, шобы мона было увеличить и поразглядывать шо где, а то так только 4 зоны понятны и доступны.

Это сообщение отредактировал Тюменский - 24.07.2012 - 12:29
 
[^]
XMerv
24.07.2012 - 12:32
1
Статус: Offline


Шутник

Регистрация: 2.12.11
Сообщений: 45
Вот все работает, с приближением/перемещением, поиском как в google maps http://internet-map.net/

Это сообщение отредактировал XMerv - 24.07.2012 - 12:33
 
[^]
Belgorodec
24.07.2012 - 12:35
8
Статус: Offline


UQ collector

Регистрация: 3.09.11
Сообщений: 2156
Цитата (bokun @ 24.07.2012 - 12:22)
ЯП где?

ЯП - черный фон
 
[^]
gadukin
24.07.2012 - 12:36
3
Статус: Offline


Приколист

Регистрация: 15.08.11
Сообщений: 288
Где youporn.com и porntube.com я спрашиваю?
 
[^]
baronet
24.07.2012 - 12:36
11
Статус: Offline


Юморист

Регистрация: 1.06.09
Сообщений: 529
Поисковик не работает)
 
[^]
Miksen
24.07.2012 - 12:36
2
Статус: Offline


Шутник

Регистрация: 23.07.12
Сообщений: 8
Чето в ФФ поиск на карте не пашет
 
[^]
Zinchuk
24.07.2012 - 12:36
2
Статус: Offline


Приколист

Регистрация: 2.11.11
Сообщений: 243
bokun
ЯП здесь! gigi.gif
 
[^]
FREEMAN
24.07.2012 - 12:45
0
Статус: Offline


L2/L3 puppeteer

Регистрация: 22.04.08
Сообщений: 1028
Цитата (Miksen @ 24.07.2012 - 12:36)
Чето в ФФ поиск на карте не пашет

Ага, тоже попробовал - google.com не нашел dont.gif

Но выглядит это все просто феерично! pray.gif pray.gif pray.gif pray.gif

Это сообщение отредактировал FREEMAN - 24.07.2012 - 12:46
 
[^]
Uzh
24.07.2012 - 12:46
0
Статус: Offline


Приколист

Регистрация: 10.01.11
Сообщений: 236
Справа вверху - красные круги - Россия
 
[^]
YPreader
24.07.2012 - 12:47
10
Статус: Offline


Читатель

Регистрация: 19.07.11
Сообщений: 209
Поиск не пашет, нашел сам

Карта Интернета
 
[^]
nomer37
24.07.2012 - 12:49
6
Статус: Offline


_____

Регистрация: 22.06.09
Сообщений: 2206
Кому там ЯП надо

Карта Интернета
 
[^]
FREEMAN
24.07.2012 - 12:49
0
Статус: Offline


L2/L3 puppeteer

Регистрация: 22.04.08
Сообщений: 1028
Цитата (YPreader @ 24.07.2012 - 12:47)
Поиск не пашет, нашел сам

Ага, там фишки.нет рядом smile.gif
 
[^]
nomer37
24.07.2012 - 12:49
2
Статус: Offline


_____

Регистрация: 22.06.09
Сообщений: 2206
и прон

Карта Интернета
 
[^]
Stepcheg
24.07.2012 - 12:52
1
Статус: Offline


Шутник

Регистрация: 16.03.12
Сообщений: 12
Нашёл русский сегмент

Карта Интернета
 
[^]
16летний
24.07.2012 - 12:54
2
Статус: Offline


Регистрация: 4.06.12
Сообщений: -2
я не могу найти ни один сайт с порнухой. cry.gif пиздешь присутствует?
 
[^]
picmir
24.07.2012 - 12:55
0
Статус: Offline


Шутник

Регистрация: 12.04.12
Сообщений: 44
поиск не работает
 
[^]
Понравился пост? Еще больше интересного в Телеграм-канале ЯПлакалъ!
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста, или зарегистрируйтесь, если не зарегистрированы.
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) Просмотры темы: 15468
0 Пользователей:
Страницы: (3) [1] 2 3  [ ОТВЕТИТЬ ] [ НОВАЯ ТЕМА ]


 
 



Активные темы






Наверх