Динамическая центральность

В дополнение к предыдущему посту про динамические свойства сложных сетей и в ознаменование начала новой серии подобных обзоров публикую краткое изложение статьи «From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks», Dan Braha, Yaneer Bar-Yam. Published in Complexity, Vol. 12 (2), pp. 59-63, November 2006.
(http://arxiv.org/ftp/physics/papers/0611/0611295.pdf)



В работе исследовалась динамика активности сетевых связей. Объектом исследования служил массив переписки по электронной почте между 57158 пользователями большого американского университета на протяжении 113 дней. Рассматривались только значимые сообщения, спам и массовые рассылки отфильтровывались. После фильтрации осталось 447543 письма. За каждый день наблюдения формировалась одна ненаправленная сеть, общее их количество составило 113 и это дало возможность исследовать динамику формирования связей в сети. Утверждается, что анализ направленных сетей при изложенном далее подходе дает практически одинаковые результаты.
И первым таким результатом стало обнаружение существенной разницы между сетями разных дней наблюдения. Оказалось, что связи из сетей разных дней слабо коррелируют друг с другом. Коэффициент корреляции связей составляет примерно 0,15 с распределением, близким к нормальному.

Интересно, что «сети рабочих дней» и «сети выходных» еще менее похожи друг на друга. По утверждению авторов, слабая корреляция означает, что наличие связи между двумя узлами в один день не делает более вероятным появление такой связи в другой день. Еще более интересным является тот факт, что в наблюдавшемся массиве данных слабая корреляция сетей, формируемых за отдельные временные интервалы остается слабой и не превышает 0,3, даже если период формирования сети увеличивается до 40 дней.

Каждая «дневная сеть» демонстрирует распределение степеней узлов, описываемое степенным законом с показателем гамма 2,5 – 2,8. Соответственно, в каждый день относительно небольшое количество узлов являются «центральными» и играют важную роль в обеспечении связанности сети. Неожиданным результатом для авторов работы стало то, что каждый день эти узлы разные… Степени таких «локальных хабов» сильно флуктуируют с течением времени. Другими словами, количество писем, которые отправляет или получает пользователь данного социума не является постоянным, а характеризуется степенным распределением.

В каждой дневной сети был выделен список ТОП1000 узлов с наибольшими степенями и для каждой пары дневных сетей рассчитывался процент совпадения узлов из двух таких списков. Оказалось, что процент совпадения центральных узлов также невелик – среднее значение 0,27 с характерными отличиями сетей рабочих и выходных дней.

Сравнение дневных сетей и общей сети, сформированной за все время наблюдения, показало, что наиболее связанные узлы в общей сети играют весьма умеренную роль в дневных. Наконец, в работе был рассмотрен полный спектр сетей, формирующихся за временной интервал больший одного дня и меньший, чем все время наблюдения. Было выяснено, что зависимость степени непохожести сетей (определяемая как 1-доля перекрытия списков ТОП1000) от размера такого интервала также описывается степенным законом.

По мнению авторов, степенная зависимость «непохожести» сетей свидетельствует о том, что сети, формируемые в течение длительного периода времени, не сходятся к какой-то четко определенной структуре.


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


Причины, с которыми связано такое поведение сети электронной почте в конкретном социуме (напомню, это крупный американский университет) авторы не рассматривают, хотя, на мой взгляд, они достаточно очевидны: активность переписки студентов явно связана с конкретными событиями - экзаменами, сдачами зачетов, поздравлением с днем рождения и т.п. Понятно, что у разных людей эти события происходят в разное время, что и обуславливает разницу между составом узлов в дневных сетях. Напротив, штатный персонал университета значительно больше вовлечен в постоянные бизнес-процессы, отправляют письма не по много, но регулярно и в агрегированной сети степени данных узлов доминируют.