Мир тесен. Насколько?

(Опубликовано в Домашнем компьютере №1/2002. Выкладываю на Арбузе, так как статья очень интересная, а журнал на сайте ДК выкладывается с трехмесячным опозданием)

Автор  Константин Кноп, konstantin@knop.com

Расстояние от Эрдеша

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

Одним из таких специалистов в математике и являлся Пал Эрдёш. Его "конек" -- постановка и исследование трудных задач и разнообразных гипотез -- и он с успехом проделывал это и в теории графов, и в геометрии, и в теории чисел, и в комбинаторике. Кроме того, Эрдеш был удивительно открытым человеком. Больше всего он любил поездки и путешествия, легко сходился с людьми, запросто дарил коллегам свои идеи и соображения... Стоит ли удивляться тому, что этот человек написал за свою долгую (1913-1996) жизнь кучу статей, соавторами которых были самые разные люди? Общее число его статей превысило 1400 -- и это при том, что среднее число публикаций на одного автора, согласно базе данных Американского Математического Общества, равно 6,87. Следующим по плодовитости после Эрдеша является болгарин Друми Байнов, а у него "всего" 782 работы. 

А теперь, собственно, о числах, названных в честь Эрдеша. Американцы Джерри Гроссман и Патрик Ион создали (между прочим, успели создать еще при жизни "дяди Пола") сайт "The Erdos Number Project", . Идея этого проекта очень проста, а вот реализация потребовала очень большой и кропотливой разыскной работы. Самому Эрдешу присвоен почетный номер 0. В списки  занесены все ученые, которые когда-либо писали совместные работы с Эрдешем. Каждый из них получил свой "номер Эрдеша", равный 1. Количество таких математиков на сегодняшний день равно 507. Далее все остальные их соавторы (общим числом 230) получили номер 2, все соавторы их соавторов -- номер 3, и т.п. Например, нобелевские лауреаты биологи Джеймс Уотсон и Френсис Крик (открывшие "двойную спираль" ДНК) имеют номера 7 и 8 соответственно, Альберт Эйнштейн получил номер 2, а Роберт Оппенгеймер -- номер 4. В списке обладателей номеров Эрдеша более сотни нобелевских лауреатов -- и это несмотря на то, что нобелевские премии по математике, как известно, не присуждаются. 

И самое забавное, что нумерация еще не окончательна, поскольку новые публикации Эрдеша (и новые обладатели номера 1) появляются даже спустя пять лет после его смерти! Вообще, оказалось, что весь математический мир очень тесно связан -- практически каждому действующему математику (пожалуй, кроме тех, кто никогда не писал в соавторстве) присвоено число Эрдеша, и все эти числа не больше 15, причем только 2% из них имеют номер больше 7! 

Игра в "Кевина Бэкона" 

Вот еще один аналогичный пример. Есть такой знаменитый американский актер Кевин Бэкон. Знаменит он прежде всего тем, что снимался в большем числе фильмов, чем кто-либо другой среди нынешних голливудских актеров (если верить данным Мирославы Сегиды, собравшей аналогичную статистику по российским актерам, то "нашим Кевином" является Армен Джигарханян). Популярная в Штатах игра состоит в том, чтобы вычислить чей-нибудь "номер по Бэкону". Например, у Алисы Фрейндлих номер Бэкона равен 3: Алиса Фрейндлих играла в фильме "Катя Исмаилова" (1993) с Владимиром Машковым, Машков снимался в "15 minutes" (2001) c Чарльзом Тероном, последний работал в фильме "24 часа" (2001) с Кевином Бэконом (пример вычислен при помощи "Оракула Кевина Бэкона",  Кстати, у Аллы Пугачевой и еще у двухсот тысяч актеров и актрис номер Бэкона тоже равен 3 или даже меньше. 

Иначе говоря, список киноактеров мира тоже связен. Причем в среднем актеры "ближе" к Бэкону, чем математики к Эрдешу (в частности, Бэкон-номер 1 имеют почти полторы тысячи человек). Вообще, сообщество математиков, видимо, перемешано слабее: среди киноактеров максимальное расстояние равно 10... [Кстати, специалисты по теории графов называют эту характеристику "диаметром". Точнее, диаметр -- это наибольшее из расстояний между отдельными вершинами графа.] Между прочим, известный математик Дан Клейтман однажды работал "математическим консультантом" фильма "Good Will Hunting". Это позволяет вычислить его "номер по Бэкону" - он равен 2. В то же время его "номер по Эрдешу" равен 1. Вы уже поняли, что отсюда следует? А вот что: ничто не мешает рассмотреть объединенный граф связей, в который войдут как математики, так и актеры -- при этом условие наличия связи будет иметь такой вид: "XX и YY имеют общую работу" (и какая разница, что собой представляет эта работа -- кинофильм или научную статью?). В таком графе Эрдеш и Бэкон будут находиться на расстоянии 3, ну, а остальные действующие лица -- в среднем чуточку дальше... Кстати, сейчас у Эрдеша есть "официальный" номер по Бэкону, равный 4. Это произошло потому, что о нем снят документальный фильм "N -- это значит Число". Относительно недавно Уильям Монтбло создал сайт посвященный аналогичным ссылкам среди рок-музыкантов. www.ultranet.com/~geezer/black_sabbath_game.html 

Подобный граф связей исследован для специалистов по теоретической информатике, см. sigact.acm.org/genealogy . Впрочем, computer science сравнительно быстро вливается в общее математическое древо... Ну, и, наконец, добавлю, что "Оракул Бэкона", с рассказа о котором я начал этот раздел, на самом деле тоже является частью более крупного проекта Star Links: вот здесь  можно ввести ЛЮБУЮ ПАРУ фамилий и указать тип фильмов для поиска связей между ними (кино, ТВ, кино+ТВ). Например, путь от Чарли Чаплина до Юрия Мамина имеет длину 3: "Yuri Mamin was in "Okno v Parizh" (1994) with Jean Rupert, Jean Rupert was in "Lady L" (1965) with Sophia Loren, Sophia Loren was in "Countess from Hong Kong, A" (1967) with Charles Chaplin". Аналогично, путь от Владимира Высоцкого до Булата Окуджавы имеет длину 2, и такую же длину имеет путь от Высоцкого до Евгения Евтушенко Кстати, вопрос для заядлых киноманов: каждый из них "имеет общую работу" с Георгием Юматовым. А в каких именно фильмах? Попробуйте ответить на этот вопрос, не заглядывая ни в "Стар Линкс", ни в Internet Movie Database , ни в другие справочные сайты. 

Шесть рукопожатий 

В 1960-х годах американский психолог Стэнли Милграм (подробнее о нем см. здесь ) задался вопросом, является ли все американское общество связным графом, и если да, то каков его диаметр. Милграм попросил 300 различных "источников" переслать "важное" письмо указанному им "приемнику" в Бостон, используя при этом в качестве связующих звеньев только своих личных друзей. Из 300 писем цели достигли 60, причем средняя длина маршрута была равна 6, из чего Милграм заключил, что в среднем любого (взятого наугад) американца отделяет от любого другого американца всего 6 рукопожатий (см. здесь). Его фразу ("Six degrees of separation" -- аналог нашего "мир тесен") подхватили и журналисты, и политики. И даже на Бродвее теперь идет одноименная пьеса... Хочу отметить, что милграмовский эксперимент разрешал отправку письма не любому знакомому, а только "другу". В первом приближении другом является только такой знакомый человек, с которым Вы при встрече непременно обменяетесь рукопожатием. (На самом деле Милграм использовал немного другой критерий -- "first name basis", то есть когда вы с другим человеком называете друг друга по имени. Но для русской культуры этот критерий менее адекватен, потому что у нас немного другие традиции...) 

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

Проект Smallworld 

Впрочем, я уже неоднократно убеждался в справедливости яндексовского тезиса "найдется все". Нашлось. Причем, что совсем уж парадоксально, нашло меня само. Точнее, меня разыскал один из знакомых (точнее, друзей, потому что за руку мы с ним здоровались еще тогда, когда он жил в России). Ныне он учится в аспирантуре Колумбийского университета и как раз занимается проектом http://smallworld.sociology.columbia.edu На этом сайте -- вся необходимая (и не очень) информация об истории, целях и ходе этого эксперимента. Все желающие могут зарегистрироваться и принять участие в проекте. Поверьте, это прежде всего будет увлекательно и интересно вам самим. Название проекта, насколько я понимаю, заимствовано из книги Дункана Уоттса, (http://www.amazon.com/exec/obidos/ASIN/0691005419/102-8877181-9512929). Впрочем, я могу и ошибаться. У меня самого еще очень много вопросов обо всем этом. Давайте искать вместе. Мир тесен.