18.6: Наближення середнього поля в безмасштабних мережах

Що робити, якщо топологія мережі дуже неоднорідна, як у безмасштабних мережах, так що випадкове припущення мережі більше не застосовується? Природним способом узгодження такої гетерогенної топології та наближення середнього поля є прийняття конкретного ступеня розподілу\(P(k)\). Це все ще непросторовий підсумок зв'язків всередині мережі, але ви можете захопити деякі неоднорідні аспекти топології в\(P(k)\).

Одне додаткове ускладнення, яке приносить розподіл ступенів, полягає в тому, що, оскільки вузли тепер відрізняються один від одного щодо своїх ступенів, вони також можуть відрізнятися один від одного щодо розподілу їх стану. Іншими словами, вже не розумно припускати, що ми можемо представляти глобальний стан мережі єдиним «середнім полем»\(q\). Замість цього нам потрібно буде представляти\(q\) як функцію ступеня\(k\) (тобто купу середніх полів, кожне для конкретного\(k\)), оскільки сильно пов'язані вузли можуть заражатися частіше, ніж погано пов'язані вузли. Отже, ось короткий виклад нових величин, які нам потрібно включити в наближення:

•\(P(k)\): Імовірність вузлів зі ступенем\(k \)

•\(q(k)\): Імовірність зараження вузла\(k\) зі ступенем

Розглянемо, як переглянути таблицю 18.5 .1 за допомогою\(P(k)\) і\(q(k)\). Очевидно, що всі повинні бути замінені на\(q(k)\).\(q\) Також очевидно, що третій і четвертий ряд (ймовірності переходів для інфікованих на даний момент станів) не зміняться, оскільки вони просто засновані на ймовірності відновлення\(p_r\). А другий ряд можна легко отримати, як тільки вийде перший ряд. Отже, ми можемо просто зосередитись на обчисленні ймовірності в першому рядку: Яка ймовірність того, що чутливий вузол зі ступенем\(k\) залишиться сприйнятливим на наступному часовому кроці?

Ми можемо використовувати ту саму стратегію, що і для випадкового випадку мережі. Тобто обчислюємо ймовірність зараження вузла з іншого вузла, а потім обчислюємо один мінус, який підвищується до потужності кількості сусідів, щоб отримати ймовірність для вузла уникнути будь-якого зараження. Для випадкових мереж всі інші вузли були потенційними сусідами, тому нам довелося підняти (\(1−p_{e}qp_{i}\)) до потужності\(n−1\). Але в цьому вже немає необхідності, тому що ми зараз обчислюємо ймовірність для вузла з конкретним ступенем\(k\). Отже, ймовірність того, що перейде в перший рядок таблиці, повинна виглядати так:

\[1-(q(k))(1- something)^{k} \label{(18.29)} \]

Тут «щось» - це спільна ймовірність двох подій, що сусідський вузол заражений хворобою і що хвороба насправді передається розглянутому вузлу. Останнє все ще\(p_i\), але перше більше не представлено єдиним середнім полем. Потрібно розглянути всі можливі ступені, які може мати сусід, а потім агрегувати їх усі, щоб отримати загальну середню ймовірність того, що сусід опиниться в зараженому стані. Отже, ось більш опрацьована ймовірність:

\[(1-q(k))(1- \sum){k'} P_{n}(k'|k)q(k')p_i)^{k} \label{(18.30)} \]

Тут,\(k'\) є ступінь сусіда, і підсумовування буде проводитися для всіх можливих значень\(k'\). \(P_{n}(k'|k)\)є умовною ймовірністю для сусіда вузла з градусом\(k\), щоб мати ступінь\(k'\). Це може бути будь-який розподіл ймовірностей, який може представляти асортативну або дисортативну топологію мережі. Але якщо припустити, що мережа не є ні асортативною, ні дисортативною, то\(P_{n}(k'|k)\))\(k\) зовсім не залежить, тому стає просто\(P_{n}(k')\): розподіл сусідніх ступенів.

Зачекайте хвилинку. Чи справді нам потрібен такий спеціальний розподіл для ступенів сусідів? Зрештою, сусіди - це звичайні вузли, тому чи не можемо ми використовувати оригінальний розподіл градусів\(P(k')\) замість\(P_{n}(k')\)? Як би дивно це не звучало, відповідь - дивовижне НІ. Це одне з найбільш загадкових явищ в мережах, але ваші сусіди - не зовсім звичайні люди. Середній ступінь сусідів насправді вище середнього ступеня всіх вузлів, що часто формулюється як «у ваших друзів більше друзів, ніж у вас». Як коротко обговорювалося в розділі 16.2, це називається парадокс дружби, про який вперше повідомив соціолог Скотт Фельд на початку 1990-х років [68].

Ми можемо аналітично отримати розподіл сусідніх ступенів для неасортативних мереж. Уявіть, що ви випадковим чином вибираєте одне ребро з мережі, простежуєте його до одного з кінцевих вузлів і вимірюєте його ступінь. Якщо ви повторюєте це багато разів, то розподіл, який ви отримуєте, - розподіл сусідніх градусів. Ця операція по суті полягає у випадковому виборі однієї «руки», тобто половини краю, з усієї мережі. Загальна кількість рук, прикріплених до вузлів з градусом\(k'nP(k')\),\(k'\) задається, і якщо ви підсумуєте це за все\(k'\), ви отримаєте загальну кількість рук в мережі. Тому, якщо вибірка є чисто випадковою, ймовірність для сусіда (тобто вузла, прикріпленого до випадково обраної руки), щоб мати ступінь,\(k'\) задається

\[P_{n}(k') =\frac{k'nP(k')}{\sum_{k}k'mP(k')} =\frac{k'P(k')}{\sum_{k'}k'P(k')}=\frac{k'}{\langle{k} \rangle}P(k'), \label{(18.31)} \]

де\(\langle{k} \rangle\) - середня ступінь. Як ви можете чітко бачити в цьому результаті, розподіл сусідніх ступенів - це модифікований розподіл градусів, щоб він був пропорційним градусу\(k'\). Це показує, що вузли вищого ступеня мають більше шансів з'явитися як сусіди. Якщо обчислити середню ступінь сусіда\(\langle{k_n} \rangle\), то отримаємо

\[\langle{k_n} \rangle =\sum_{k'}{k'P_{n}(k')}= \sum_{k'}\frac{k'^{2}P(k')}{\langle{k} \rangle} =\frac{\langle{k^{2}} \rangle}{\langle{k} \rangle} =\frac{\langle{k} \rangle^{2}+\sigma{(k)^{2}}}{\langle{k} \rangle} = \langle{k} \rangle +\frac{\sigma (k)^{2}}{\langle{k} \rangle}, \label{(18.32)} \]

де\(σ(k)^{2}\) - дисперсія розподілу ступенів. Це математично показує, що якщо є якісь відхилення в розподілі ступенів (що вірно практично для всіх мереж реального світу), у ваших друзів більше друзів, ніж у вас, в середньому. Це може бути трохи пригнічує, але вірно. Просто зіткніться з цим.

Гаразд, вистачить парадоксу дружби. Давайте підключимо рівняння\ ref {(18.31)} назад до рівняння\ ref {(18.30)}, що дає

\[(1-q(k))(1- \sum_{k'}\frac{k'}{\langle{k} \rangle} P(k')q(k')p_{i})^{k}. \label{(18.33)} \]

Цим ми можемо остаточно завершити таблицю ймовірності переходу стану, як показано в таблиці 18.6.1.

Таблиця\(\PageIndex{1}\): Можливі сценарії переходів стану в мережевій моделі SIS, з розподілом ступенів\(P(k)\) і залежною від ступеня ймовірності зараження\(q(k)\).

Поточний стан	Наступний стан	Імовірність такого переходу
0 (сприйнятливий)	0 (сприйнятливий)	\[(1-q(k))(1- \sum_{k'}\frac{k'}{\langle{k} \rangle} P(k')q(k')p_{i})^{k} \nonumber \]
0 (сприйнятливий)	1 (інфікований)	\[(1-q(k))(1- (1- \sum_{k'}\frac{k'}{\langle{k} \rangle} P(k')q(k')p_{i})^{k}) \nonumber \]
1 (інфікований)	0 (сприйнятливий)	\[q(k)p_{r} \nonumber \]
1 (інфікований)	1 (інфікований)	\[q(k)()1-p_{r} \nonumber \]

Ми можемо додати ймовірності переходів стану, які перетворюють наступний стан в 1, щоб отримати різницеве рівняння для\(q_{t}(k)\) (знову ж таки, індекси опущені з правого боку), т. Е.

\[\begin{align} q_{t+1}(k)=(1-q(k))(1-q(k))(1- (1- \sum_{k'}\frac{k'}{\langle{k} \rangle} P(k')q(k')p_{i})^{k}) +q(k)(1-p_{r}) \label{(18.34)} \\ = (1-q(k))(1-(1-q_{n}p_{i})^{k})+q(k)(1-p_{r}) \end{align} \label{(18.35)} \]

із

\[q_{n} =\frac{\sum_{k'}k'P(k')q(k')}{\langle{k}\rangle}. \label{(18.36)} \]

\(q_n\)ймовірність того, що сусідський вузол заражений хворобою. Таким чином\(q_np_i\) відповідає частині «щось» в Equation\ ref {(18.29)}. Він може приймати будь-яке значення від 0 до 1, але для нашої мети вивчення епідемічного порогу ймовірності зараження ми можемо припустити, що\(q_np_i\) це мало. Тому, використовуючи наближення\((1−x)^{k} ≈ 1−kx\) для малого\(x\) знову, ітераційна карта вище стає

\[\begin{align} q_{t+1}=(1-q(k)) (1-(1-kq_{n}p_{i})) +q(k)(1-p_{r}) \label{(18.37)} \\ = (1-q(k)) kq_{n}p_{i}+p(k)-q(k)p_{r} =f(q(k)). \label{(18.38)} \end{align} \]

Потім ми можемо обчислити рівноважний стан вузлів зі ступенем\(k\) наступним чином:

\[q_{eq}(k)=(q- q_{eq}(k))kq_{n}p_{i}+ q_{eq}(k)-q_{eq}(k)p_{r} \label{(18.39)} \]

\[q_{eq}p_{r} =kq_{n}p_{i}-kq_{n}p_{i}q_{eq}(k)\label{(18.40)} \]

\[q_{eq} (k)=\frac{kq_{n}p_{i}}{kq_{n}p_{i}+p_{r}} \label{(18.41)} \]

Ми можемо застосувати це назад до визначення,\(q_n\) щоб знайти фактичний стан рівноваги:

\[q_{n} =\frac{1}{\langle{k} \rangle}\sum_{k'}k'P(k') \frac{kq_{n}p_{i}}{kq_{n}p_{i}+p_{r}} \label{(18.42)} \]

Ясно,\(q_n = 0\) (тобто\(q_{eq}(k) = 0\) для всіх\(k\)) задовольняє це рівняння, тому згасання хвороби - це все-таки рівноважний стан цієї системи. Але те, що нас цікавить, так це рівновага з\(q_n \neq{ 0 }\) (тобто\(q_{eq}(k) > 0\) для деяких\(k\)), де хвороба продовжує існувати, і ми хочемо знати, чи є такий стан стабільним. Щоб розв'язати Equation\ ref {(18.42)}, нам потрібно буде припустити певний розподіл ступенів\(P(k)\).

Наприклад, якщо припустити, що мережа велика і випадкова, ми можемо використовувати наступний грубий приблизний розподіл градусів:

\[P(k) \approx \begin{cases} 1 \text{ if } k =\langle{k}\rangle \label{(18.43)} \\ 0 \text{otherwise} \end{cases} \]

Ми можемо використовувати це наближення, оскільки зі збільшенням розміру мережі розподіл ступеня випадкового графіка стає все більш концентрованим у середньому ступені (щодо розміру мережі), завдяки закону великих чисел, добре відомому в статистиці. Тоді рівняння\ ref {(18.42)} вирішується наступним чином:

\[q_{n}=\frac{\langle{k}\rangle {q_{n}}p_{i}}{\langle{k} \rangle {q_{n}}p_{i}+p_{r}} \label{(18.44)} \]

\[\langle{k} \rangle {q_{n}p_{i}+p_{r}} = \langle{k} \rangle{p_{i}} \label{(18.45)} \]

\[q_{n}=1-\frac{p_{r}}{ \langle{k} \rangle{p_{i}}} \label{(18.46)} \]

Ми можемо перевірити стабільність цього стану рівноваги, диференціюючи Equation\ ref {(18.38)},\(q(k)\) а потім застосувавши наведені вище результати. При цьому ми повинні мати на увазі, що\(q_n\) міститься\(q(k)\) в ньому (див. Рівняння\ ref {(18.36)}). Отже, результат повинен виглядати наступним чином:

\[\begin {align}\frac{df(q(k))}{dq(k)} =-kq_{n}p_{i} +(1-q(k))kp_{i}\frac{dq_{n}}{dq(k)} +1-p_{r} \label{(18.47)} \\ =-kq_{n}p_{i}+(1-q(k))\frac{k^{2}P(k)p_{i}}{\langle{k}\rangle} +1-p_{r} \label{(18.48)} \end{align} \]

При рівноважному стані Рівняння\ ref {(18.41)} це стає

\[\frac{df(q(k))}{dq(k)}|_{q(k)=\frac{kq_{n}p_{i}}{kq_{n}p_{i} +p_{r}}} =-kq_{n}p_{i} +\frac{p_{r}}{kq_{n}p_{i}+p_{r}} \frac{k^{2}P(k)p_{i}}{\langle{k}\rangle}+1-p_{r}=r(k). \label{(18.49)} \]

Потім, застосовуючи\(P(k)\) і\(q_n\) з обмеженням\(k → \langle{k}\rangle\) для великих випадкових мереж, отримаємо

\[\begin{align} r(\langle{k}\rangle) =-\langle{k}\rangle(1-\frac{p_{r}}{\langle{k}\rangle{p_{i}}})p_{i}+\frac{p_{r}}{\langle{k}\rangle(1-\frac{p_{r}}{\langle{k}\rangle{p_{i}}})p_{i}+p_{r}} \frac{\langle{k}\rangle^{2}p_{i}}{\langle{k}\rangle} + -p_{r} \label{(18.50)} \\ =- \langle{k}\rangle{p_{i}} +p_{r}+p_{r}+1-p_{r} \label{(18.51)} \\ =-\langle{k}\rangle{p_{i}}+p_{r}+1. \label{(18.52)} \end{align} \]

Для того щоб ненульовий стан рівноваги було стабільним:
\[-1<- \langle{k}\rangle {p_{i}}+p_{r}+1<1 \label{(18.53)} \]

\[\frac{p_{r}}{\langle{k}\rangle}< p_{i} < \frac{p_{r}+2}{\langle{k}\rangle} \label{(18.54)} \]

Зверніть увагу, що нижня межа, зазначена вище, така ж, як і епідемічний поріг, який ми отримували у випадкових мережах раніше (ур. (18.5.18)). Отже, здається, наш аналіз поки що послідовний. А для вашої інформації верхня межа, зазначена вище, є ще одним критичним порогом, при якому це ненульовий стан рівноваги втрачає стабільність і система починає коливатися.

Що станеться, якщо мережа не масштабується? Тут припустимо, що мережа - це безмасштабна мережа Barab'asi-Albert, ступінь розподілу якої, як відомо,\(P(k) = 2m^{2}k^{−3}\) де\(m\) число ребер, за якими кожен новачок вузол приєднаний до мережі, а отже\(\langle{k}\rangle = 2m\) і\(k_{min} = m\) [57]. Потім з Рівняння\ ref {(18.42)} ¹ отримаємо

\[q_{n} =\frac{1}{2m} \sum_{k'=m}^{\infty} k' \cdot 2m^{2}k'^{-3}\frac{k'q_{n}p_{i}}{k'q_{n}p_{i}+p_{r}} \label{(18.55)} \]

\[1=mp_{i} \sum_{k'=m}^{\infty} \frac{1}{k'(k'q_{n}p_{i}+p_{r})}.\label{(18.56)} \]

Підсумовування може бути наближений неперервним інтегралом, що призводить до

\[\begin{align} 1 \approx mp_{i} \int^{\infty}_{m} \frac{dk'}{k'(k'q_{n}p_{i}+p_{r})} \label{(18.57)} \\ = \frac{mp_{i}}{p_{r}} \int^{\infty}_{m} (\frac{1}{k'}-\frac{1}{k'+ p_{r}/(q_{n}p_{i})})dk' \label{(18.58)} \\ =\frac{mp_{i}}{p_{r}} [\log{(\frac{k'}{k'+p_{r/(q_{n}p_{i})}})}]^{\infty}_{m} \\ = \frac{mp_{i}}{p_{r}} \log{(1+\frac{p_{r}}{mq_{n}p_{i}})}, \label{(18.60)} \\ q_{n} \approx \frac{p_{r}}{(e^{\frac{p_{r}}{mp_{i}}} -1)mp_{i}}. \label {(18.61)} \end{align} \]

Ми можемо застосувати цей результат (разом з\(P(k) = 2m^{2}k^{−3})\) to\(r(k)\) in Equation\ ref {(18.49)} для перевірки стійкості цього ненульового стану рівноваги:

\[\begin{align} r(k)=-k \frac{p_{r}}{(e^{\frac{p_{r}}{mp_{i}}} -1 mp_{i})}p_{t}+\frac{p_{r}}{k \frac{p_{r}}{(e^{\frac{p_{r}}{mp_{i}}} -1)mp_{i}}p_{i}+p_{r}} \\ = - \frac { k p _ { r } } { \left( e ^ { \frac { p _ { r } } { m p _ { i } } } - 1 \right) m } + \frac { m p _ { i } } { \left( e ^ { \frac { p r } { m _ { i } } } - 1 \right) m } + 1 - p _ { r } \label{(18.63)}\end{align} \]

Це досить складно, і вирішити його в плані було б складно\(p_i\). Але все ж, ми можемо показати щось дуже цікаве, використовуючи цю формулу. Якщо\(p_i\) знизити ймовірність зараження до нуля, це відбувається асимптотично:

\[\begin{align} \lim _ { p _ { i } \rightarrow 0 } r ( k ) = - \frac { k p _ { r } } { ( \left[ e ^ { \frac { p _ { r } } { m p _ { i } } } \rightarrow \infty \right] m } + \frac { m \left[ p _ { i } \rightarrow 0 \right] } { ( \left[ e ^ { \frac { p _ { r } } { m p _ { i } } \rightarrow \infty } \right] - k } + 1 - p _ { r } \label{(18.64)} \\ 1-p_{r} \end{align} \]

Це показує\(0 < lim_{pi→0} r(k) < 1\), тобто ненульовий стан рівноваги залишається стабільним, навіть якщо\(p_i\) наближається до нуля. Іншими словами, немає епідемічного порогу, якщо мережа не масштабується! Цей глибокий результат був виявлений статистичними фізиками Ромуальдо Пастор Саторрас та Алессандро Веспіньяні на початку 2000-х років [79], що ілюструє важливий факт, що в мережах, топології яких не мають масштабу, хвороби можуть затримуватися на невизначений час, якою б слабкою не була їх інфекційність. Це чудовий приклад того, як складні мережеві топології можуть кардинально змінити динаміку системи, а також ілюструє, наскільки іноді можуть вводити в оману прогнози, зроблені за допомогою випадкових моделей. Цей висновок та інші пов'язані теорії мають безліч реальних застосувань, таких як розуміння, моделювання та запобігання епідемій інфекційних захворювань у суспільстві, а також комп'ютерних вірусів в Інтернеті.

Вправа\(\PageIndex{1}\)

Імітуйте динаміку мережевої моделі SIS на безмасштабних мережах Барабасі Альберта, щоб перевірити, чи справді немає епідемічного порогу, як прогнозує теорія. У симуляціях на будь-яких кінцевих мережах завжди є можливість випадкового згасання захворювань, тому вам потрібно буде зробити розмір мережі якомога більшим, щоб мінімізувати цей ефект «кінцевого розміру». Слід порівняти результати з результатами, отриманими в результаті контрольних експериментів, які використовують випадкові мережі.

Нарешті, я повинен зазначити, що всі аналітичні методи, розглянуті вище, все ще досить обмежені, тому що ми не враховували жодної асортативності чи дизасортативності, будь-яких можливих кореляцій станів по краях або будь-якої коеволюційної динаміки, яка поєднує зміни стану та топологічні зміни. Реальні мережі часто включають такі складності вищого порядку. Для того, щоб краще їх захопити, існують більш досконалі аналітичні методи, такі як наближення пари та закриття моменту. Якщо ви хочете дізнатись більше про ці методи, є кілька детальніших технічних посилань [80, 81, 82, 83].

Вправа\(\PageIndex{2}\)

Розглянемо мережу з надзвичайно сильною асортативністю, щоб

\[P \left( k ^ { \prime } | k \right) \approx \left\{ \begin{array} { l l } { 1 } & { \text { if } k ^ { \prime } = k } \\ { 0 } & { \text { otherwise } } \end{array} \right. \label{(18.66)} \]

Використовуйте це нове визначення\(P(k'|k)\) in Equation\ ref {(18.30)}, щоб провести наближення середнього поля та визначити, чи має ця сильно асортативна мережа епідемічний поріг чи ні.

¹ Тут ми припускаємо, що мережі Барабасі-Альберта не є асортативними.