Шесть степеней

Исследователи из Массачусетского университета в Амхерсте изобрели новый алгоритм, который решает задачу поиска в сетях, долгое время ставившую в тупик ученых и социологов.
Ученые создали алгоритм, который объясняет результаты социологических исследований, легших в основу теории о «шести степенях разделения», и является алгоритмом, позволяющим осуществлять поиск в сетях. Применение этой технологии позволит улучшить работу аварийных систем, предотвратить распространение компьютерных вирусов и т.д.
Алгоритм, названный навигация по ожидаемым значениям (expected-value navigation), описывает эффективный способ поисков конкретного класса сетей. Он был представлен докторантом Озгюр Симсеком (Özgür Simsek) и профессором информатики и вычислительной техники Дэвидом Йенсеном (David Jensen), на 19-ой Международной совместной конференции, посвященной проблемам искусственного интеллекта, прошедшей в Эдинбурге, Шотландия.
Алгоритм применим к разным сетям, утверждают исследователи. В частности, от новой технологии выиграют беспроводные сети, одноранговые сети, а также сама всемирная паутина. Особенно хорошо алгоритм работает с динамическими системами (беспроводными сетями), где структура меняется настолько быстро, что их ядра быстро устаревают.
Источником работы послужило исследование, проведенное в конце 60-х годов, предметом которого была навигация в социальных сетях, объясняет Симсек. В рамках этого исследования, результаты которого стали известны не так давно, психологи Милграм (Milgram) и Траверз (Travers), людей из Бостона, Омахи и Небраски попросили об обычной вещи: доставить письмо целевому человеку в Бостоне, однако необычным способом. Сообщение следовало передавать по цепочке знакомых.
Людям в начале цепочки предоставлялась некоторая базовая информация о целевом человеке, в том числе имя, возраст и род занятий, и их просили передать письмо через знакомых с наименьшим количеством посредником. Если учесть только те письма, которые в итоге были доставлены, то средняя длина цепочки знакомств составила шесть человек.
«Из результатов этого исследования следует, что мы все связаны», - утверждает Симсек. Однако следующий вопрос, который возникает – как именно. Какие свойства социальных сетей позволяют людям эффективно ориентироваться в них?
Социальная сеть, послужившая предметом исследования Травреза и Милграма, - не является упорядоченной сетью. С одной стороны, топологическая схема сети известна только в локальной точке – люди, которым вручалось письмо, не знали целевого человека. С другой – сеть децентрализована, у нее не было формального ядра в виде, скажем, почтового отделения.
Если предположить, что навигация в такой сети должна быть успешной (а задачи поиска в одноранговых сетях совместного пользования файлами или навигации по всемирной паутине переходами с ссылки на ссылку подразумевает именно это), то в структуре, лежащей в основе этих сетей, должно быть что-то, что обеспечивает успех поиска, утверждают Йенсен и Симсек.
Те участники эксперимента, проведенного Траверзом и Милграмом, которые успешно доставили письмо, видимо, действовали интуитивно и обладали двумя качествами, которые применимы и к поиску в компьютерных сетях. Во-первых, люди общаются, как правило, с людьми, похожими на них самих, а во-вторых – некоторые люди более коммуникабельны, чем другие. «Поиск» с помощью двух этих факторов оказывается эффективным даже тогда, когда структура сети практически неизвестна.
Тенденция «общаться с себе подобными» означает, что атрибуты узла (человека в исследовании Милграма и Траверза), скорее всего, окажутся коррелированными. Бостонцы часто знакомы с другими бостонцами, и то же самое можно сказать о таких качествах как возраст и род занятий. Вторая важная характеристика таких сетей – это то, что некоторые люди имеют больше знакомых, чем прочие. Эта «несоразмерность степеней» приводит к тому, что эти люди начинают играть роль ядер.
Если учесть оба этих фактора, то получается алгоритм поиска, доставляющий сообщения целевому человеку через наиболее общительных людей, которые с большей вероятности оказываются целевыми.
Или, в терминах сетевого поиска, алгоритм тяготеет к узлам, относительно которых вероятность связи с целевым узлом наиболее высока.
Предыдущие исследования в этой области опирались на какой-либо один из этих факторов, однако Симсек и Йенсен впервые объединили их и создали алгоритм, в основе которого лежит теория вероятностей. Алгоритм оказался чрезвычайно эффективен при поиске наикратчайшего пути между узлами сети, центральная структура которой неизвестна, говорят ученые.

21-09-2005г.

Архив новостей

Архив сообщений о новых публикациях