Что запомнилось в 2015

В декабре принято подводить итоги минувшего года, и мы решили последовать этой традиции. В этом посте мы расскажем о трех направлениях в исследованиях социальных сетей этого года, показавшихся нам интересными.

Графы-близнецы

В конце ноября социальные сети облетела новость о том, что предложен способ уменьшения вычислительной сложности при работе с изоморфными графами. Хотя формулировка задачи может показаться тяжеловесной, на деле все не так уж и сложно.

Изоморфными называются графы G и H, если путем перестановки строк и столбцов матрицы смежности графа G удается получить матрицу смежности графа H.  Другими словами, два рассматриваемых графа одинаковы.

Изоморфные графы. Источник.

Так называемая «проблема изоморфизма графов» (graph isomorphism problem) заключается в том, что перебор всех возможных перестановок занимает очень много времени. И в случае анализа больших графов эти сравнения могут в принципе не выполняться, что ограничивает возможности исследователя. Например, невозможно сравнить между собой граф социальных сетей Facebook и Twitter.

Профессор Ласло Бабаи из университета Чикаго предложил альтернативный метод для выявления изоморфизма графов. Подробности о методе можно прочесть в работе.

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

Множество сетевых измерений

Исследование многоуровневых социальных сетей (multilevel social networks) нельзя назвать новой темой, однако в текущем году вышло много исследований по этой тематике, и с большой долей уверенности можно утверждать, что это не конец. Многоуровневой называют такую социальную систему, в которой рассматривается сразу несколько типов связей между агентами. Одной из наиболее цитируемых работ, рассматривающей развитие одновременно двух социальных сетей, стала статья Леи Эллвардт с соавторами. В ней рассматривается влияние «сплетен» и обсуждений сотрудников в организации на формирование дружеских взаимоотношений внутри коллектива. Результаты эмпирических оценок свидетельствуют о том, что эти отношения находятся в сложной взаимозависимости.

В этом году в  журнале Social Networks вышел специальный выпуск, посвященный многоуровневым сетям. Исследователи теперь получили возможность рассматривать социальные взаимоотношения не в каком-либо узком контексте, а принимать во внимание и другие события, происходящие с людьми.

Как предотвратить эпидемию

Все большее внимание сетевиков приковывают исследования в области эпидемиологии. Это происходит из-за целого комплекса факторов: развития матметодов, совершенствования процедур сбора данных о пандемиях, новых вспышках эпидемий и т.д.

География лихорадки Эбола. Источник.

Хотя число исследований эпидемий и пандемий растет в геометрической прогрессии, на данный момент нет готового инструмента, позволяющего предсказать, во что выльется заболевание тем или иным вирусом. Разработкой таких методов занимаются в центре сетевых исследований университета Норсвестерн. Об исследованиях можно почитать здесь, здесь и здесь. Схожий проект есть в институте сложных адаптивных систем Санта Фе (о проекте можно почитать здесь). Ученые анализируют как распространение гриппа (работа 1, работа 2), так и лихорадку Эбола, вспышки холеры и т.д. Современные исследования принимают во внимание сразу многие факторы – природу и устойчивость вируса, структуру контактных сетей, влияние мобильности людей на развитие эпидемии. Так что мы все ближе и ближе приближаемся к пониманию всех механизмов распространения заболеваний а, значит, и к контролю над ними.

Желаем в Новом году найти новых близких по духу друзей (как изоморфные графы), иметь многогранные отношения с близкими (мультисетевые), и не болеть (и не заражать)!