619
Карта Інтернет
Звідси.
Привіт, кожен!
Я хочу показати вам Інтернет-карту або результат кластеризації більше 350,000 сайтів відповідно до переходу користувачів між ними. Розмір кола визначається відвідуваністю сайту, кольором - національністю, а позиція на мапі - його посилання з іншими сайтами. Якщо два сайти мають стійкий потік користувачів між ними, вони намагаються ближче до одного. Після завершення алгоритму на карті можна спостерігати кластери сайтів (кластерів) об’єднаних загальними користувачами.
Наприклад, якщо ви шукаєте habrahabr.ru, ви можете побачити, що брудні.ru і leprosorium.ru в тій же «сtellation» і навіть далі від livejournal.ru. Це говорить про те, що хто-небудь читає цей текст зараз, ймовірно, відвідує ці сайти (відносний до середнього користувача RuNet).
Ще більш цікавий приклад кластеризації можна побачити в нижній частині карти, між пурпурною Японією і жовтуватою Бразилії: є ціла країна в розмірах, порівнянні з цілою євромережею. Цікаво, що достатня компетентність в цій матерії, в рамках великого кластеру порно можна виділити менші тематичні підкласники.
Для тих, хто цікавиться короткий технічний опис, ласкаво просимо до kata.
Інженерна частина
Весь проект написаний в C# і складається з трьох частин: програми кластеризації, програми для створення плитки та сайту. Кожна частина заслуговує окремого розгляду і, якщо є інтерес, я міг розповісти про них пізніше.
Ініціальні дані були взяті з Alexa, вони є записи про відвідуваність, переходи в потік і внизу трафіку користувачів (потоку – де вони прийшли з, внизустрі – де вони пішли). Після нормалізації ми отримуємо ваговий непрямий графік з 350 тис. вершин і більше 2 млн. ребер.
Розрахунок такого графіка є складним обчислювальним завданням, тому був написаний спеціальний модуль для GPU, але необов'язково. Після розумних оптимізацій, весь розрахунок займає кілька тижнів безперервної роботи потужних, але ще і побутових прасок.
Щоб поставити його просто, робота алгоритму полягає в покроковому русі сайтів на карті відповідно до сил, що діють на них. Багато переходів користувачів – сильна сила намагається наблизити сайти разом; якщо сайти занадто близькі, сила відповідей починає працювати і т.д. Для отримання додаткової інформації див. звіти-архів.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf
Основна проблема була величезною обчислювальною складністю цього алгоритму. Після того, як при вирішенні проблеми «в голові», на кожному кроці потрібно розрахувати надположення сил для кожного майданчика, тобто розрахувати сили для кожної пари сайтів, і є близько 122 мільярдів таких пар (не погано для одного кроку, прямо?). Таким чином, проведена жорсткість алгоритму та повна паралелізація розрахунків. На щастя, платформа .net була дивно добре для цього виду задоволення.
Другий етап – це генерація плитки. Tile - це невелика картина 256x256 пікселів, яка складається з зображення карти на Google Maps, yandex та інших послуг. В цілому нічого складного - генерується велика картина, нарізаний на квадрати потрібного розміру, бізнес як це. Але ці фотографії майже 30 млн. Навіть тільки копіювання або видалення каталогу з плиткою в вікнах займає два дні. І заливають їх на хостинг – окрема проблема.
Третій крок - викрутити двигун Google Maps, покласти все разом і зробити це показати карту. Тут немає нічого складного, хоча були деякі труднощі з проекціями і позицією карти.
Останній етап – вибір хостингу та релізу. Не було пригод. Тепер це все в хмарі Amazon, і це набагато простіше і дешевше, ніж я уявляв.
Все, що я маю досвід і буду раді поділитися ним з повагою громадою. Звісно, в цілому, нічого особливого, є дійсно цікаві проекти і непривабливі рішення на Habra, але ще, я думаю, що багато людей можуть бути зацікавлені в цьому.
Я також вітатиме будь-які ідеї, відгуки, критика - будь-який відгук!
Джерело:
Привіт, кожен!
Я хочу показати вам Інтернет-карту або результат кластеризації більше 350,000 сайтів відповідно до переходу користувачів між ними. Розмір кола визначається відвідуваністю сайту, кольором - національністю, а позиція на мапі - його посилання з іншими сайтами. Якщо два сайти мають стійкий потік користувачів між ними, вони намагаються ближче до одного. Після завершення алгоритму на карті можна спостерігати кластери сайтів (кластерів) об’єднаних загальними користувачами.
Наприклад, якщо ви шукаєте habrahabr.ru, ви можете побачити, що брудні.ru і leprosorium.ru в тій же «сtellation» і навіть далі від livejournal.ru. Це говорить про те, що хто-небудь читає цей текст зараз, ймовірно, відвідує ці сайти (відносний до середнього користувача RuNet).
Ще більш цікавий приклад кластеризації можна побачити в нижній частині карти, між пурпурною Японією і жовтуватою Бразилії: є ціла країна в розмірах, порівнянні з цілою євромережею. Цікаво, що достатня компетентність в цій матерії, в рамках великого кластеру порно можна виділити менші тематичні підкласники.
Для тих, хто цікавиться короткий технічний опис, ласкаво просимо до kata.
Інженерна частина
Весь проект написаний в C# і складається з трьох частин: програми кластеризації, програми для створення плитки та сайту. Кожна частина заслуговує окремого розгляду і, якщо є інтерес, я міг розповісти про них пізніше.
Ініціальні дані були взяті з Alexa, вони є записи про відвідуваність, переходи в потік і внизу трафіку користувачів (потоку – де вони прийшли з, внизустрі – де вони пішли). Після нормалізації ми отримуємо ваговий непрямий графік з 350 тис. вершин і більше 2 млн. ребер.
Розрахунок такого графіка є складним обчислювальним завданням, тому був написаний спеціальний модуль для GPU, але необов'язково. Після розумних оптимізацій, весь розрахунок займає кілька тижнів безперервної роботи потужних, але ще і побутових прасок.
Щоб поставити його просто, робота алгоритму полягає в покроковому русі сайтів на карті відповідно до сил, що діють на них. Багато переходів користувачів – сильна сила намагається наблизити сайти разом; якщо сайти занадто близькі, сила відповідей починає працювати і т.д. Для отримання додаткової інформації див. звіти-архів.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf
Основна проблема була величезною обчислювальною складністю цього алгоритму. Після того, як при вирішенні проблеми «в голові», на кожному кроці потрібно розрахувати надположення сил для кожного майданчика, тобто розрахувати сили для кожної пари сайтів, і є близько 122 мільярдів таких пар (не погано для одного кроку, прямо?). Таким чином, проведена жорсткість алгоритму та повна паралелізація розрахунків. На щастя, платформа .net була дивно добре для цього виду задоволення.
Другий етап – це генерація плитки. Tile - це невелика картина 256x256 пікселів, яка складається з зображення карти на Google Maps, yandex та інших послуг. В цілому нічого складного - генерується велика картина, нарізаний на квадрати потрібного розміру, бізнес як це. Але ці фотографії майже 30 млн. Навіть тільки копіювання або видалення каталогу з плиткою в вікнах займає два дні. І заливають їх на хостинг – окрема проблема.
Третій крок - викрутити двигун Google Maps, покласти все разом і зробити це показати карту. Тут немає нічого складного, хоча були деякі труднощі з проекціями і позицією карти.
Останній етап – вибір хостингу та релізу. Не було пригод. Тепер це все в хмарі Amazon, і це набагато простіше і дешевше, ніж я уявляв.
Все, що я маю досвід і буду раді поділитися ним з повагою громадою. Звісно, в цілому, нічого особливого, є дійсно цікаві проекти і непривабливі рішення на Habra, але ще, я думаю, що багато людей можуть бути зацікавлені в цьому.
Я також вітатиме будь-які ідеї, відгуки, критика - будь-який відгук!
Джерело:
