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

Теория шести рукопожатий: еще одно подтверждение

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

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

Мой взгляд был устремлен на ВКонтакте. Да, он охватывает только Россию и СНГ (причем неравномерно — в одноклассниках, к примеру, публика постарше). Да, там огромное количество ботов. ВКонтакте неидеален, но зато умеет раздавать список друзей в 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.

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

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

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

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

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

Все мы — близкие люди: как работает теория шести рукопожатий?

Здорово было бы быть лично знакомым с любимым писателем или музыкантом. А с каким-нибудь высокопоставленным лицом — например, королевой Великобритании? Вы скажите, что это невозможно, но в научном сообществе уже давно появилась теория, доказывающая обратное. Она называется — теория шести рукопожатий.

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

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

Первым предположил, что любые два человека связаны последовательной цепью связей, венгерский писатель Фридеш Каринти. Свою идею он описал в рассказе «Звенья цепи» 1929 года.

В нем шла речь о неком мысленно игре-эксперименте, доказывающим, что, на самом деле, люди намного ближе друг к другу. Назывался любой известный или неизвестный человек из 1,5 млрд, проживавших на Земле в XX веке. Игроку из книги нужно было построить цепочку не более чем из 5 звеньев, которые связывали бы его с загаданным человеком.

Как это выглядит в теории?

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

В итоге получилось, что игроку из книги понадобилось только два «рукопожатия», чтобы познакомиться с королем Швеции.

Есть ли подтверждения теории в реальной практике?

Теория без реальных доказательств остается лишь набором идей — не более того. Эксперименты для подтверждения идеи о «шести рукопожатиях» проводились много раз.

Так, автором первого эксперимента в 1967 стал американский психолог Стэнли Милгрэм. Он получил название «Тесный мир».

Для эксперимента случайным образом выбрали 300 человек из двух городов в разных штатах Америки. Им нужно было отправить письмо некому брокеру в третий город. Адрес получателя не был известен, но участники могли попробовать послать письмо через знакомых, которые теоретически могли знать брокера. Каждый человек, которому приходило письмо, перед тем, как отправить его далее, должен был подписать свое имя.

В результате этого эксперимента выявили, что среднее число людей, которым приходило письмо, прежде чем дойти до брокера — 5 человек или 6 «рукопожатий». В последующие годы проводился еще ряд подобных экспериментов — все они подтвердили гипотезу.

В чем заключается «слабость» теории?

Главное слабое место теории шести рукопожатий заключается в том, что её смысл немного исказился из-за ее большой популярности. Многие понимают, что ее так: любой человек знаком с другим через шесть рукопожатий. Но шесть — это лишь средняя длина цепочки, которая в реальности может состоять и из 10, и даже из 15 «рукопожатий».

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

К тому же, само наличие этих различных групп и соответственно их границ становится проблемой для «проникания» в них новым участникам. Не смотря на развитие связей благодаря Интернету и изменению мировоззрения людей, в мире все еще существуют и крайне изолированные группы.

И даже сами эксперименты, которые проводились для подтверждения теории, не совсем идеальны. Дело в том, что многие из писем просто потерялись по пути к тому или иному «звену». Поэтому доказательность таких исследований можно поставить под сомнение.

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

Впервые о теории шести рукопожатий мир узнал в 30-х годах прошлого века. Она была подробно описана в фантастическом рассказе Фридеша Каринти «Звенья цепи». В основе сюжета лежал эксперимент, который доказал, что все жители планеты знакомы друг с другом максимум через 5 человек. Этот феномен стал интересен социологам, и в 1969 году теория была окончательно сформирована. Чтобы подтвердить гипотезу американские социологи Джеффри Трэверс и Стэнли Милгрэм раздали жителям небольшого города 300 конвертов. Цель была проста: используя только собственные контакты доставить письмо адресату. 60 писем дошли до нужного адреса, а длина пути каждого письма не превысила 5 человек. Суть эксперимента заключалась в следующем: если испытуемый не знал адресата, то требовалось отправить письмо человеку, который, скорее всего с ним знаком. Возможно, организаторы не учли расходы на марки, потому из 300 писем дошло всего 60.

Позднее эксперимент провели повторно, но уже с использованием современных средств коммуникации. Всего было создано 20 секретных адресов, а добровольцам предложили найти этих людей. Удивительно, но первым справился житель Австралии, который отыскал нужный адрес всего через четырех знакомых. И этот адрес оказался не на соседней улице и даже не в соседнем городе, а в Сибири!

Microsoft подошел к эксперименту с размахом

Компания Microsoft задействовала все необходимые ресурсы, потратила 2 года, в течение которых специалисты проанализировали почти 250 млн. сообщений и выявили взаимосвязи. Да, и опять все сошлось – любой пользователь сервиса мог найти другого через 6,6 человек в среднем.

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

Эксперимент в социальных сетях

С приходом эпохи социальных сетей эксперимент повторили и в них. Наверное, каждый из нас замечал, что принимая приглашение в друзья от незнакомого человека, мы видим одного или двух общих друзей. Удивительно, но эти люди связывали вас долгое время в реальной или в виртуальной жизни и фактически вы были знакомы еще задолго до того момента, как стали общаться в соцсетях. Facebook, являясь на сегодня самой широкой социальной сетью, популярной во всем мире, провел свое исследование совместно с Миланским университетом. И их вердикт: количество звеньев в человеческой цепочке всего 4,4. Конечно, есть погрешность, так как охват регистрации в сети Facebook составляет не 100%.

Аргументы в пользу опровержения гипотезы

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

Что касается социальных сетей, то в чем-то критики правы: да, не всех своих друзей мы знаем лично, но Интернет позволяет людям стать ближе к другу, заводить виртуальные знакомства и общаться без ограничений. Вы ведь все-таки знакомы, пусть и заочно. Других, более весомых аргументов в пользу опровержения теории, нет.

Игра «ВКонтакте» как способ проверить теорию

Вам даже не нужно устанавливать дополнительных приложений, просто вбейте в поиск любое имя и фамилию. Из списка, который выдаст социальная сеть, выбирайте человека из другого города и начинайте играть. Зайдите в его список друзей, потом зайдите на страницу первого друга в списке и повторите действие. Соцсеть ранжирует друзей по рейтингу, подставляя наверх наиболее вероятных знакомых. В среднем цепочка будет состоять из 3-5 человек. Таким образом, даже скептики могут проверить теорию, не выходя из дома и даже не вставая из-за рабочего стола. Инструкция:

1. Выберите «жертву» (она должна быть реальной).
2. Зайдите на ее страницу.
3. Зайдите на страницу ее первого друга в списке.

Теория работает не всегда

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

Что мешает подтвердить или опровергнуть правило:

• использование разных способов связи, мессендежеров и социальных сетей;
• наличие «закрытых» групп людей на планете;
• невозможность провести эксперимент, задействуя всех жителей Земли.

Нужно принять как должное факт, что наш мир не монолитен и не однороден и состоит из множества слоев, в каждом из которых люди живут по своим правилам. Конечно, с приходом технологий люди стали ближе друг к другу, но для полного подтверждения или опровержения теории нужно 100% участие всех жителей планеты. А это не представляется возможным.

Теория шести рукопожатий в искусстве и кино:

• пьеса «Шесть степеней разделения»;
• кинофильм «Реальная любовь»;
• сериал «Друзья»;
• сериал «Шестеро»;
• кинофильм «Елки».
• Игра «шесть шагов до…»

Киноманам хорошо известна игра «Шесть шагов до Кевина Бэйкона». Цель игры найти цепочку от любого актера до Кевина Бэйкона по принципу «они снимались вместе». Сам Кевин дал идею для этой игры, заявив, что все, кто с ним снимался, снимались со всеми актерами Голливуда. А у математиков есть аналогичное развлечение – игра «Число Эрдеша». Нужно добраться до Эрдеша, используя принцип «кто работал вместе с ним». Такую карту знакомств можно сделать самим и попробовать сыграть. Как минимум это интересная идея для вечера в большой компании друзей.

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