В современном обществе мало найдется людей, которым не знакома теория 6 рукопожатий. Сейчас, когда Интернет стер все границы в общении людей, которые в ином случае, возможно, никогда не встретились бы, эту теорию можно переименовать в правило 6 кликов. Однако немногие знают, что она была описана задолго до своего появления в романе известного в Венгрии писателя Фридеша Каринти. Произведение относилось к жанру фантастики и было опубликовано, когда о теории 6 рукопожатий и ее сути никто еще даже не задумывался.
Теория 6 рукопожатий
Сложно поспорить с утверждением, что мир тесен. Мало кто не сталкивался с ситуацией, когда, находясь в малознакомом обществе, встречали общих знакомых. Никто не задумывается о том, что, по сути, человеческое общество не бесконечно, оно ограничено определенными рамками и в какой-то мере замкнуто. В теории, каждый из нас может быть знаком с любым человеком на земном шаре через общих знакомых или родственников.
Казалось бы, это невозможно. Однако не стоит спешить с выводами. Существует теория 6 рукопожатий, которая заключается в том, что все люди планеты Земля знакомы друг с другом через 5 людей, что составляет 6 уровней связи.
Мир тесен
Несмотря на то что данная теория выглядит фантастической на первый взгляд, она существует уже достаточно давно и не раз находила подтверждение.
Сложно сказать, когда появилось выражение «Мир тесен». Скорее всего, оно берет свое начало еще с тех времен, когда люди жили только на своей территории и практически не выезжали за ее пределы. 
С годами границы расширялись, люди стали сначала ездить друг к другу в гости, а затем и переезжать с насиженных мест в поисках лучшей доли. Однако и в новых местах встречались либо земляки, либо другие люди, с которыми когда-то были знакомы. В крайнем случае в разговорах с новыми людьми практически всегда находились общие знакомые. Именно с тех пор и вошло в наш лексикон данное понятие.
Эксперимент Милгрэма
Правило о тесных связях человечества связано с именами американских психологов Стэнли Милгрэма и Джефри Трэверса, которые в 1969 году предложили понятие, дошедшее до нас как теория 6 рукопожатий. Еще за 2 года до того, как были опубликованы результаты эксперимента, Милгрэм провел исследование, целью которого являлось определение длины цепочки, связывающей людей друг с другом. Назвав его «Мир тесен», ученый разработал особый алгоритм, призванный подсчитать число связей между двумя людьми.
Ход эксперимента
Площадками, где проводился эксперимент Милгрэма, стали города Омаха и Уичито, которые находятся, соответственно, в штатах Небраска и Канзас. Адресатом выбрали жителя Бостона. Ученые объяснили свой выбор тем, что, несмотря на небольшую отдаленность городов друг от друга с точки зрения географии, их жителей разделяла целая пропасть по уровню жизни и образования.
Эксперимент заключался в том, жителям Омахи и Уичито, выбранным случайным образом, отправили письма с приглашением принять участие в научном эксперименте. В том случае, если они соглашались, им следовало написать на бланке, вложенном в письмо, свои данные. Затем это письмо нужно было отправить жителю Бостона, имя которого было указано на конверте. Если адресат знал его лично, он должен был переадресовать письмо ему, а если нет, то надо было отправить послание человеку, который с большей вероятностью его знает. Единственным условием было то, что конверт должен пересылаться только лично знакомому человеку или родственнику.
Итоги эксперимента
Основная трудность исследования заключалось в количестве согласившихся передать письмо дальше. Причем отказ происходил на различных этапах эксперимента. В итоге из 296 писем, отправленных с приглашением участия, конечный адресат получил 64. При этом длина цепочки друзей в среднем составляла 5-6 человек. 
Примечательно, что многие люди, выбирая следующего адресата, исходили из того, кто живет ближе к городу адресата, и как раз в этом случае письмо до конечной цели не доходило. Понадобилось 2 года, чтобы сформулировался закон шести рукопожатий, который с появлением Интернета получил новый смысл.
6 писем по электронной почте
Уже на современном этапе развития общества ученые решили повторить эксперимент Милгрэма с использованием новых технологий. Группа сотрудников Колумбийского университета отправила 24613 электронных письма в разные точки планеты. Смысл исследования заключался в том, что люди, получившие эти письма, должны были найти одного из 20 адресатов. Данные о них были минимальные: имя, фамилия, образование, род деятельности, место жительства. 
Первый успех исследованию принес доброволец из Австралии, который сумел найти своего тайного адресата в Сибири посредством всего 4 сообщений. Таким образом, второй раз была подтверждена теория 6 рукопожатий, как проверить которую было интересно многим социологам.
Подтверждение теории 6 рукопожатий в социальных сетях
В 2011 году правило шести рукопожатий решила проверить самая знаменитая социальная сеть Facebook. Было проведено очередное исследование совместно с Миланским университетом. По его итогам, количество звеньев в человеческой цепи даже меньше 6 и составляет в среднем 4,74. Таким образом, житель планеты, живущий на одной точке земного шара, связан с жителем другой точки посредством «друзей друзей». Единственное условие - регистрация в мировом виртуальном сообществе.
Следующее исследование достоверности теории было проведено среди пользователей российской социальной сети «ВКонтакте». Здесь цепочка друзей насчитывала в среднем 3-4 человека. Удивительно, но не было зафиксировано ни одного превышения цифры 6 в человеческой цепочке. Учитывая территориальное ограничение данного виртуального сообщества, можно утверждать, что результаты исследования также подтверждают теорию 6 рукопожатий.
Критика закона 6 рукопожатий
Как и любое исследование, данное правило не раз подвергалось критике, как со стороны ученых, так и обычных людей. Основной аргумент, на который ссылалась категория сомневающихся, это то, что звенья человеческой цепи не раз прерывались во всех экспериментах. Однако в данном случае сбой в проведении исследования происходил только из-за отказа участников передавать эстафету.
Другой довод, который приводят критики, касается исследования в социальных сетях. В этом случае объектом сомнения выступает отнесение к категории знакомых всех людей, находящихся в списке друзей участников. Это достаточно спорное утверждение, однако все-таки, если кто-то входит в число друзей на вашей страничке в какой-либо социальной сети, значит, какое-то отношение друг к другу вы все-таки имеете.
Таким образом, доводы критиков, высказывающихся против закона 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 рукопожатий" не раз становилась мишенью для критики. Во-первых, потому, что, как уже было сказано, многие цепочки прерывались, так как очередное “звено” эксперимента не хотело ее продолжать. Во-вторых, если речь идет о проведении опыта в социальных сетях, неизвестно, насколько корректно называть знакомыми всех людей, которые внесены в список друзей.
Теперь вы знакомы с правилом шести рукопожатий и сможете сами проверить его правдивость на своем любимом ресурсе.
Здравствуйте, уважаемые читатели! Думаю, многие встречали в социальной сети Facebook сообщение, к примеру, что был найден или утерян кошелёк, и автор хочет проверить правило 6 рукопожатий, которое гласит о том, что мы знакомы абсолютно с любым человеком в этом мире, которого разделяет от нас не более шести уровней связи. Именно этот смысл вносили наши предки, сформировав поговорку о том, что мир тесен.
Немного истории
Чтобы совсем упростить эту схему, объясню на примере. Помните сериал «Во все тяжкие»? Там есть интересный момент, про то, что адвокат знает парня, который знает другого парня, который нужен. Пока ещё не была сформирована теория, об этом впервые написал венгр Каринти Фридеш примерно в 1929 году. Он в шуточной форме в рассказе «Звенья цепи» поделился идеей о том, что все люди на планете связаны между собой, несмотря на то, знамениты они, или из обычного простого рода.
Исследования психологов
В 1969 году психолог Стэнли Милгрэм вместе с коллегой Джеффри Трэверосом решили исследовать эту гипотезу и провести эксперимент. Для этого им требовался совершенно незнакомый человек, которого они решили обнаружить с помощью людей, что могли знать его «шапочных» знакомых и друзей. Случайным образом выбор пал на маклера из Массачучетса, который трудился в Бостоне.
Стэнли и Джеффри, по одним данным, подготовили 160 писем, а по другим – 300, и отправили разным жителям США. В этих письмах была просьба, чтобы они, написав свои контактные данные, переслали конверт какому-то человеку, который может быть близок к указанному маклеру или профессионально, или территориально, допустим, также живя в Бостоне или зная его родных в Массачусетсе.
Важно только, чтобы этот человек, которому они планировали пересылку, был или родственником, или другом, но никак не случайным незнакомцем. И пока конверты совершали своё путешествие, они постепенно обрастали новыми именами. У тех, кто знал об эксперименте, было мнение, что придётся затратить на процесс немало времени, и что письма пройдут, как минимум, через 100 рук, прежде, чем доберутся к указанному человеку. В конце концов, до адресата дошло 60 писем.
И после того, как Милгрэм проанализировал весь список имён, которые указывали люди, участвующие в эксперименте, он понял, что конверты успели побывать в основном у 5-6 человек, после чего уже оказались у маклера. То есть, теория шести рукопожатий действительно подтвердилась. После, Стэнли заметил, что имена трёх людей были указаны больше, чем на 30 конвертах. Один из них – продавец одежды из магазина, рядом с которым проживал маклер, остальные два – его коллеги.
То есть, они обладали наиболее широким кругом знакомств, благодаря чему исследование завершилось благополучно. Позже, Малкольм Глауделл, журналист из Канады придумал термин «объединитель», который характеризует таких личностей, умеющих создавать связи.
Исследования Microsoft
В 2006 году компания Microsoft заинтересовалась этой теорией и решила провести собственное исследование. Благодаря современным технологиям стало возможным вычислить средний показатель математическим путём. Сотрудники корпорации обработали целые миллиарды сообщений, буквально за один месяц, и пришли к выводу, что двоих совершенно разных и незнакомых людей отделяет действительно 6 так называемых рукопожатий. А если быть точнее, то средняя величина была равна 6,6.
Исследования на базе Facebook
Но на этом эксперименты не закончились, взяв за основу известную социальную сеть Facebook, в 2011 году учёные из университета в Милане получили немного иную цифру – всего 4,74. И действительно, с каждым годом круг знакомств у каждого человека на планете увеличивается, потому что стало популярным добавлять в друзья даже тех людей, с которыми раз пересекались где-то, и то, толком не успели познакомиться.
А то, что в редком доме не имеется телефона или компьютера с доступом в интернет позволяет любому общаться даже с тем, кто в данный момент находится на другом краю земного шара. Существует даже сервис, которые помогает установить связь между пользователями и ведутся разработки касательно того, чтобы организовать масштабную коммуникацию между всем населением планеты.
А социологи из университета в Колубмии устроили целый квест. Набрав примерно тысячу добровольцев, они, предоставив всего поверхностную информацию, такую, как ФИО, место жительства и род деятельности 20 человек, попросили их найти при условии, что те будут пользоваться только электронной почтой. Не поверите, но буквально с помощью 4-х сообщений первый «секретный» человек был обнаружен.
Очень интересно представлена теория 6 рукопожатий в фильме «Ёлки». Он лёгкий, весёлый и трогательный, и повествует о том, как жители из разных уголков России помогают одному ребёнку из детского дома. А знаете, каким образом? Передают его просьбу друг другу, которая обращена к Президенту. А это сделать не так просто, хотя бы потому, что никто с ним лично не знаком.
Алгоритм
Предлагаю поиграть в игру и провести собственный эксперимент, чтобы убедиться, что вы действительно связаны через знакомых с абсолютно разными людьми на планете, даже с самим Дональдом Трампом или Аллой Пугачёвой с Тимати. Итак, что требуется:
2. В поиске напишите любое имя и фамилию, просто даже придумав.
3. Вам будет предложен список людей по запросу, выбирайте того, кто первым приглянется. Можете даже рискнуть и кликнуть на чужестранца.
4. Когда зашли на его страницу, посетите список друзей и нажимайте на самого первого.
5. Теперь повторяйте вышеуказанные действия, пока не обнаружите кого-то из тех, кто есть у вас в друзьях. Если даже придётся пройти 7-8 страничек, думаю, всё равно игру можно будет считать успешной.
Заключение
Сил вам и вдохновения!
Материал подготовила Журавина Алина.
Теория шести рукопожатий - теория, согласно которой любые два человека на Земле разделены в среднем лишь пятью уровнями общих знакомых (и, соответственно, шестью уровнями связей).
Теория была выдвинута в 1969 году американскими психологами Стэнли Милгрэмом и Джеффри Трэверсом. Предложенная ими гипотеза заключалась в том, что каждый человек опосредованно знаком с любым другим жителем планеты через недлинную цепочку общих знакомых. В среднем эта цепочка состоит из шести человек.
Милгрэм опирался на данные эксперимента в двух американских городах. Жителям одного города было роздано 300 конвертов, которые надо было передать определенному человеку, который жил в другом городе. Конверты можно было передавать только через своих знакомых и родственников. До бостонского адресата дошло 60 конвертов. Произведя подсчеты, Милгрэм определил, что в среднем каждый конверт прошел через шесть человек. Так и родилась теория «шести рукопожатий».
Повторили эксперимент Милгрэма при помощи электронной почты ученые кафедры социологии Колумбийского университета. Тысячам добровольцев они предложили «достучаться» до 20 засекреченных человек, о которых сообщали лишь основные характеристики: имя, фамилию, род занятий, место жительства, образование. Первой успешной попыткой стало определение почтового адреса одного из таких «засекреченных» в Сибири. Доброволец из Австралии нашел адрес сибирской «цели» при помощи всего четырех сообщений!
Анализ экспертами Microsoft данных, полученных за месяц общения 242 720 596 пользователей, занял два года. Объем исследуемых данных составил около 4,5 терабайт. На этой базе данных было установлено, что каждый из 240 миллионов пользователей сервиса мог бы «дойти» до другого в среднем за 6,6 «шага». Чем исследователи математически доказали теорию и расхожую шутку о том, что через пять человек каждый из нас знаком с английской королевой.
Между прочим, на основе теории «тесного мира» возникло и множество популярных в США игр. Например, ученые играют в «Число Эрдёша». Венгерский математик Пол Эрдёш - один из крупных учёных ХХ века, имеющий огромное число работ, написанных в соавторстве. Нужно найти кратчайшую цепочку от него до другого известного учёного. Если он написал какую-нибудь работу вместе с Эрдёшом, то число Эрдёша у него равно единице. Если в соавторстве с тем, кто, в свою очередь, написал что-нибудь с Полом Эрдёшом, то это число у него равняется двум и т. д. Почти все нобелевские лауреаты имеют небольшие числа Эрдёша.
Ещё одну попытку подтвердить Теорию шести рукопожатий предприняли пользователи социальной сети ВКонтакте. Специальное приложение ("Цепочка друзей - теория шести рукопожатий") позволяет искать цепочки знакомств между пользователями сети. Поскольку аудитория ВКонтакте ограничена (Россия и страны СНГ), добиться тех же результатов, какие были описаны выше, не удаётся - цепочки оказываются короче (3 - 4 человека). Однако интересно, что цепочки длиной более 6 человек практически не встречаются, что косвенно подтверждает изначальную теорию.
14 ноября 2011 в 16:21Теория шести рукопожатий: еще одно подтверждение
- Data Mining
Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в 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). Так что полученный результат можно считать еще одним подтверждением теории шести рукопожатий.
Документы
