18.2: Дифузія в мережах

Last updated
Save as PDF

Page ID: 67420

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Багато важливих динамічних мережевих моделей можна сформулювати як лінійну динамічну систему. Перший приклад - рівняння дифузії в мережі, яке ми обговорювали в главі 16:

\[\frac{dc}{dt} =-\alpha{Lc} \label{(18.5)} \]
Це безперервна версія часу, але ви також можете написати еквівалент дискретного часу. Як ми обговорювали раніше,$L = D−A$ це лапласіанська матриця мережі. Це симетрична матриця, в якій діагональні компоненти є невід'ємними (представляють ступені вузла), тоді як інші компоненти є непозитивними. Ця матриця володіє деякими цікавими, корисними динамічними властивостями:

Лапласіанська матриця неспрямованої мережі має такі властивості:

Принаймні одне з його власних значень дорівнює нулю.
Всі інші власні значення є або нульовими, або додатними.
Число його нульових власних значень відповідає кількості підключених компонентів в мережі.
Якщо мережа підключена, то домінантним власнимвектором є вектор однорідності$h = (1 1 ...1)^{T}$ ^a.
Найменшим ненульовим власнимзначенням називають спектральний проміжок мережі, який визначає, наскільки швидко відбувається дифузія в мережі.

^a Навіть якщо мережа не підключена, ви все одно можете взяти вектор однорідності як одну з основ її домінуючого власного простору.

Перше властивість легко показати, тому що$Lh = (D −A)h = d−d = 0$, де$d$ знаходиться вектор, зроблений з ступенів вузла. Це означає, що$h$ можна прийняти як власний вектор, який відповідає власному значенню 0. Друге властивість походить від того, що матриця Лапласа є позитивно-напіввизначеною, тому що її можна отримати,$L = M^{T}M$ де$M$ знаходиться підписана матриця падіння мережі (не детально описана в цьому підручнику).

Щоб зрозуміти інші властивості, нам потрібно розглянути, як інтерпретувати власні значення матриці Лапласа. Фактична матриця коефіцієнтів рівняння дифузії є$−αL$, а її власні значення${λ_i}$ є${−αλ_i}$, де є$L$ власні значення. Відповідно до перших двох властивостей, розглянутих вище, матриця коефіцієнтів рівняння має принаймні одне власне значення 0, а всі власні значення 0 або від'ємні. Це означає, що нульове власне значення насправді є домінуючим в даному випадку, і його відповідний домінантний власний вектор ($h$або власний простір, якщо мережа не підключена) повідомить нам асимптотичний стан мережі.

Давайте розглянемо інші властивості. Третя властивість виникає інтуїтивно, тому що, якщо мережа складається з декількох підключених компонентів, кожен з цих компонентів поводиться як окрема мережа і показує дифузію самостійно, сходжуючись до іншої асимптотичної величини, а значить, асимптотичний стан всієї мережі повинно мати стільки ж ступеня свободи в якості з'єднаних компонентів. Це вимагає, щоб домінантний власний простір мав стільки вимірів, тому має бути стільки ж вироджених домінантних власних значень 0, скільки з'єднаних компонентів у мережі. Четверту властивість можна вивести, об'єднавши this з аргументом на властивість 1 вище.

І нарешті, спектральний проміжок. Він так називається тому, що список власнихзначень матриці називається матричним спектром в математиці. Спектральний проміжок є найменшим ненульовим власним значенням$L$, яке відповідає найбільшому ненульовому власному значенню$−αL$ і, отже, режиму стану мережі, який показує найповільніший експоненціальний розпад з часом. Якщо спектральний проміжок близький до нуля, це розпад займає дуже багато часу, в результаті чого відбувається повільна дифузія. Або якщо спектральний проміжок набагато вище нуля, розпад відбувається швидко, як і дифузія. У цьому сенсі спектральний розрив матриці Лапласа захоплює деякі топологічні аспекти мережі, тобто наскільки добре вузли з'єднані між собою з динамічної точки зору. Спектральний проміжок зв'язного графа (або, друге найменше власне значення матриці Лапласа загалом) називається алгебраїчною зв'язністю мережі.

Ось як отримати матрицю Лапласа та спектральний проміжок у NetworkX:

$Код 18.1pt1.PNG$

$Код 18.1пт 2.PNG$

Отже, спектральний проміжок (= алгебраїчна зв'язність в даному випадку) графа Карате Клубу становить близько 0,4685. Це значення не говорить нам багато про швидкість дифузії в цій мережі. Нам потрібно буде порівняти спектральні прогалини між різними топологіями мережі.

Вправа$\PageIndex{1}$

Рандомізуйте топологію графа Карате Клубу кілька разів і виміряйте їх спектральні прогалини. Порівняйте результат з вихідним значенням, отриманим вище, і обговоріть, що він означає з точки зору швидкості дифузії.

Вправа$\PageIndex{2}$

Створіть такі топології мережі з порівнянними розмірами та щільністю:

• випадковий графік

• графік штанги

• кільцеподібний графік (тобто регулярний граф 2 ступеня)

Виміряйте їх спектральні прогалини і подивіться, як топології кількісно впливають на швидкість дифузії.