Проекция двудольной сети

Двудольные сети представляют собой особый класс сложных сетей, чьи вершины разделены на множества X и Y, при этом допускаются только связи между вершинами из разных множеств. Для удобства визуализации структуры связей внутри одного из множеств двудольные сети часто сжимают посредством одномодовой проекции. Это означает, что построенная сеть содержит вершины только одного из двух множеств, и две вершины X (или Y) соединены ребром тогда и только тогда, когда у них есть хотя бы один общий сосед из противоположного множества Y (или X).

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

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

1. Простое взвешивание. При простом взвешивании веса рёбер равны количеству совместных связей через общий элемент противоположного множества (данный принцип используется на приведённом рисунке выше). Этот подход часто хорошо работает при анализе, например, кулинарных рецептур или большинства социальных сетей. Однако он может быть некорректным, если вклад каждой дополнительной связи зависит от особенностей сети (например, от исходного веса между соответствующими вершинами). Такая ситуация возможна, например, в исследовании научных коллабораций, на что указывали Fan и др..
2. Гиперболическое взвешивание. В случае убывающего маржинального вклада дополнительных связей к вершине простое взвешивание может быть недостаточно информативным. Например, в сетях научного сотрудничества можно ожидать, что два автора, чьи имена стоят в публикации вместе с большим числом других соавторов, знают друг друга хуже, чем те, кто был единственным соавтором^[3]. Для учёта этого так называемого эффекта насыщения было предложено взвешивать связи обратно пропорционально количеству общих связей в соседнем множестве. Обычно это реализуется путём введения коэффициента 1/(n − 1), ослабляющего связь между вершинами, имеющими более популярные общие связи.
3. Взвешивание, основанное на распределении ресурсов. При простом и гиперболическом взвешивании результирующая матрица смежности проекции симметрична, то есть связь между двумя вершинами имеет одинаковый вес с обеих сторон. Более того, информация о рёбрах, чьи «конечные» вершины имели степень 1 в исходной сети, теряется при проецировании, что может быть критично для некоторых реальных сетей с большим числом независимых рёберных множеств. Для устранения этих недостатков Чжоу и др. предложили метод взвешивания, основанный на предположении о наличии фиксированного ресурса у каждой вершины проекции; направленный вес w_ij трактуется как доля ресурса, которую вершина j готова передать вершине i. Распределение ресурса осуществляется на основе исходного двудольного графа, равномерно по его соседям, и состоит из двух шагов: сначала — из проецируемого множества в непрямицомое, затем обратно. Численные эксперименты показывают, что этот метод превосходит некоторые широко применяемые подходы (например, коллаборативную фильтрацию) для задач персональных рекомендаций.

Каждый выбранный способ взвешивания приводит к получению взвешенной одномодовой (унипарной) сети, в которой веса связей отражают степень общности соседей двух вершин в исходной двудольной сети. Конкретные значения этих весов зависят от степеней обеих групп вершин. Например, в сети научного соавторства^[4] количество выявленных совместных публикаций определяется: 1) числом статей каждого автора и 2) числом авторов в каждой статье. Специализированные скелетные алгоритмы, разработанные для проекций двудольных сетей (в противоположность универсальным алгоритмам для взвешенных сетей, таким как дисперсионный фильтр), используют данную исходную информацию для идентификации статистически значимо высоких (либо, напротив, низких) весов рёбер^[5]. Если оставить только рёбра со статистически значимыми весами, на выходе получается невзвешенная и обычно разреженная «скелетная» сеть, более удобная для анализа и визуализации.

Современными альтернативами классической одномодовой проекции выступают гиперграфы и симплициальные комплексы, позволяющие сохранять сложную топологию исходной сети без потерь информации^[6].

Для обработки двудольных графов активно применяются графовые нейронные сети (GNN) и механизм передачи сообщений (Message-Passing)^[7]. Среди современных методов прогнозирования связей выделяются алгоритм BiGLP, предназначенный для предсказания связей между индивидами и группами, а также архитектура SBSN, применяемая для анализа масштабных знаковых двудольных графов^[8].

• Сеть ароматов и принципы Сочетание продуктов

• Сеть научного сотрудничества^[4]
• Сеть корпоративной элиты
• Сеть человеческих болезней^[9]
• Сеть совместного спонсорства в Конгрессе США^[10]
• Рекомендательные системы (электронная коммерция, стриминговые платформы), где применяются графовые нейронные сети (например, архитектура на основе GraphSage) для предсказания взаимодействий пользователей с контентом^[11].
• Биологические сети и поиск новых лекарств (drug discovery), включая анализ взаимодействий молекул и предсказание ответа на препараты с помощью моделей MGTNSyn и H-GCN^[12].^[13]
• Анализ политических сетей (на примере Сената США), где использование бипартитной модели (biMMSBM) вместо классической проекции позволило избежать искусственного завышения партийной поляризации^[14].