Компьютерра - Журнал «Компьютерра» № 27-28 от 24 июля 2007 года (695 и 696 номер)

(думаю над продолжением)

Автор: Захаров, Павел

По мере проведения исследований выявляется множество удивительных общих свойств сетей столь разного происхождения. Например, очень многие сети являются «малыми мирами», поскольку путь от одного узла к другому зачастую намного меньше ожидаемого интуитивно. Один из самых известных экспериментов в истории социологии, проведенный психологом из Гарварда Стэнли Милгрэмом в 1967 году, показал, что жителей США объединяет цепочка в среднем из пяти знакомых или шести рукопожатий. Парадоксальность полученного результата привела к быстрой популяризации концепции малого мира, которая позже была продемонстрирована для сетей совместных съемок актеров и сотрудничества ученых. А недавно в процессе изучения русскоязычного сегмента LiveJournal наша группа из Швейцарского университета Фрибурга выяснила, что эта сеть – еще более тесный мир, где всех пользователей разделяет цепочка в среднем в 4,3 рукопожатия.

МИНИАТЮРНАЯ ВСЕЛЕННАЯ

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

конце 90-х группа физиков из Университета Нотр-Дам (США) под руководством Альберто Барабаши предприняла попытку определить, насколько мал мир веба, то есть сколько в среднем требуется кликов, чтобы перейти от одной веб-страницы к другой. Оказалось, что уже в далеком 1999 году кликов требовалось всего лишь девятнадцать. Благодаря этой работе была сделана еще одна чрезвычайно важная и неожиданная находка – самоподобие структуры веба. Распределение количества ссылок, размещенных и указывающих на веб-страницы, спадает по степенному закону, что приводит к так называемому эффекту "толстого хвоста" распределения – наличию значительного количества страниц с чрезвычайно большим количеством ссылок.

С тех пор пошло-поехало: класс малых безразмерных сетей стал пополняться все новыми и новыми типами сетей окружающего нас мира. И вот, наконец, ученые снова взялись за самые сокровенные сети – сети человеческих взаимоотношений, или, попросту, социальные сети. Произошло это во многом благодаря набравшим популярность в последние годы блог-сервисам со встроенной поддержкой социальных связей, которым удалось накопить гигантские базы виртуальных взаимоотношений пользователей. Некоторые из них, такие как безусловный лидер в России – LiveJournal, или Живой Журнал, даже не думают скрывать свои базы ни от

праздного наблюдателя, ни от сетевого исследователя и более того – поддерживают бот-интерфейс, заметно упрощающий сбор данных. Эта возможность и была использована нашей группой для изучения доступной сети френдования1 LiveJournal. В LJ на момент написания статьи (май 2007 года) зарегистрировано больше 12 млн. пользователей, 1,8 млн. из которых, по сведениям LJ, активны. Начав с нескольких активных пользователей и исследуя все исходящие дружеские связи, краулер способен в течение некоторого времени собрать данные о более чем 4,3 млн. пользователей, пока не будут исчерпаны все ссылки. Этот блок сети, составляющий ее основную и самую важную часть, называют сильно связанным компонентом. Когда вся информация собрана исохранена на локальном компьютере, она может быть досконально исследована методами анализа графов.

Итак, является ли социальная сеть LJ "малым миром"? Оказывается, да. Конечно, LJ – очень тесный мир, где один пользователь соединен с другим цепочкой в среднем из пяти друзей. То есть требуется шесть шагов по друзьям, чтобы, начав с одного, достичь любого другого пользователя. Не правда ли, удивительное совпадение с легендарными шестью рукопожатиями Милгрэма?

Но на этом неожиданности не заканчиваются. Что представляет собой подобная сеть?

Является ли она бессистемным переплетением связей, то есть случайной сетью, или ее структурой все же управляют некие скрытые законы. Читатель, знакомый с LiveJournal, тут же отметит, что кириллический ЖЖ [Я намеренно использовал термин «кириллическое» сообщество, а не «российское» или "русскоговорящее", поскольку оно не ограничивается определенной страной, национальностью или языком. Как правило, его составляют выходцы из стран бывшего СССР и Израиля, которые, однако, могут географически находиться где угодно. В дальнейшем под ЖЖ будет подразумеваться именно этот сегмент, а под LJ – сеть в целом] и остальной, преимущественно англоязычный LJ – совершенно разные сущности, и будет прав. Они лишь функционируют внутри одной программной системы, и собраны нами в один большой граф. Есть ли возможность разделить их, пользуясь лишь имеющейся информацией о дружеских связях?