Многомерная сеть

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Составная часть Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес-модель Уоттс-Строгац Экспоненциальная случайность (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Блочное моделирование Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
Списки Категории
Темы Программное обеспечение Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

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

• 1 Терминология
• 2 Определение
  • 2.1 Невзвешенные многослойные сети
  • 2.2 Весовые многослойные сети
  • 2.3 Общая формулировка в терминах тензоров
• 3 Определения многомерной сети
  • 3.1 Многослойные соседи
  • 3.2 Длина многослойного пути
  • 3.3 Сеть слоев
• 4 меры центральности
  • 4,1 степень
  • 4.2 Универсальность как многослойная центральность
    • 4.2.1 Универсальность собственных векторов
    • 4.2.2 Универсальность Каца
    • 4.2.3 Универсальность HITS
    • 4.2.4 Универсальность PageRank
• 5 Триадные коэффициенты замыкания и кластеризации
• 6 Открытие сообщества
  • 6.1 Максимизация модульности
  • 6.2 Тензорное разложение
  • 6.3 Статистический вывод
• 7 Структурная сводимость
• 8 Другие дескрипторы многоуровневой сети
  • 8.1 Степенные корреляции
  • 8.2 Доминирование пути
  • 8.3 Обнаружение кратчайшего пути
  • 8.4 Многомерное расстояние
  • 8.5 Актуальность измерения
  • 8.6 Связь измерений
  • 8.7 Обнаружение пакетов
• 9 Процессы диффузии в многослойных сетях
  • 9.1 Случайные блуждания
  • 9.2 Классическая диффузия
  • 9.3 Информация и распространение эпидемий
  • 9.4 Перколяция многослойных взаимозависимых сетей
  • 9.5 Взаимозависимость с сообществами
  • 9.6 Динамическая взаимозависимость в многослойных сетях
• 10 Программное обеспечение
• 11 Источники
• 12 Внешние ссылки

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

Невзвешенные многослойные сети

В элементарной теории сети, сеть представлена в виде графа, в котором есть множество узлов, и в связи между узлами, как правило, представлена в виде набора узлов. Хотя эта базовая формализация полезна для анализа многих систем, сети реального мира часто добавляют сложности в виде нескольких типов отношений между элементами системы. Ранняя формализация этой идеи пришла благодаря ее применению в области анализа социальных сетей (см., Например, статьи о реляционных алгебрах в социальных сетях), в которых множественные формы социальных связей между людьми были представлены множественными типами ссылок. ${\ Displaystyle G = (V, E)}$${\ displaystyle V}$ ${\ displaystyle E}$ ${\ displaystyle u, v \ in V}$

Чтобы учесть наличие более чем одного типа связи, многомерная сеть представлена ​​тройкой, где - это набор измерений (или слоев), каждый член которого представляет собой другой тип связи и состоит из троек с и. ${\ Displaystyle G = (V, E, D)}$${\ displaystyle D}$${\ displaystyle E}$${\ Displaystyle (и, v, d)}$${\ displaystyle u, v \ in V}$${\ displaystyle d \ in D}$

Обратите внимание, что, как и во всех ориентированных графах, связи и различны. ${\ Displaystyle (и, v, d)}$${\ displaystyle (v, u, d)}$

По соглашению, количество связей между двумя узлами в данном измерении равно 0 или 1 в многомерной сети. Однако общее количество связей между двумя узлами по всем измерениям меньше или равно. ${\ displaystyle | D |}$

Взвешенные многослойные сети

В случае взвешенной сети этот триплет расширяется до четверки, где - вес на связи между и в измерении. ${\ Displaystyle е = (и, v, d, ш)}$${\ displaystyle w}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle d}$

Мультиплексная сеть европейских аэропортов. Каждая авиакомпания обозначает отдельный уровень. Визуализация с помощью программы muxViz

Кроме того, как это часто бывает при анализе социальных сетей, веса ссылок могут принимать положительные или отрицательные значения. Такие подписанные сети могут лучше отражать такие отношения, как дружба и вражду в социальных сетях. В качестве альтернативы, знаки ссылки могут быть изображены как сами размеры, например, где и. Этот подход имеет особое значение при рассмотрении невзвешенных сетей. ${\ Displaystyle G = (V, E, D)}$${\ Displaystyle D = \ {- 1,0,1 \}}$${\ Displaystyle Е = \ {(и, v, d); и, v \ in V, d \ in D \}}$

Эта концепция размерности может быть расширена, если атрибуты в нескольких измерениях нуждаются в спецификации. В этом случае ссылки представляют собой n кортежей. Такая расширенная формулировка, в которой связи могут существовать в нескольких измерениях, необычна, но использовалась при исследовании многомерных сетей, изменяющихся во времени. ${\ Displaystyle е = (и, v, d_ {1} \ точки d_ {п-2})}$

Всемирный экономический форум карта глобальных рисков и глобальных тенденций, моделируется как взаимозависимой сети (также известной как сеть сетей). Визуализация сделана с помощью программного обеспечения [ http://muxviz.net/ muxViz

Общая формулировка в терминах тензоров

В то время как одномерные сети имеют двумерные матрицы смежности размера, в многомерной сети с измерениями матрица смежности становится многослойным тензором смежности, четырехмерной матрицей размера. Используя индексную нотацию, матрицы смежности могут обозначаться значком для кодирования соединений между узлами и, в то время как многослойные тензоры смежности обозначаются значком, для кодирования соединений между узлом на уровне и узлом на уровне. Как и в случае с одномерными матрицами, эта структура легко адаптирует направленные ссылки, ссылки со знаком и веса. ${\ Displaystyle V \ раз V}$${\ displaystyle D}$${\ Displaystyle (V \ раз D) \ раз (V \ раз D)}$ ${\ displaystyle A_ {j} ^ {i}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle M_ {j \ beta} ^ {i \ alpha}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle j}$${\ displaystyle \ beta}$

В случае мультиплексных сетей, которые представляют собой особые типы многослойных сетей, в которых узлы не могут быть взаимосвязаны с другими узлами на других уровнях, трехмерной матрицы размера с элементами достаточно для представления структуры системы путем кодирования соединений между узлами. и в слое. ${\ Displaystyle (V \ раз V) \ раз D}$${\ displaystyle A_ {ij} ^ {\ alpha}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ alpha}$

Мультиплексная социальная сеть саги «Звездные войны». Каждый слой обозначает отдельный эпизод, и два узла связаны друг с другом, если соответствующие персонажи действовали вместе в одной или нескольких сценах. Визуализация с помощью программы muxViz

Многослойные соседи

В многомерной сети все соседи какого-либо узла являются узлами, соединенными в разных измерениях. ${\ displaystyle v}$${\ displaystyle v}$

Длина многослойного пути

Путь между двумя узлами в многомерной сети может быть представлен в виде вектора г, в котором я запись в г есть число звеньев, проходимых в м измерения. Как и в случае степени перекрытия, сумму этих элементов можно принять как грубую меру длины пути между двумя узлами. ${\ displaystyle = (r_ {1}, \ dots r_ {| D |})}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle G}$

Сеть слоев

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

Сеть слоев в многослойных системах

Сеть слоев обычно имеет весовые коэффициенты (и может быть направлена), хотя, как правило, весовые коэффициенты зависят от интересующего приложения. Простой подход - для каждой пары слоев суммировать все веса в соединениях между их узлами, чтобы получить веса ребер, которые можно закодировать в матрицу. Тензор смежности ранга 2, представляющий нижележащую сеть слоев в пространстве, задается выражением ${\ displaystyle q _ {\ alpha \ beta}}$${\ Displaystyle \ mathbb {R} ^ {L \ times L}}$

${\ Displaystyle \ Psi _ {\ delta} ^ {\ gamma} = \ sum \ limits _ {\ alpha, \ beta = 1} ^ {L} q _ {\ alpha \ beta} E _ {\ delta} ^ {\ gamma } (\ альфа \ бета)}$

где - каноническая матрица, все компоненты которой равны нулю, за исключением записи, соответствующей строке и столбцу, равной единице. Используя тензорную запись, можно получить (взвешенную) сеть слоев из тензора многослойной смежности как. ${\ Displaystyle Е _ {\ дельта} ^ {\ гамма} (\ альфа \ бета)}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ Psi _ {\ delta} ^ {\ gamma} = M_ {j \ delta} ^ {i \ gamma} U_ {i} ^ {j}}$

Степень

В несвязанной многомерной сети, где отсутствуют межуровневые связи, степень узла представлена ​​вектором длины. Вот альтернативный способ обозначения количества слоев в многослойных сетях. Однако для некоторых вычислений может быть более полезным просто суммировать количество ссылок, смежных с узлом, по всем измерениям. Это перекрытие степени:. Как и в случае с одномерными сетями, можно аналогичным образом различать входящие и исходящие ссылки. Если присутствуют межслойные связи, приведенное выше определение должно быть адаптировано для их учета, а степень многослойности определяется выражением ${\ displaystyle | D |: \ mathbf {k} = (k_ {i} ^ {1}, \ dots k_ {i} ^ {| D |})}$${\ displaystyle | D |}$${\ displaystyle L}$${\ Displaystyle \ сумма _ {\ альфа = 1} ^ {| D |} k_ {я} ^ {\ альфа}}$

${\ Displaystyle к ^ {я} = M_ {j \ beta} ^ {i \ alpha} U _ {\ alpha} ^ {\ beta} u ^ {j} = \ sum _ {\ alpha, \ beta = 1} ^ {L} \ sum _ {j = 1} ^ {N} M_ {j \ beta} ^ {i \ alpha}}$

где все компоненты тензоров и равны 1. Неоднородность количества соединений узла на разных уровнях может быть учтена с помощью коэффициента участия. ${\ Displaystyle U _ {\ alpha} ^ {\ beta}}$${\ displaystyle u ^ {j}}$

Универсальность как многослойная центральность

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

Универсальность собственных векторов

Что касается одномерных сетей, универсальность собственных векторов может быть определена как решение проблемы собственных значений, заданной формулой, где для простоты используется соглашение Эйнштейна о суммировании. Здесь дается многослойное обобщение центральности собственного вектора Бонацича на узел на слой. Общая универсальность собственного вектора просто получается суммированием оценок по слоям как. ${\ displaystyle M_ {j \ beta} ^ {i \ alpha} \ Theta _ {i \ alpha} = \ lambda _ {1} \ Theta _ {j \ beta}}$ ${\ displaystyle \ Theta _ {j \ beta} = \ lambda _ {1} ^ {- 1} M_ {j \ beta} ^ {i \ alpha} \ Theta _ {i \ alpha}}$${\ Displaystyle \ тета _ {я} = \ Тета _ {я \ альфа} и ^ {\ альфа}}$

Кац универсальность

Что касается его одномерного аналога, универсальность Кац получают в виде раствора в тензорном уравнении, где, является постоянным меньше наибольшим собственным значением и является другой константой обычно равно 1. Общая Katz универсальность просто получаются путем суммирования баллов по слоям как. ${\ displaystyle \ Phi _ {j \ beta} = [(\ delta -aM) ^ {- 1}] _ {j \ beta} ^ {i \ alpha} U_ {i \ alpha}}$${\ displaystyle \ Phi _ {j \ beta} = AM_ {j \ beta} ^ {i \ alpha} \ Phi _ {i \ alpha} + bu_ {j \ beta}}$${\ displaystyle \ delta _ {j \ beta} ^ {i \ alpha} = \ delta _ {j} ^ {i} \ delta _ {\ beta} ^ {\ alpha}}$${\ displaystyle a}$${\ displaystyle b}$${\ Displaystyle \ phi _ {я} = \ Phi _ {я \ альфа} и ^ {\ альфа}}$

HITS универсальность

Для одномерных сетей алгоритм HITS был первоначально введен Джоном Клейнбергом для оценки веб-страниц. Основное предположение алгоритма состоит в том, что соответствующие страницы, названные властями, указываются специальными веб-страницами, названными концентраторами. Этот механизм можно математически описать двумя связанными уравнениями, которые сводятся к двум задачам на собственные значения. Когда сеть неориентирована, авторитетность и центральность концентратора эквивалентны центральности по собственному вектору. Эти свойства сохраняются за счет естественного расширения уравнений, предложенных Клейнбергом, на случай взаимосвязанных многослойных сетей, задаваемых и, где указывает оператор транспонирования и указывают центральность концентратора и органа власти, соответственно. Сужая тензоры концентратора и авторитета, можно получить общую универсальность как и, соответственно. ${\ displaystyle (MM ^ {t}) _ {j \ beta} ^ {i \ alpha} \ Gamma _ {i \ alpha} = \ lambda _ {1} \ Gamma _ {j \ beta}}$${\ displaystyle (M ^ {t} M) _ {j \ beta} ^ {i \ alpha} \ Upsilon _ {i \ alpha} = \ lambda _ {1} \ Upsilon _ {j \ beta}}$${\ displaystyle t}$${\ displaystyle \ Gamma _ {я \ альфа}}$${\ displaystyle \ Upsilon _ {я \ альфа}}$${\ Displaystyle \ гамма _ {я} = \ гамма _ {я \ альфа} и ^ {\ альфа}}$${\ Displaystyle \ ипсилон _ {я} = \ Ипсилон _ {я \ альфа} и ^ {\ альфа}}$

Универсальность PageRank

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

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

Случайные блуждания были определены также в случае взаимосвязанных многослойных сетей и мультиграфов с разноцветными краями (также известных как мультиплексные сети). Для взаимосвязанных многослойных сетей тензор переходов, управляющий динамикой случайных блуждающих устройств внутри и между слоями, задается выражением, где - константа, обычно равная 0,85, - это количество узлов, а - количество слоев или измерений. Здесь можно было бы назвать тензор Google и это тензор ранга 4 со всеми компонентами, равными 1. ${\ displaystyle R_ {j \ beta} ^ {i \ alpha} = rT_ {j \ beta} ^ {i \ alpha} + {\ frac {(1-r)} {NL}} u_ {j \ beta} ^ {i \ alpha},}$${\ displaystyle r}$${\ displaystyle N}$${\ displaystyle L}$${\ displaystyle R_ {j \ beta} ^ {i \ alpha}}$${\ Displaystyle и_ {дж \ бета} ^ {я \ альфа}}$

Как его одномерный аналог, универсальность PageRank состоит из двух составляющих: один кодирует классическое случайное блуждание со скоростью, а другой кодирует телепортацию между узлами и уровнями со скоростью. ${\ displaystyle r}$${\ displaystyle 1-r}$

Если мы указываем на в eigentensor тензора Google, обозначая стационарную вероятность найти ходок в узле и слой, многослойная PageRank получается путем суммирования над слоями eigentensor:${\ displaystyle \ Omega _ {я \ альфа}}$ ${\ displaystyle R_ {j \ beta} ^ {i \ alpha}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ Displaystyle \ omega _ {я} = \ Omega _ {я \ альфа} и ^ {\ альфа}}$

Дополнительная информация: триадное закрытие.

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

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

Максимизация модульности

Обобщение хорошо известного метода максимизации модульности для открытия сообщества было первоначально предложено Mucha et al. Этот метод множественного разрешения предполагает трехмерное тензорное представление сетевого соединения внутри слоев, как для мультиграфов с краями, и трехмерное тензорное представление сетевого соединения между слоями. Это зависит от параметра разрешения и веса межслойных соединений. В более компактной нотации, используя тензорную нотацию, модульность может быть записана как, где, - многослойный тензор смежности, - это тензор, кодирующий нулевую модель, а значение компонентов определяется как 1, когда узел в слое принадлежит определенному сообществу, помеченному индексом, и 0, если это не так. ${\ displaystyle \ gamma}$${\ displaystyle \ omega}$${\ displaystyle Q \ propto S_ {i \ alpha} ^ {a} B_ {j \ beta} ^ {i \ alpha} S_ {a} ^ {j \ beta}}$${\ displaystyle B_ {j \ beta} ^ {i \ alpha} = M_ {j \ beta} ^ {i \ alpha} -P_ {j \ beta} ^ {i \ alpha}}$${\ displaystyle M_ {j \ beta} ^ {i \ alpha}}$${\ displaystyle P_ {j \ beta} ^ {i \ alpha}}$${\ Displaystyle S_ {а} ^ {я \ альфа}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle a}$

Тензорная декомпозиция

Неотрицательная матричная факторизация была предложена для извлечения структуры активности сообщества временных сетей. Многослойная сеть представлена ​​трехмерным тензором, подобным мультиграфу с краями, где порядок слоев кодирует стрелку времени. Таким образом, тензорная факторизация с помощью декомпозиции Крускала применяется для назначения каждого узла сообществу во времени. ${\ displaystyle T_ {ij} ^ {\ tau}}$${\ displaystyle T_ {ij} ^ {\ tau}}$

Статистические выводы

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

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

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

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

Степенные корреляции

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

Доминирование пути

Учитывая два многомерных пути, r и s, мы говорим, что r доминирует над s тогда и только тогда, когда: и так, что. ${\ displaystyle \ forall d \ in \ langle 1, | D | \ rangle, r_ {l} \ leq s_ {l}}$${\ Displaystyle \ существует я}$${\ displaystyle r_ {l} lt;s_ {l}}$

Обнаружение кратчайшего пути

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

Многомерное расстояние

Один из способов оценить расстояние между двумя узлами в многомерной сети - это сравнить все многомерные пути между ними и выбрать подмножество, которое мы определяем как преобладание кратчайших промежуточных путей: пусть будет набором всех путей между и. Тогда расстояние между и представляет собой набор таких путей, что доминирует. Таким образом, длина элементов в наборе кратчайших путей между двумя узлами определяется как многомерное расстояние. ${\ Displaystyle MP (и, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ Displaystyle P \ substeq MP}$${\ displaystyle \ forall p \ in P, \ nexists p '\ in MP}$${\ displaystyle p '}$${\ displaystyle p}$

Актуальность измерения

В многомерной сети, актуальность данной размерности (или набора размеров) для одного узла может быть оценена соотношением:. ${\ Displaystyle G = (V, E, D)}$${\ displaystyle D '}$${\ displaystyle {\ frac {{\ text {Neighbours}} (v, D ')} {{\ text {Neighbours}} (v, D)}}}$

Связь измерений

В многомерной сети, в которой разные измерения соединения имеют разные реальные значения, представляет интерес статистика, характеризующая распределение ссылок на различные классы. Таким образом, полезно рассмотреть два показателя, которые оценивают это: возможность подключения измерения и возможность подключения измерения исключительно на границе. Первый из них является просто отношением общего количества звеньев в данном измерении к общему числу звеньев в каждом измерении:. Последние оценивает, для данного измерения, число пар узлов связаны только звено в этом измерении:. ${\ displaystyle {\ frac {| \ {(u, v, d) \ in E | u, v \ in V \} |} {| E |}}}$${\ Displaystyle {\ гидроразрыва {| \ {(и, v, d) \ в Е | и, v \ в V \ клин \ forall j \ в D, j \ neq d: (и, v, j) \ notin E \} |} {| \ {(u, v, d) \ в E | u, v \ in V \} |}}}$

Обнаружение пакетов

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

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

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

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

Процесс диффузионной реакции в многослойной системе изучался Lazaridis et al. Обнаружено, что для процесса, когда A и B изначально находятся в разных слоях, затем они рассеиваются случайным образом, а при встрече оба исчезают. Было обнаружено, что в этой модели из-за реакции возникает своего рода отталкивание между A и B, которое задерживает их смешивание и, следовательно, их реакцию. ${\ displaystyle A + B \ rightarrow 0}$

Случайные прогулки

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

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

В случае взаимосвязанных многоуровневых систем вероятность перехода от узла в слое к узлу в слое может быть закодирована в тензор перехода ранга 4, а переход в дискретном времени может быть описан главным уравнением ${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle j}$${\ displaystyle \ beta}$${\ displaystyle T_ {j \ beta} ^ {i \ alpha}}$

${\ displaystyle p_ {j \ beta} (t + 1) = \ sum _ {\ alpha = 1} ^ {L} \ sum _ {i = 1} ^ {N} T_ {j \ beta} ^ {i \ альфа} p_ {i \ alpha} (t) = \ sum _ {\ alpha = 1} ^ {L} \ sum _ {i = 1} ^ {N} (T ^ {t}) _ {j \ beta} ^ {я \ альфа} p_ {я \ альфа} (0)}$

где указывает вероятность нахождения пешехода в узле в слое в определенный момент времени. ${\ Displaystyle р_ {я \ альфа} (т)}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle t}$

Есть много разных типов прогулок, которые можно закодировать в тензор переходов, в зависимости от того, как ходячим разрешено прыгать и переключаться. Например, ходунок может либо прыгнуть, либо переключиться за один временной шаг, не различая межуровневые и внутриуровневые связи ( классическое случайное блуждание), или он может выбрать либо остаться в текущем слое и прыгнуть, либо переключить слой и затем перейти к другому узлу на том же временном шаге ( физическое случайное блуждание). Более сложные правила, соответствующие конкретным задачам, которые необходимо решить, можно найти в литературе. В некоторых случаях можно аналитически найти стационарное решение основного уравнения. ${\ displaystyle T_ {j \ beta} ^ {i \ alpha}}$

Классическая диффузия

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

${\ displaystyle {\ frac {dX_ {j \ beta} (t)} {dt}} = - L_ {j \ beta} ^ {i \ alpha} X_ {i \ alpha} (t)}$

где - количество рассеиваемого количества за один раз в узле в слое. Тензор ранга 4, управляющий уравнением, является тензором Лапласа, обобщающим комбинаторную матрицу Лапласа одномерных сетей. Стоит отметить, что в нетензорной записи уравнение принимает более сложный вид. ${\ Displaystyle X_ {я \ альфа} (т)}$${\ displaystyle t}$${\ displaystyle i}$${\ displaystyle \ alpha}$

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

Информация и распространение эпидемий

См. Также: эпидемиология

В последнее время вопрос о том, как информация (или болезни) распространяется через многослойную систему, стал предметом интенсивных исследований.

Проникновение многослойных взаимозависимых сетей

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

Взаимозависимость с сообществами

Многослойные взаимозависимые сети (см. Рисунок) изучались также при наличии сообществ внутри различных сетей. Для пространственных сообществ в многомерных взаимозависимых сетях см. Vaknin et al.

Изучаем две возможные конфигурации сети сетей. (а) древовидная сеть сетей с полной связью и двунаправленными зависимыми ссылками и (б) петлеобразная сеть сетей с долей зависимых узлов q и однонаправленными зависимыми ссылками. Как в (a), так и в (b) связи зависимости ограничены так, что они соединяют узлы только в пределах одних и тех же сообществ, то есть узел в модуле ma в сети i будет зависеть от узла также в модуле ma в сети j. (c) Демонстрация зависимости между парой взаимозависимых сетей, показанных в (a) и (b). Зависимость между одними и теми же сообществами в разных сетях (одинаковые цвета).

Динамическая взаимозависимость в многослойных сетях

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

• muxViz, бесплатная и эффективная среда для анализа и визуализации многослойных сетей, основанная на R [1]
• Библиотека многослойных сетей для Python (Pymnet) от Микко Кивеля
• MAMMULT показатели и модель для сетей многослойных (набор коды C / Python)
• Код GenLouvain MATLAB для обнаружения сообщества на основе максимизации мультисрезовой модульности
• Библиотека Multinet R и C ++ для анализа многослойных сетей.