Теория шести рукопожатий
Вы наверное слышали об идее что цепочки из шести человек, в среднем, достаточно чтобы связать вас с любым человеком на земле. Интересно также, возможно ли любого человека на земле связать с любым разумным существом во вселенной и какова длина этой цепочки. Но этот вопрос мы оставим на потом, и вернемся к границам земного шара.
Итак, в 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 если:
- Из вершины А есть путь в вершину B
- Его длина равна k
- Это кратчайший путь для двух данных вершин
Рассмотрим пример:
Из узла 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.
Я знаю вам не терпится это посчитать:
Куча нулей берется потому что наша сеть довольно ограничена, если бы человек было больше размер 3-соседей был бы в разы больше.
Получается что 3 рукопожатия это максимум что нам понадобится для того чтобы войти в контакт с любым человеком из этой сети.
Расширим масштаб нашей сети до 140 человек в клике и 10 случайных знакомых. Посчитаем сколько человек мы можем достать используя 6 рукопожатий:
Тринадцать миллиардов. Впечатляет! Это почти в два раза больше чем население земли.
Так откуда возникает столь интересный феномен? Он возникает из структуры нашей сети, а именно из того что у нас есть клики друзей и случайные знакомые. Структура же возникает из того, как каждый элемент сети создает связи с другими элементами. Для объяснения теории шести рукопожатий мы предполагали что у людей есть клика близких знакомых и у каждой такой клики есть связь, некий мост, в другую клику. Вообще, такие графы называются забавным названием «Мир тесен», и что самое удивительное не только социальные сети проявляют свойства подобных графов.
Интересно наблюдать за тем как растет число контактов с ростом числа рукопожатий. Если 1-соседей у нас 150, то 2-соседей уже 2900, а 3-соседей уже 239 000. Это население довольно крупного города. Это может натолкнуть на мысль, что более слабые связи могут дать нам больше, потому что в них участвует большее количество людей. Именно эту идею представляет американский социолог Марк Грановеттер в статье «Сила слабых связей».
Конечно, это не полностью описывает то, как обстоят дела настоящем мире. Это всего лишь игрушечная модель. Но в отличии от анализа реального положения дел, со всеми его деталями, наша модель позволяет нам получить понимание того, почему теория шести рукопожатий имеет место быть.