ITHACA, N. Y. - Мы все знаем, что это тесен мир: каждый из нас находится всего в шести знакомых друг от друга. Даже в огромной путанице Всемирной паутины в среднем одна страница находится всего в 16-20 кликах от любой другой. Но как, не имея возможности видеть всю карту, мы можем передать сообщение человеку, который находится всего в «шести степенях разделения»?
Ученый-компьютерщик Корнеллского университета пришел к выводу, что ответ кроется в личных сетях: мы используем «структурные сигналы» в нашей локальной сети друзей. Это коллективное явление. В совокупности сеть умеет находить людей, даже если этого не делает ни один человек», - говорит Джон Клейнберг, доцент кафедры компьютерных наук, опубликовавший свое объяснение в последнем номере (24 августа) журнала Nature.
Его исследование основано на компьютерной модели, показывающей, что «идеальная» сетевая структура - это структура, в которой соединения распределены по схеме «обратный квадрат». С точки зрения человека это означает, что у «идеального» человека в модели будет примерно столько же друзей в остальной части округа, сколько и в районе, столько же друзей в остальной части штата, сколько в округе, столько же друзей в округе. вся нация как в государстве и т. д., как вы могли бы найти в очень мобильном обществе.
Ответы Кляйнберга могут иметь очень практическое применение, помогая сократить количество кликов, необходимых при просмотре веб-страниц, а также помогая ускорить другие виды сетей.
Хотя Клейнберг сыграл важную роль в разработке улучшенных поисковых систем для Интернета, он не считает, что эта работа применима к традиционным поисковым системам. У них уже есть «общая картина» сети, объясняет он, поскольку они работают с индексами сети. Скорее, он считает, что это полезно для создания «агентов», компьютерных программ, которые будут прыгать по сети в поисках конкретной информации.
Это также может относиться к распространению данных через Интернет, где компьютеры, называемые маршрутизаторами, должны отправлять пакеты информации по пути к месту назначения, не зная, в каком состоянии находится сеть за пределами их непосредственного соседства.
Клейнберг показал, что компьютерный алгоритм (базовая схема программы) может выбрать наилучший способ отправки сообщения в удаленное место в сети, даже если он знает только о характеристиках своего непосредственного окружения. «Корреляция между локальной структурой и дальними связями дает фундаментальные подсказки для поиска путей в сети», - пишет он в статье Nature.
Работа Клейнберга является усовершенствованием более раннего исследования двух других корнеллианцев, Стивена Х. Строгаца, профессора теоретической и прикладной механики, и его аспиранта Дункана Уоттса, ныне доцента кафедры социологии Колумбийского университета.
Строгац и Уоттс предложили математическое объяснение результатов знакового эксперимента, проведенного в 1960-х годах в Гарварде социальным психологом Стэнли Милгрэмом. Исследователь раздал письма случайно выбранным жителям Омахи, штат Небраска, и попросил их доставить письма жителям Массачусетса, передавая их от одного человека к другому. Среднее количество шагов оказалось около шести, что породило популярное понятие «шесть степеней разделения» и, в конечном итоге, игру «шесть степеней Кевина Бэкона», в которой актеры связаны своими появлениями в кино с другими актерами.
Строгац и Уоттс создали математическую модель сети, в которой каждая точка или узел тесно связана со многими другими соседними узлами. Когда они добавили всего несколько случайных соединений между несколькими удаленными друг от друга узлами, сообщения могли перемещаться от одного узла к другому намного быстрее, чем можно было бы предположить из-за размера сети. По их словам, идея шести степеней разделения работает, потому что в каждой небольшой группе друзей есть несколько человек, которые имеют более широкие связи, либо географические, либо социальные. Они также показали, что такие взаимосвязанные сети существуют не только между людьми, но и в таких различных местах, как компьютерные сети, электрические сети и человеческий мозг.
Но Клейнберг математически обнаружил, что модель, предложенная Строгацем и Уоттсом, не объясняет, как сообщения могут так быстро перемещаться по реальным человеческим сетям. «В модели Строгаца-Уоттса были случайные соединения между узлами. Полностью случайные соединения сближают всех, - объясняет Клейнберг, - но компьютерный алгоритм будет иметь только локальную информацию. потерял."
Итак, Клейнберг разработал модель, в которой узлы расположены в виде квадратной сетки, и каждый узел соединен с другими случайным образом, но с «предвзятостью, основанной на географии». В результате каждый узел связан со многими близлежащими, несколькими на более дальнем расстоянии и еще меньшим количеством на большом расстоянии - структура «обратный квадрат». «Эта предвзятость встроена в структурные сигналы моих дальних связей, и именно эта предвзятость неявно ведет вас к цели», - объясняет Клейнберг. «В модели Строгаца-Уоттса вообще нет предвзятости и, следовательно, никаких сигналов - структура дальних связей не дает вам вообще никакой информации о базовой сетевой структуре».
Отправитель сообщения в этой системе не знает, где находятся все соединения, но знает общее географическое направление пункта назначения, и если сообщения отправляются в этом направлении, говорит Клейнберг, они прибывают намного быстрее, чем они бы совершили совершенно случайное путешествие.
Кляйнберг объясняет: «Модель Уоттса и Строгаца похожа на большую группу людей, которые знают друг друга только посредством электронного чата в Интернете. Если вам дали идентификатор пользователя кого-то, кого вы не знаете, очень трудно угадать, кто из ваших друзей может помочь вам переслать им сообщение.
"Модель обратных квадратов больше похожа на географический взгляд на эксперимент Милгрэма - если вы живете на Западном побережье и вам нужно переслать сообщение кому-то в Итаке, вы можете догадаться, что житель штата Нью-Йорк является хороший первый шаг в цепочке. Они, скорее всего, знают кого-то в районе Фингер-Лейкс, а тот, в свою очередь, с большей вероятностью знает кого-то в Итаке и т. д. Зная, что наше распределение друзей коррелирует с географией, вы можете делать предположения о том, как быстро переслать сообщение."
Географическая информация в сетке, добавляет он, является аналогом социальных связей между людьми. Точно так же, как узлы в его смоделированной сети выбирают правильное географическое направление для отправки сообщения, люди могут выбирать социальное направление: математик, который хочет отправить сообщение политику, может начать с передачи его юристу.
С другой стороны, он говорит: «Когда связи дальнего действия генерируются равномерно случайным образом, наша модель описывает мир, в котором существуют короткие цепи, но люди, сталкиваясь с дезориентирующим набором социальных контактов, не могут найди их."
Статья в Nature называется «Навигация в маленьком мире».
Связанные сайты в Интернете:
- Домашняя страница Джона Кляйнберга:
- Природа: