Работает ли правило шести рукопожатий? Удивителен каждый день! Шесть наихудших рукопожатий в мире.
Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в Facebook пытается подтвердить теорию шести рукопожатий. Для тех кто не в курсе, эта теория заключается в том, что все жители земли в среднем знакомы друг с другом через цепочку из пяти друзей (т.е. шести рукопожатий). Подробнее об истории этой теории можно прочитать в википедии , там же можно узнать о том, что Майкрософт несколько лет назад пыталась подтвердить эту теорию на основе данных о контакт-листах мессенджера MSN - в результате у них получилось 6,6 рукопожатий, что вполне вписывается в теорию.
Очень мне захотелось эту теорию подтвердить самому, используя данные, которые есть под рукой - ВКонтакте. Для претворения моей странной идеи в жизнь надо было решить целый комплекс проблем:
- На каких данных это все расчитывать.
- Где эти данные взять.
- Как эти данные сохранять.
- Каким алгоритмом воспользоваться для расчетов.
Мой взгляд был устремлен на ВКонтакте. Да, он охватывает только Россию и СНГ (причем неравномерно - в одноклассниках, к примеру, публика постарше). Да, там огромное количество ботов. ВКонтакте неидеален, но зато умеет раздавать список друзей в json-формате через запрос к al_friends.php.
Но как эти данные хранить и обрабатывать?
- Можно пойти в лоб и писать сразу в MySQL: паук выплевывает 100 пользователей в секунду, у каждого 130 друзей, итого 13000 вставок в БД в секунду. Цифра не запредельная, но с учетом того, что паук работал на слабом сервере (старый одноядерный атлон), не совсем радужная.
- Можно писать текстовый дамп на диск, а потом всасывать его в базу данных. При таком раскладе база будет весить примерно (4 байта (размер поля user_id) + 4 байта (размер поля friend_id) + 8 байтов на оверхед и индексы) * 80М пользователей вконтакте * 130 друзей = 166Гб. Многовато будет. Причем выборка с такой базы всех друзей пользователя не будет выглядеть как суперэффективный запрос.
- Можно забить на 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). Так что полученный результат можно считать еще одним подтверждением теории шести рукопожатий.
Малкольм Глауделл, канадский журналист и автор книг по популярной психологии и социологии, называет таких людей «объединителями» и утверждает, что большинство социальных связей возможны благодаря ним – людям с очень широким кругом знакомств. Грубо говоря, не любой человек «А» связан с любым другим человеком «Б» через шесть приёмов, а есть несколько объединителей с огромным количеством контактов, которые через небольшое число рукопожатий связаны между собой и с «обычными» людьми вроде пресловутых «А» и «Б». Кстати, в наш век Интернета, когда у многих есть привычка сохранять знакомства с шапочно знакомыми людьми через соцсети, эти цепи рукопожатий могут быть ещё короче.
Вернёмся к нашим предположениям в начале статьи. Знакомство с французским президентом – шутка? Не совсем. Другая шутка о знакомстве любого из нас с английской королевой через пять шагов возникла после проведённого Microsoft анализа данных более 240 миллионов пользователей. Количество выявленных в их исследовании «рукопожатий» между любым «А» и любым «Б» – 6,6. Другой эксперимент – Facebook - определил эту цифру в 4,74.
Австралийский фермер? И снова не шутка. В 2012 году в Columbia Magazine была опубликована статья об исследовании колумбийских учёных, которые предложили добровольцам найти человека в любой точке мира по его имени, месту жительства и профессии с помощью электронной почты. В ходе этого эксперимента австралийский резидент всего через четыре сообщения «нашёл» адресата из Сибири.
Ну ладно, с крестьянином из Никарагуа может так просто и не получиться. В конце концов число рукопожатий, будь то четыре, пять или шесть с половиной, – это среднее количество. Тем не менее сама возможность такого (любого!) знакомства в нашем «тесном» мире, согласитесь, захватывает.
Теория шести рукопожатий означает, что каждый из нас знает любого человека на Земле через пятерых общих знакомых.
Эта теория была выдвинута в 1969 году двумя психологами из Америки: Стенли Милгрэмом и Джеффри Трэверсом. Предложенная ими гипотеза заключалась в том, что каждый человек опосредованно знаком с любым другим жителем планеты через цепочку общих знакомых, в среднем состоящую из пяти человек. Они провели эксперимент в двух городах. Было создано 300 конвертов, которые каждый участник эксперимента должен был передать другому человеку жившему в этом городе. Ограничение заключалось в том, что передавать конверты можно было только знакомым. Из расчетов удалось определить, что каждый конверт прошел через шесть рук. Именно так и родилась теория шести рукопожатий.
Со временем появилась электронная почта, и этот эксперимент повторили социологи Колумбийского университета. Они создали 20 засекреченных человек, до которых должны были дойти письма, тем самым подтверждалось что начальные добровольцы через друзей знают их. Оказалось, что доброволец из Австралии нашел засекреченного человека из Сибири всего за 4 сообщения - это было первое успешное определение засекреченной цели.
Microft так же проводил подобный эксперимент. На сей раз в их распоряжении было 240 миллионов человек, и каждый из них знал любого человека через 6,6 ступеней. По этому поводу даже существует распространенная шутка о том, что каждый из нас знает английскую королеву через 5 знакомых.
Так же всем известная социальная сеть Вконтакте создала приложение “Цепочка друзей - теория шести рукопожатий“. Но аудитория в контакте не весь мир, а лишь страны СНГ, поэтому эту теорию можно назвать как “теория 3-5 рукопожатий”, что означает что каждый участник Контакта знает другого через 3-5 общих знакомых.
Но лично не устанавливал себе это приложение. Я редко бываю ВКонтакте, и как правило захожу туда если надо написать кому-то сообщение или скачать музыку или видео, для этого я пользуюсь программой лови в контакте.
Стоит заметить, что цепочки длиннее 6 человек практически отсутствуют, что еще раз подтверждает теорию шести рукопожатий!
Графический вид теории шести рукопожатий
Миланский университет и социальная сеть Facebook также провели совместное исследование теории шести рукопожатий, взяв за основу данные социального графа Facebook. Было установлено, что двух любых пользователей Facebook отделяет 4,74 уровня связи. Для США количество звеньев составило 4,37.
Между прочим, на основе теории «тесного мира» возникло и множество популярных в США игр. Например, учёные играют в «Число Эрдёша». Венгерский математик Пол Эрдёш — один из крупных учёных ХХ века, имеющий огромное число работ, написанных в соавторстве. Нужно найти кратчайшую цепочку от него до другого известного учёного. Если он написал какую-нибудь работу вместе с Эрдёшом, то число Эрдёша у него равно единице. Если в соавторстве с тем, кто, в свою очередь, написал что-нибудь с Полом Эрдёшом, то это число у него равняется двум и т. д. Почти все нобелевские лауреаты имеют небольшие числа Эрдёша.
Пользователи «ВКонтакте» проверяют теорию 6 рукопожатий
По просторам сайта «ВКонтакте» гуляет забавная игра. «Теория 6 рукопожатий» находит своё реальное подтверждение. Причём, можно быть знакомым с человеком через 6 рукопожатий, даже если он живёт в другой стране.
Для проверки нужно сделать следующее:
Напишите в поиске людей любое имя и фамилию, какие придут в голову. Из полученного списка выберите человека не из вашего города, а ещё лучше подальше, чтобы было интереснее.
Теперь зайдите в его список друзей и перейдите на страницу первого в списке (незнакомые друзья ранжируются по рейтингу). На странице этого человека откройте список друзей и снова щёлкните на первого друга. Делайте так несколько раз и считайте «рукопожатия». В среднем бывает 3-5.
Лично я сам проэкспериментировал и был удивлен результатами. В первом случае у меня цепочка получилась всего в 2 "рукопожатия", во втором - в 4, а самая длинная получилась ровно 6. Удивительно, но теория работает!
Правда были случаи, когда рукопожатий было 7 или даже 9, но их в разы меньше.
Попробуйте, и вы будете удивлены))
Каждый из нас когда-либо задумывался о том, как огромен и необъятен мир, о том, как много на Земле абсолютно разных людей. Несмотря на различия в возрасте, поле, цвете кожи, все люди связаны. Порой можно даже удивиться, насколько много у каждого друзей и просто знакомых.
Вероятно, глубоко задумавшись об этом, венгерский писатель-фантаст Фридеша Каринти в 1929 году написал рассказ «Звенья цепи». Именно в нем впервые представлена теория шести рукопожатий. Он предлагает провести необычный эксперимент и доказать, что каждый человек может связаться с абсолютно любым жителем планеты через знакомых друг другу людей и, при этом, их число не превысит шести.
В 1969 году теория рукопожатий была окончательно сформирована американскими социологами Джеффри Трэверсом и Стэнли Милгрэмом. Их гипотеза состояла в том, что каждый человек знаком с любым другим через цепочку знакомых, которая состоит в среднем из пяти человек. Был проведен интересный эксперимент. Жителям одного небольшого американского городка раздали 300 конвертов. Они должны были переслать их конкретному адресату через своих знакомых. Было доставлено всего 60 писем. После проведения некоторых подсчетов и анализов, специалисты пришли к выводу, что каждое письмо прошло в среднем через пять человек. Таким образом, теория шести рукопожатий была доказана.
Научно-технический прогресс позволил ученым из повторить с помощью электронной почты. Было создано двадцать секретных адресатов. Участникам открыли их имена, фамилии, места жительства, образование, Тысячам добровольцев было предложено найти их через друзей и знакомых. Первым, кто справился успешно, стал житель Австралии, который нашел засекреченный адрес в Сибири через четырех знакомых.
Всемирно известную корпорацию Microsoft также заинтересовала теория шести рукопожатий. На ее проверку у них ушло около двух лет. За это время было проанализировано 242 720 596 сообщений от пользователей. В результате было установлено, что любой из 240 миллионов пользователей данного сервиса может найти другого через 6,6 человек в среднем.
Теория 6 рукопожатий легла в основу большого числа популярных игр. К примеру, многие в том числе и с мировыми именами, играют в «Число Эрдёша». Такое название было дано в честь венгерского математика Пола Эрдёша. Он написал огромное количество работ, в том числе и в соавторстве. Суть игры состоит в следующем: если ученый имеет одну работу, которая написаны вместе с Эрдёшем, то получает один балл; если в соавторстве с ученым, который писал с Эрдёшем, то два балла. Как известно, все лауреаты Нобелевской премии имеют большие числа Эрдёша.
Популярная в странах СНГ социальная сеть ВКонтакте запустила приложение «Цепочка друзей — теория шести рукопожатий». Оно позволяет составлять цепочки знакомств среди пользователей сети. В связи с тем, что аудитория ВКонтакте несколько ограниченна, результаты получаются немного иные. В основном цепочки имеют размер от трех до четырех человек. Интересным фактом является то, что цепочек длиннее шести человек не встречается. Это, в свою очередь, подтверждает первоначальную теорию.
Кроме различных экспериментов, теория рукопожатий нашла отражение и в кинематографе. Она легла в основу сюжета таких известных фильмов, как «Елки», «Реальная любовь».
Благодаря всевозможным исследованиям ученых и социологов появилась шутка, что каждый из нас через пять человек знаком с
Сегодня Интернет стер все границы, и каждый день миллионы людей из разных стран и континентов знакомятся друг с другом, хотя в реальной жизни вряд ли когда-нибудь могли бы увидеться. Однако немногие знают, что которую сегодня скорее можно было бы назвать теорией шести кликов, была описана в фантастическом рассказе Фридеша Каринти задолго до начала компьютерной эры.
Правда ли, что мир тесен?
Наверное, никто не сможет сказать точно, когда появилось это присловье. Скорее всего, это было во времена, когда люди крайне редко выезжали за пределы своей страны и даже населенного пункта, поэтому так или иначе были знакомы или становились родственниками через кумовство и браки. Со временем границы становились, как сказали бы сегодня, прозрачнее, и люди начинали уезжать в поисках лучшей доли подальше от насиженных мест. Но и там они, к своему удивлению, встречали земляков или людей, которые были знакомы с теми, с кем они когда-либо имели дело.
"Звенья цепи"
Многие произведения литературы, относящиеся к жанру фантастики, со временем были признаны пророческими. Как уже было сказано, впервые идея, оформившаяся позднее как теория 6 рукопожатий, стала достоянием общественности в 1929 году благодаря книге венгерского писателя Фридеша Каринти "Звенья цепи". В ней он активно продвигал мысль, что благодаря таким средствам коммуникации, как телефон и телеграф, а также авиации, жители Земли стали "гораздо ближе друг к другу, чем когда-либо прежде". Надо сказать, что на тот момент население планеты составляло "всего" полтора миллиарда человек. Однако идея о том, что любой из них, зная не более 5 человек, каждый из которых являлся бы приятелем предыдущего, сможет связаться со случайным жителем планеты, показалась читателям шуткой, и никто не стал проверять ее истинность.
Теория 6 рукопожатий
Проблемы общения и социальных связей во все времена были в центре внимания психологов. В 1969 году двое из них, Джеффри Трэверс и Стэнли Милгрэм, выдвинули гипотезу, впоследствии получившую название "правило 6 рукопожатий". Согласно ей каждый из нас является опосредованно знакомым с любым другим жителем нашей планеты через довольно короткую цепочку общих знакомых, которая в среднем состоит из пяти человек.
Экспериментальная основа
Первый вопрос, возникший после того, как была предложена теория 6 рукопожатий — как проверить ее истинность. Надо сказать, что еще за два года до опубликования своей работы Стэнли Милгрэм провел исследование, имевшее целью определить длину цепочки, соединяющей жителей нашей планеты. Оно получило название "Мир тесен", и в качестве математической модели была выбрана сильно-связная сеть, характеризуемая короткими путями между двумя случайными вершинами графа. Для численной реализации эксперимента Милгрэм разработал специальный алгоритм для подсчета количества связей между двумя объектами. Кроме того, по ходу исследования его авторами постоянно фиксировалась длина пути от одного человека до другого.
Ход эксперимента
В качестве стартовых площадок для исследования ученые выбрали города Омаха и Уичито, расположенные в штатах Небраска и Канзас, а в качестве адресата — одного из жителей Бостона. Такое решение было обосновано тем, что эти населенные пункты не только были удалены друг от друга географически: между ними была настоящая пропасть в плане уровня жизни и образования.
В момент старта эксперимента, который впоследствии позволил сформулировать закон 6 рукопожатий, случайно выбранным жителям Омаха и Уичито были отправлены письма, предлагающие принять участие в научном исследовании. В случае согласия они должны были записать на присланном бланке свое имя и, если были лично знакомы с тем бостонцем, имя которого им назвали, переслать письмо ему, в противном случае - тому из своих знакомых, который вероятнее других мог его знать лично.
Результат
Главным препятствием к получению точной информации в результате данного эксперимента стало то, что многие из тех, к кому приходили письма на различных этапах его проведения, не соглашались передавать их дальше. Всего ученые отправили 296 конвертов с просьбой об участии, из которых до бостонца дошли только 64. При этом средняя длина каждой цепочки, достигшей цели, составила 5,5-6 человек. Был установлен и еще один интересный факт: некоторые участники выбирали "промежуточное" звено данной цепи, руководствуясь тем, кто из их знакомых живет ближе других к Бостону. Причем именно в таких случаях письма и не достигали до цели.
На основе полученных данных спустя два года была сформулирована теория 6 рукопожатий, которая с развитием Интернета получила новый смысл.
Шесть электронных писем
В 2003 году группа ученых решила провести эксперимент в стиле "Мир тесен", но с учетом современных реалий. Поэтому вместо обычных были использованы 24163 электронных письма, значительно расширен круг участников и число конечных адресатов. Интересно, что итог эксперимента вновь показал, что даже с учетом отказов в участии или, как их назвали, “истощений”, на разных участках пересылки сообщений, средняя длина цепочки оказалась равна шести.
Теорема 6 рукопожатий: прикладное значение
В информатике данные, полученные в ходе эксперимента "Мир тесен", и его концепция используется для развития однорангового безопасного протокола, а также разработки новых алгоритмов эффективного поиска в сетях связи любых видов, маршрутизации в глобальной сети Интернет и специальных беспроводных сетях.
Граф "Мир тесен"
Интересно, что, казалось бы, чисто социологическое исследование положило начало развитию целого направления в теории графов. В частности, было введено новое понятие — граф “Мир тесен”, обладающий следующими свойствами: две его произвольные вершины с большой вероятностью не являются смежными, но одна из них достижима из другой посредством небольшого числа переходов через другие вершины. Иначе говоря, граф “Мир тесен” представляет собой сеть, в которой типичное расстояние между двумя любыми вершинами или количество шагов, которые необходимы, чтобы достичь одну из другой, увеличивается пропорционально натуральному логарифму от числа вершин в сети. Причем доказано, что социальные сети, вики-сайты, связность сети Интернет, генные сети и др. довольно хорошо описываются графом “Мир тесен”.
Подтверждение правила 6 рукопожатий в социальных сетях
В 2011 году к экспериментам, призванным подтвердить теорию 6 рукопожатий, подключилась знаменитая социальная сеть сети Facebook, которая провела совместное исследование с Миланским университетом. Согласно его результатам количество “звеньев цепи” в среде пользователей виртуального мира, созданного Марком Цукербергом, даже меньше 6-ти и в среднем равно 4,74. Как написано в отчете для прессы, любой житель сибирской тундры, зарегистрированный в Facebook, связан с пользованием той же сети из перуанских джунглей через “друзей друзей”.
Нашлись энтузиасты, которые проверили, действует ли теория "6 рукопожатий" ВКонтакте. По их данным, между двумя случайными пользователями этой российской сети в среднем всего 5,65 звеньев, или 6,65 “рукопожатий”. Таким образом, идеи Стэнли Милгрэма оказались верны и в данном случае.
Нетворкинг
Принцип "6 рукопожатий" лег в основу нового понятия. Речь идет о нетворкинге, который определяется как профессиональная или общественная деятельность, имеющая целью максимально эффективно решать поставленные задачи, пользуясь помощью друзей и знакомых.
Критика
Теория "6 рукопожатий" не раз становилась мишенью для критики. Во-первых, потому, что, как уже было сказано, многие цепочки прерывались, так как очередное “звено” эксперимента не хотело ее продолжать. Во-вторых, если речь идет о проведении опыта в социальных сетях, неизвестно, насколько корректно называть знакомыми всех людей, которые внесены в список друзей.
Теперь вы знакомы с правилом шести рукопожатий и сможете сами проверить его правдивость на своем любимом ресурсе.