05.04.2017

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

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

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

В 2001 году Дункан Уоттс повторил вышеупомянутый эксперимент на современный манер. В качестве пакета для информации использовались электронные письма. Он получил такой же результат в виде средней длины цепочки равной шести.

Поразительно то, что шесть человек это не так уж и много. Это 0.00000008% от населения земли, которое примерно равно 7,3 миллиарда человек. Шесть человек можно посадить в ладу шестерку и устроить круиз по подмосковью. Но, как ни феноменально, этого может быть достаточно чтобы связать вас с любой, на первый взгляд самой недоступной, персоной.

Графы

Перед тем как мы приступим к рассмотрению возможного объяснения этого феномена нам необходимо познакомится с математическими объектами — графами, и с некоторыми из их свойств.

Граф это множество вершин и множество ребер, которые соединяют эти вершины. В графическом виде граф можно представить следующим образом:

У нас есть три вершины: A, B, C, и два ребра соединяющие их: AB, BC.

Может кто помнит такой вид развлечения из детства: дают набор точек и путем их правильного соединения получалась картинка какого нибудь котика. Набор точек это множество вершин, и по задаче мы рисовали к ним ребра. Граф в действии. Довольно продвинуто для детей, не находите? Так же я уже описывал такой объект как деревья, которые являются частным случаем графов.

Путь

Как видно из нашего рисунка некоторые ребра непосредственно связаны друг с другом. В нашем предыдущем примере из узла A есть ребро в узел B. Представим все ребра графа как дороги для автомобилей. Ну а там где есть дороги возможно и путешествие! Из A мы можем попасть в B, а из B мы можем попасть в C. Следовательно из A мы можем попасть в C, с промежуточной остановке в B.

Такое путешествие, а формально последовательность ребер через которые мы проходим, мы назовем путем. Длину последовательности ребер в пути будем считать длинной пути.

Итак, если мы из A хотим попасть в C, то нам необходимо преодолеть путь (AB, BC). Мы проходим два ребра, следовательно длина пути равна двум.

K-соседи

Для анализа путей вида A → C с промежуточной остановкой в B введем понятие k-соседей.

Вершина B является k-соседом вершине A если:

  1. Из вершины А есть путь в вершину B
  2. Его длина равна k
  3. Это кратчайший путь для двух данных вершин

Рассмотрим пример:

Из узла A в узел C мы можем попасть двумя путями: напрямую через ребро AC, или с промежуточной остановкой в B. Данные пути, соответственно, мы можем записать следующим образом (AC), (AB, BC). Каким же соседом C является для A? У нас есть два пути, длины этих путей равны 1 и 2 соответственно. Но для того чтобы полностью соответствовать нашему определению нам необходимо выбрать наименее короткий путь, следовательно C является 1-соседом вершине A.

Клика

Если из каждой вершины графа есть путь к любую другую вершину, то такой граф мы называем связанным.

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

Возьмем, к примеру, следующий граф:

В этом графе вершины A, B, C образуют клику, потому что у нас есть ребра из каждой вершины в каждую, а именно AB, AC, BC.

Сила

Крутость графов в том, что мы можем представлять объекты реального мира в их виде и, через такого посредника, производить вычисления над ними.

Приведем пример. В качестве вершин представим города, а в качестве ребер дороги между ними. Это называется дорожной сетью. Почему слово сеть заменило слово граф? Я, поверхностно просмотрев сеть интернет, так и не нашел ответа. Есть некая тенденция сетями называть объекты которые относятся к реальному миру, а графами объекты относящиеся к математическому. А может кому то не нравится благородство происхождения?

Так, не отвлекаемся. Представим себе гипотетическую дорожную сеть между четырьмя городами России:

Изображение схематично, не имеет общего с реальным положением дел

Используя то, что мы уже знаем о графах, проведем вычисления над этим графом. Если мы возьмем Москву как отправную точку нашего путешествия, то Санкт-Петербург, Воронеж, и Ярославль являются 1-соседями Москвы. Архангельск и Волгоград 2-соседями. Также города Москва, Ярославль, Санкт-Петербург образуют клику.

На этом мы не остановимся. Мы, также, можем вычислять кратчайшие пути между городами. Скажем, перед нами стоит задача попасть из Архангельска в Ярославль. Кратчайшим путем будет Архангельск — Санкт-Петербург — Ярославль, а не Архангельск — Санкт-Петербург — Москва — Ярославль.

Еще такой пример. Представим что мы проектируем дорожную сеть. Если на дороге из Москвы в Санкт-Петербург произойдет затор, то мы все же сможем попасть из Москвы в Архангельск через путь Москва — Ярославль — Санкт-Петербург — Архангельск. Но если произойдет затор Москва — Воронеж, то мы не сможем попасть из Воронежа и Волгограда в Санкт-Петербург. Москва является узким местом в нашей дорожной сети. Мы можем это исправить проведя дорогу между Воронежем и Ярославлем.

Звучит довольно тривиально, но переведем наши задачи в масштаб городских улиц. Скажем у нас 3 500 улиц с множеством перекрестков, на каждой из улиц разный параметр загруженности и следовательно время прохождения. Ответ на вопрос «Как быстрее попасть из пункта А в пункт Б» уже не столь тривиален. Сложность выявление узких мест в дорожной сети может стать настоящим кошмаром. Но если мы перекладываем нашу проблему на графы, то мы можем использовать алгоритмы для решения этих задач, а следовательно и компьютеры. Вот это уже звучит более интересно, не так ли?

Решение

Теперь мы полностью готовы рассмотреть наш изначальный вопрос. Для этого мы сконструируем модель социальной сети человечества.

Первое предположение: каждый человек обладает определенным кругом знакомств. У нас есть друзья, и, обычно, каждый наш друг знает другого нашего друга. Таким образом мы формируем некую клику в социальной сети, обозначим ее буквой C.

Второе предположение: у человека есть случайные знакомые не входящие в его круг знакомств. Скажем, с кем то мы учились в школе в параллельных классах или познакомились в детском лагере летом. Обозначим их буквой R. У каждого из таких случайных знакомых есть своя клика друзей, у людей из этой клики есть свои случайные знакомые и так далее. Скажем у нас есть 12 человек, в каждой клике по 3 человека, у половины по одному случайному знакомому. Социальная сеть будет выглядеть следующим образом:

Давайте посмотрим на k-соседей для A1 в нашей социальной сети. 1-соседи состоят из людей в клике С (вершины B1, C1), и произвольного друга R (вершина A2). 2-соседи состоят из произвольных знакомых людей из нашей клики (CR), и друзей из клики нашего произвольного знакомого (RC). Мы не включаем друзей клики из нашей клики (CC) потому что это теже люди что и сама клика C. В общем случае мы не включаем цепочки в которых C идет два раза подряд. Ну а с 3-соседей довольно затруднительно описать словами, поэтому просто перечислю в виде обозначений: CRR, CRC, RRR, RCR, RRC.

Я знаю вам не терпится это посчитать:

1-соседи: C + R = 2 + 1 = 3
2-соседи: CR + RC + RR = 2×1 + 1×2 + 1×0 = 4
3-соседи: CRR + CRC + RCR + RRC + RRR = 2×1×0 + 2×1×2 + 1×2×0 + 1×0×0 + 1×0×0 = 4

Куча нулей берется потому что наша сеть довольно ограничена, если бы человек было больше размер 3-соседей был бы в разы больше.

Получается что 3 рукопожатия это максимум что нам понадобится для того чтобы войти в контакт с любым человеком из этой сети.

Расширим масштаб нашей сети до 140 человек в клике и 10 случайных знакомых. Посчитаем сколько человек мы можем достать используя 6 рукопожатий:

1-соседи: C + R = 140 + 10 = 150
2-соседи: CR + RC + RR = 140×10 + 10×140 + 10×10 = 2 900
3-соседи: CRR + CRC + RCR + RRC + RRR = 140×10×10 + 140×10×140 + 10×140×10 + 10×10×140 + 10×10×10 = 239 000
4-соседи: CRRC + CRRR + CRCR + RCRC + RCRR + RRCR + RRRC + RRRR = 6 450 000
5-соседи: CRRCR + CRRRC + CRRRR + CRCRC + CRCRR + RCRCR + RCRRC + RCRRR + RRCRC + RRCRR + RRRCR + RRRRC + RRRRR = 399 100 000
6-соседи: CRRCRC + CRRCRR + CRRRCR + CRRRRC + CRRRRR + CRCRCR + CRCRRC + CRCRRR + RCRCRC + RCRCRR + RCRRCR + RCRRRC + RCRRRR + RRCRCR + RRCRRC + RRCRRR = 13 021 000 000

Тринадцать миллиардов. Впечатляет! Это почти в два раза больше чем население земли.

Так откуда возникает столь интересный феномен? Он возникает из структуры нашей сети, а именно из того что у нас есть клики друзей и случайные знакомые. Структура же возникает из того, как каждый элемент сети создает связи с другими элементами. Для объяснения теории шести рукопожатий мы предполагали что у людей есть клика близких знакомых и у каждой такой клики есть связь, некий мост, в другую клику. Вообще, такие графы называются забавным названием «Мир тесен», и что самое удивительное не только социальные сети проявляют свойства подобных графов.

Интересно наблюдать за тем как растет число контактов с ростом числа рукопожатий. Если 1-соседей у нас 150, то 2-соседей уже 2900, а 3-соседей уже 239 000. Это население довольно крупного города. Это может натолкнуть на мысль, что более слабые связи могут дать нам больше, потому что в них участвует большее количество людей. Именно эту идею представляет американский социолог Марк Грановеттер в статье «Сила слабых связей».

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

общество  /  математика  /  социология  /  теория графов
лайк