Правило 10 рукопожатий: «ВКонтакте» запустила приложение для проверки теории шести рукопожатий

еще одно подтверждение / Хабр

Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в Facebook пытается подтвердить теорию шести рукопожатий. Для тех кто не в курсе, эта теория заключается в том, что все жители земли в среднем знакомы друг с другом через цепочку из пяти друзей (т.е. шести рукопожатий). Подробнее об истории этой теории можно прочитать в википедии, там же можно узнать о том, что Майкрософт несколько лет назад пыталась подтвердить эту теорию на основе данных о контакт-листах мессенджера MSN — в результате у них получилось 6,6 рукопожатий, что вполне вписывается в теорию.

Очень мне захотелось эту теорию подтвердить самому, используя данные, которые есть под рукой — ВКонтакте. Для претворения моей странной идеи в жизнь надо было решить целый комплекс проблем:

1. На каких данных это все расчитывать.
2. Где эти данные взять.
3. Как эти данные сохранять.
4. Каким алгоритмом воспользоваться для расчетов.

С засильем социальных сетей в современной жизни вопрос о том, где взять данные о социальных связях, не такой уж сложный. Конечно, было бы прекрасно взять данные о друзьях из Facebook, ведь он охватывает весь мир, да и народа там много. Но через публичный API вытянуть список друзей для любого человека я не могу, а парсить страничку — не самый эффективный вариант, ибо Facebook список друзей выплевывает в виде dhtml, примерно по 1кб данных на одного друга, итого 400М человек * 130 друзей в среднем * 1кб = 52 Тб трафика. Такой объем трафика малость не вписывался в стремившийся к нулю бюджет исследования, и вариант с Facebook был откинут.

Мой взгляд был устремлен на ВКонтакте. Да, он охватывает только Россию и СНГ (причем неравномерно — в одноклассниках, к примеру, публика постарше). Да, там огромное количество ботов. ВКонтакте неидеален, но зато умеет раздавать список друзей в json-формате через запрос к al_friends.php.

Но как эти данные хранить и обрабатывать?

1. Можно пойти в лоб и писать сразу в MySQL: паук выплевывает 100 пользователей в секунду, у каждого 130 друзей, итого 13000 вставок в БД в секунду. Цифра не запредельная, но с учетом того, что паук работал на слабом сервере (старый одноядерный атлон), не совсем радужная.
2. Можно писать текстовый дамп на диск, а потом всасывать его в базу данных. При таком раскладе база будет весить примерно (4 байта (размер поля user_id) + 4 байта (размер поля friend_id) + 8 байтов на оверхед и индексы) * 80М пользователей вконтакте * 130 друзей = 166Гб. Многовато будет. Причем выборка с такой базы всех друзей пользователя не будет выглядеть как суперэффективный запрос.
3. Можно забить на MySQL и использовать какое-нибудь hash-value хранилище. В него писать пару «user_id array(friend_id friend_id …)», таким макаром база сдуется раза в четыре и всех друзей будет выбирать одним обращением к диску. В качестве хранилища изначально был выбран Kyoto Cabinet, но из-за каких-то странных аномалий в производительности на большой базе состоялся переезд на гугловый LevelDB.

Спустя трое суток и полтора терабайта трафика база друзей была получена (между прочим, всего лишь 22Гб). И тут возникает самый интересный вопрос: как же считать дистанцию между пользователями?

1. Алгоритм Флойда-Уоршелла, позволил бы рассчитать дистанции от всех пользователей ко всем. Чудесный алгоритм, но у него есть неприятное требование памяти — необходимо хранить квадратную матрицу user_id/user_id, которая бы занимала 1 байт * 80М пользователей * 80М пользователей = 6400 Тб. Совсем многовато.
2. Алгоритм Дейкстры, позволил бы найти дистанции от одного пользователя до всех остальных сразу. Существует довольно много эффективных его реализаций, одна из которых и была ради эксперимента использована. Алгоритм чудесно работал на 1% синтетическом сэмпле всей базы, но при запуске уже на среднем 10% семпле базы начинал жестоко тормозить в довольно неожиданном месте — обход большого дерева друзей постоянно лазил в случайные места памяти и ловил почти 100% CACHE_MISS и без того слабого процессора. Говоря человеческим языком, данные не помещались в кэш процессора, и тут начинались феерические тормоза.
3. Двунаправленный поиск. Да, не самый элегантный в мире алгоритм, зато простой как таблица умножения. Позволяет найти кратчайшую дистанцию между двумя пользователями. Реализация его писалась с использованием битовых полей, которые элегантно упихивались в кэш процессора, в результате дистанцию между двумя людьми алгоритм находил где-то за полминуты.

При решении ресурсоемких задач я люблю делать такие их реализации, которые будут нормально работать даже на моем скромном нетбуке, а потом уже включать тяжелую артиллерию. В качестве тяжелой артиллерии использовался скромный сервер с двумя шестиядерными ксеонами X5650 и 32Гб памяти. На нем дистанция считалась уже за 10 секунд на поток. С учетом распараллеливания, за минуту рассчитывались дистанции между 144 парами пользователей.

Далее начались странности с данными. Почти 50% всех пользователей с ненулевым количеством друзей входило в абсолютно независимые кластеры, в которых нет внешних связей (или таких связей полторы штуки на весь кластер). Грубо говоря, 50 человек зафрендили друг друга и больше никого. Довольно странное поведение, не так ли? Да, возможно, это сектанты и им религия запрещает френдить ВКонтакте не-членов секты. Но врядли, скорее всего это боты.

Выкинув ботов, отловленных подобным неожиданными способом, было проанализировано 6773 пары пользователей и получился очень интересный результат:

На гистограмме по оси x — длина найденной кратчайшей цепочки друзей, а по оси y — вероятность ее найти в процентах.

Таком образом, в среднем, между двумя случайными пользователями ВКонтакте есть 5.65 друзей (т.е. 6.65 рукопожатий). Эта цифра вполне вписывается в изначально проверяемую теорию, к тому же довольно точно совпадает с результатом, полученным в Microsoft (у них вышло 6.6). Так что полученный результат можно считать еще одним подтверждением теории шести рукопожатий.

Теорию шести рукопожатий сократили до пяти

Архив rb.ru 23 ноября 2011

Архив rb.

ru 23 ноября 2011

Мария Грибцова

Автор издания RB (Архив)

Мария Грибцова

Количество связей между 700 млн пользователей Facebook равно 69 млрд

Мария Грибцова

Исследователи из Миланского университета совместно со специалистами соцсети Facebook выяснили, что двое любых людей в мире могут быть знакомы через 4,47 «рукопожатия». Хотя ранее считалось, что этот показатель равен шести.

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

Таким образом гипотеза о шести рукопожатий сократилась до пяти.

 

В процессе исследований учеными из лаборатории веб-алгоритмов был разработан специальный алгортим «социальный граф», с помощью которого были проанализированы связи между более чем 700 млн пользователей социальной сети Facebook. Количество связей между ними составило 69 миллиардов. В исследовании участвовали только активные пользователи — те, кто хотя бы раз логинился в мае 2011 года. 

Согласно полученным данным, средняя длина цепочки между двумя любыми людьми составляет 4,74 «рукопожатия». При этом ученые выяснили, что если брать ограниченные локации, например связи между людьми в пределах одной страны, то цепочка окажется еще короче, в среднем — три посредника или четыре рукопожатия. Эту теорию подтвердил пример Италии.

Исходя из официальной статистики соцсети, каждый человек имеет около 130 друзей — около 50% пользователей имеют более 100 друзей, 20% — менее 25 друзей, а 10% — менее 10 друзей.

 

Теорию о «шести рукопожатиях» впервые высказал в 1929 году фантаст и журналист из Венгрии Фридеш Каринти. Он утверждал, что цепочка из пяти человек может связать двух абсолютно незнакомых друг с другом людей. Это предположение спустя сорок лет было проверено опытным путем Стенли Милгремом, который уточнил показатель до 5,2. Суть эксперимента Милгрэма заключалась в том, что добровольцам предлагалось послать письмо некоторому неизвестному человеку через знакомых с просьбой передать послание дальше. После этого теория получила широкую известность и статус гипотезы.

 

В августе 2011 года Facebook вместе с Yahoo начали масштабный эксперимент Small World, который длится до сих пор. Его участники делают то же самое, что и участники эксперимента Милгрэма, только при помощи возможностей социальной сети. 

Эксперты из Microsoft также проверяли эту теорию в 2008 году, проанализировав связи между 240 млн пользователей. Эксперты выяснили, что среднее число связей между двумя любыми пользователями составляет 6,6 «рукопожатия».

• Facebook
• Microsoft
• Yahoo!

Нашли опечатку? Выделите текст и нажмите Ctrl + Enter

Материалы по теме

1. 1 От Tesla до Google: 14 крупных компаний из США, основанных мигрантами
2. 2 53 стартапа, которые купила Yahoo. Что с ними стало
3. 3 Цифры дня. Никто не хочет давать пиратам деньги
4. 4 Как конкуренция с Google меняет бизнес корпораций
5. 5 Битва капитализаций: Apple стоит как 12 «Газпромов»

ВОЗМОЖНОСТИ

10 мая 2023

«Покажи Москву!»

10 мая 2023

«Финам Trade API»

10 мая 2023

Aeroclub Challenge 2023

Все ВОЗМОЖНОСТИ

Новости

Создатель ChatGPT представил криптокошелек, работающий без комиссий

Новости

Верховный суд взыскал с «2ГИС» расходы по делу о негативном отзыве

Архив rb. ru

Итоги Второй мировой войны глазами граждан разных стран

Колонки

Пять шагов для построения инхаус-команды по маркетингу

Списки и рейтинги

Самые интересные нейросети: топ-14 сервисов для раскрашивания изображений, генерации текста и не только

Рукопожатие | NZ Maths

Цель

Это упражнение по решению задач сосредоточено на алгебре.

Цели достижения

NA3-8: соедините элементы последовательных шаблонов с их порядковым номером и используйте таблицы, графики и диаграммы, чтобы найти отношения между последовательными элементами числовых и пространственных шаблонов.

Разработка АО и другие учебные ресурсы

Студенческая деятельность

 

Шесть деловых людей встречаются за обедом и обмениваются рукопожатием.

Сколько рукопожатий?

 

Конкретные результаты обучения

• Опишите словами правила шаблона.

• Определите структуру треугольных чисел.

• Разработайте и используйте стратегии решения проблем для математического исследования ситуаций (систематический список, рисование картинок, использование оборудования).

Описание математики

Математика, используемая в этой задаче, зависит от подхода, используемого для ее решения. Если учащиеся ищут закономерности, начиная с более простых случаев (2 человека и т. д.), задача связана с треугольными числами.

Необходимые материалы

• Копи-мастер задачи (маори)
• Копи-мастер задачи (английский)

Деятельность

Проблема

Шесть деловых людей встречаются за обедом и обмениваются рукопожатием. Сколько рукопожатий?

Последовательность обучения

1. Представьте задачу, предложив трем ученикам разыграть людей, которые встречаются и обмениваются рукопожатием.
2. Подсчитайте и запишите количество рукопожатий. Обсудите другие способы убедить других в том, что рукопожатий было 3 (например, нарисуйте рисунок).
3. Поставьте задачу для работы учащихся в парах или малых группах.
4. Придумайте способы решения более крупной проблемы (разыграйте ее, составьте список и найдите закономерность). Перечислите их на доске, чтобы студенты могли их обдумать.
5. Во время работы учащиеся задают вопросы, которые фокусируют их мышление на систематической работе и поиске закономерностей.
   Как вы отслеживаете рукопожатия? (диаграмма, список)
   Как вы думаете, сколько рукопожатий было бы, если бы вы добавили еще одного человека?
   Что вы заметили в отношении количества рукопожатий и количества людей?
   Как бы вы могли записать свою работу, чтобы найти закономерность?
6. Делитесь результатами.

Добавочный номер

Сколько рукопожатий будет на собрании, если люди приходят парами и пожимают руки всем, кроме своих партнеров.

Решение

Если два человека обмениваются рукопожатием, то это одно рукопожатие.
Если три человека обмениваются рукопожатиями, то получается 3 рукопожатия.
Если четыре человека обмениваются рукопожатиями, то 3 + 3 = 6 рукопожатий.
Если пять человек пожимают друг другу руки, то есть еще 4 рукопожатия, поэтому 6 + 4 = 10.
На 6 человек приходится еще 5 рукопожатий, поэтому 10 + 5 = 15. руки со всеми остальными. Если вас 6 человек, то каждому нужно сделать по 5 рукопожатий. Но каждый раз, когда происходит рукопожатие, участвуют 2 человека. Это означает, что вам нужно только ½ (6 x 5) = 15,

Решение для расширения

6 человек = 12 рукопожатий (15 – 3 = 12, вычесть 3 для рукопожатий между партнерами).

Приложения

Добавить в план

Третий уровень

Рукопожатий

Возраст от 11 до 14 лет

Уровень сложности

Студент из замка Мирнс сделал полезная связь с другой проблемой, опубликованной в этом месяц:

Это похоже на определение количества строк в Mystic Rose.

Допустим, есть n человек. Первый человек пожимает руку другие n-1 человек.
Затем второй человек пожимает руку другому n-2 люди.
И так далее, пока (n-1)-й человек не пожмет руку n-му человек.

Итак, количество рукопожатий равно (n-1) + (n-2)… + 3 + 2 + 1, что равно (n-1)(n)/2.

Другой способ рассмотрения состоит в том, что каждый человек имеет в общей сложности n-1 рукопожатий, и есть n человек, поэтому будет (n-1)(n) рукопожатия, но это включает каждое рукопожатие дважды (1 и 2, 2 и 1) поэтому деление на 2 дает правильный ответ.

Асваат из Garden International Школа в Куала-Лумпуре, Малайзия, упомянула, что метод решение этой проблемы, связанной с метод, которым пользовался Гаусс, когда он был еще молодой студент.

Джо из начальной школы Хоув Парк также замечены связи с другой работой:

Если встретились, например, 10 математиков, то первый составит 9 рукопожатий, второй делает 8, третий делает 7 и так далее, пока десятый находит, что он уже со всеми поздоровался и так больше не делает.

Это дает 9+8+7+6+5+4+3+2+1+0 рукопожатий, а это 45.

Но посмотрите на последовательность… это 9-й треугольник число.
(см. рисунок Triangle Numbers и/или Clever Carl)

Формула для T-го треугольного числа: T(T+1)/2
В задаче о рукопожатии, если есть n человек, то число рукопожатий эквивалентно (n-1)-му треугольному числу.

Подставляя T = n-1 в формулу для треугольных чисел, мы можем вывести формулу для количества рукопожатий между n человек:

Количество рукопожатий = (n-1)(n)/2

Джейми из Garden International Школа согласилась и использовала это понимание, чтобы исправить ошибку Сэма. рассуждение:

Метод Сэма неверен, потому что он не разделил ответ на 2. Если вы не разделите его на 2, вы будете считать количество рукопожатия между парами математиков дважды.

Если встречаются 20 математиков:
20 x 19 = 380
380 / 2 = 190 (общее количество рукопожатий)

Если встречается 161 математик:
161 x 160 = 25760
25760 / 2 = 12880 (общее количество рукопожатий)

Может ли быть ровно 4851 рукопожатие на собрании, где все пожимают друг другу руки?

Мы знаем, что 4851 рукопожатие — это между 20 математиками и 160 математики. Итак, начнем с проверки 100 математики.
Общее количество рукопожатий = 100 x 99 / 2 = 4950

Это слишком много, так что теперь я попробую 99 математиков.
Общее количество рукопожатий = 99 x 98 / 2 = 4851
Следовательно, может быть ровно 4851 рукопожатие, когда 99 встречаются математики.

Может ли быть ровно 6214 рукопожатий на собрании, где все пожимают друг другу руки?

Начнем с проверки 112 математиков.
Общее количество рукопожатий = 112 x 111/ 2 = 6216

Это слишком много, так что теперь я попробую 111 математиков.
Общее количество рукопожатий = 111 x 110 / 2 = 6105
Это слишком мало, поэтому не может быть ровно 6214 рукопожатий.

Джозеф из Bradon Forest School и Табита из школы Норвуд использовала аналогичные рассуждения: 92 -99 = 97024$

Так что да, если 99$ математиков встретятся, то будет 4851$ рукопожатия

$6214$ рукопожатия?
Нет, ближайшее треугольное число $6216$, а $6214$ не является число треугольника

$3655$ рукопожатия?
Да, $86$ Математики

$7626$ рукопожатий?
Да, $124$ Математики

$8656$ рукопожатия?
Нет, ближайшее треугольное число $8646$, а $8656$ не является номер треугольника.