Двусторонняя сетевая проекция - Bipartite network projection

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

Фон

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

«Возможные проекции простой двудольной сети»

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

Возможные методы взвешивания

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

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

Некоторые известные приложения

  • Сеть вкусов и принципы сочетания еды[4]
  • Сеть научного сотрудничества [5]
  • Корпоративная элитная сеть [6]
  • Сеть болезней человека [7]

Рекомендации

  1. ^ а б «Проекция двусторонней сети и личная рекомендация» Тао Чжоу, Цзе Рен, Матуш Медо и И-Ченг Чжан в PHYSICAL REVIEW E 76 (4): 046115 (2007)
  2. ^ а б «Влияние веса на структуру сообщества в сетях» Ин Фань, Мэнхуй Ли, Пэн Чжан, Цзиньшань Ву, Цзэнру Ди в PHYSICA A 378 (2007) 583–590[постоянная мертвая ссылка ]
  3. ^ «Сети научного сотрудничества. II. Кратчайшие пути, взвешенные сети и центральность» М. Э. Дж. Ньюмана в PHYSICAL REVIEW E, vol. 64, 016132 (2001)
  4. ^ Ahn, Y. Y .; Ahnert, S.E .; Bagrow, J. P .; Барабаши, А. Л. (2011). ""Сеть вкусов и принципы сочетания продуктов питания "Йонг-Ёль Ан, Себастьян Э. Анерт, Джеймс П. Багроу и Альберт-Ласло Барабаси в NATURE, SCIENTIFIC REPORTS 1: 196, DOI: 10.1038 / srep00196" (PDF). Научные отчеты. 1: 196. Дои:10.1038 / srep00196. ЧВК  3240947. PMID  22355711. Архивировано из оригинал (PDF) на 2012-03-07. Получено 2012-05-17.
  5. ^ «Почему социальные сети отличаются от других типов сетей» Ньюман и Парк в PHYSICAL REVIEW E 68, 036122 (2003)
  6. ^ "Маленький мир американской корпоративной элиты, 1982-2001 гг." Дэвиса, Ю и Бейкера в СТРАТЕГИЧЕСКОЙ ОРГАНИЗАЦИИ, август 2003 г., т. 1 шт. 3 301-326
  7. ^ «Сеть болезней человека» Кванг-Иль Го, Майкла Э. Кьюсика, Дэвида Валле, Бартона Чайлдса, Марка Видаля и Альберта-Ласло Барабаси в PNAS vol. 104, нет. 21 (2007)