Перегляд вихідного коду сторінки Користувач:Sawarad/Розподіл ступеня

{{Наука про мережі}}

При дослідженні [[Граф (математика)|графів]] та [[Складні мережі|мереж]] [[Степінь вершини (теорія графів)|ступінь]] вузла в мережі — це кількість зв’язків з іншими вузлами, а '''розподіл ступенів''' — це [[Розподіл імовірностей|розподіл ймовірностей]] цих ступенів по всій мережі.

== Визначення ==
[[Степінь вершини (теорія графів)|Ступінь]] вузла в мережі (іноді неправильно згадується як зв'язність) — це кількість з'єднань або [[Словник термінів теорії графів|ребер]] вузла з іншими вузлами. Якщо мережа [[Орієнтований граф|орієнтована]], що позначає, що якщо ребра вказують у напрямку з одного вузла до іншого, то вузли мають два різних ступені: вхідний ступінь, що дорівнює кількості вхідних ребер, та вихідний ступінь, що дорівнює кількості вихідних ребер.

Розподіл ступенів ''P''(''k'') мережі визначається як відношення кількості вузлів у мережі зі ступенем ''k'' до кількості всіх вузлів у цій мережі. Таким чином, якщо мережа складається з ''n'' вузлів і ''n''<sub>''k''</sub> з них мають ступінь ''k'', то маємо <math>P(k) = \frac{n_{k}}{n}</math> .

Ця інформація іноді представлена у вигляді ''кумулятивного розподілу ступенів'', частки вузлів зі ступенем, меншим за ''k'', або навіть ''додаткового кумулятивного розподілу ступенів'', частки вузлів зі ступенем який більший або дорівнює до ''k'', що позначається як (1 - ''C''), якщо розглядати ''C'' як ''сукупний розподіл ступенів''; тобто доповнення до ''C'' .

== Спостережувані розподіли ступенів ==
Розподіл ступенів є дуже важливим при вивченні як реальних мереж, таких як [[Інтернет]] та [[Список соціальних мереж|соціальні мережі]], так і теоретичних мереж. Найпростіша модель мережі — [[випадковий граф]] ([[модель Ердеша — Реньї]]), в якому кожен з ''n'' вузлів може бути незалежно пов’язаним (або ні) з ймовірністю ''p'' (або 1 − ''p''), має [[біноміальний розподіл]] ступенів ''k'' :

: <math>
P(k) = {n-1\choose k} p^k (1 - p)^{n-1-k},
</math>

(або [[Розподіл Пуассона|Пуассона]] в межах великого ''n'', якщо середній ступінь <math>\langle k\rangle=p(n-1)</math> є фіксованим). Однак більшість реальних мереж мають розподіл ступенів, що дуже відрізняються. Більшість із них мають значне [[Коефіцієнт асиметрії|відхиленна праворуч]], що позначає, що більша кількість вузлів мають низький ступінь, та лише невелика кількість, відома як «хаби», мають високий ступінь. Стверджувалося, що певні мережі, зокрема Інтернет, [[Всесвітнє павутиння|Всесвітня мережа]] та деякі соціальні мережі, мають розподіл ступенів, які приблизно відповідають [[Степеневий розподіл|степеневому закону]]: <math>
P(k)\sim k^{-\gamma}
</math>, де ''γ'' — константа. Такі мережі називаються [[Безмасштабна мережа|безмасштабними мережами]] та вони привертають особливу увагу своїми структурними та динамічними властивостями.<ref name="BA">{{Cite journal|last=Barabási|first=Albert-László|last2=Albert|first2=Réka|date=1999-10-15|title=Emergence of Scaling in Random Networks|journal=Science|volume=286|issue=5439|pages=509–512|arxiv=cond-mat/9910332|bibcode=1999Sci...286..509B|doi=10.1126/science.286.5439.509|issn=0036-8075|pmid=10521342}}</ref> <ref name="AB">{{Cite journal|last=Albert|first=Réka|last2=Barabási|first2=Albert-László|date=2000-12-11|title=Topology of Evolving Networks: Local Events and Universality|url=https://repository.library.northeastern.edu/files/neu:331099/fulltext.pdf|journal=Physical Review Letters|volume=85|issue=24|pages=5234–5237|arxiv=cond-mat/0005085|bibcode=2000PhRvL..85.5234A|doi=10.1103/physrevlett.85.5234|issn=0031-9007|pmid=11102229}}</ref> <ref name="Doro">{{Cite journal|last=Dorogovtsev|first=S. N.|last2=Mendes|first2=J. F. F.|last3=Samukhin|first3=A. N.|date=2001-05-21|title=Size-dependent degree distribution of a scale-free growing network|journal=Physical Review E|volume=63|issue=6|page=062101|arxiv=cond-mat/0011115|bibcode=2001PhRvE..63f2101D|doi=10.1103/physreve.63.062101|issn=1063-651X|pmid=11415146}}</ref> <ref name="PSY">{{Cite journal|last=Pachon|first=Angelica|last2=Sacerdote|first2=Laura|last3=Yang|first3=Shuyi|year=2018|title=Scale-free behavior of networks with the copresence of preferential and uniform attachment rules|journal=Physica D: Nonlinear Phenomena|volume=371|pages=1–12|arxiv=1704.08597|bibcode=2018PhyD..371....1P|doi=10.1016/j.physd.2018.01.005}}</ref> Однак дослідження широкого кола реальних мереж показує, що безмасштабні мережі, якщо їх оцінювати за допомогою точних статистичних показників зустрічаються рідко.<ref>{{Cite journal|last=Broido|first=Anna D.|last2=Clauset|first2=Aaron|date=2019-03-04|title=Scale-free networks are rare|journal=Nature Communications|language=en|volume=10|issue=1|pages=1017|doi=10.1038/s41467-019-08746-5|issn=2041-1723|pmc=6399239|doi-access=free}}</ref> Деякі дослідники заперечують ці висновки, стверджуючи, що визначення, які було використано у дослідженні, є невідповідно жорсткими,<ref>{{Cite journal|last=Voitalov|first=Ivan|last2=van der Hoorn|first2=Pim|last3=van der Hofstad|first3=Remco|last4=Krioukov|first4=Dmitri|date=18 October 2019|title=Scale-free networks well done|journal=Physical Review Research|volume=1|issue=3|pages=033034|doi=10.1103/PhysRevResearch.1.033034|doi-access=free}}</ref> в той час як інші стверджують, що точна функціональна форма розподілу ступенів менш важлива, ніж знання того, чи є розподіл ступенів [[Жирнохвостий розподіл|розподілом з товстим хвостом]] чи ні.<ref>{{Cite journal|last=Holme|first=Petter|date=2019-03-04|title=Rare and everywhere: Perspectives on scale-free networks|journal=Nature Communications|language=en|volume=10|issue=1|pages=1016|bibcode=2019NatCo..10.1016H|doi=10.1038/s41467-019-09038-8|issn=2041-1723|pmc=6399274|pmid=30833568}}</ref> Надмірну інтерпретацію конкретних форм розподілу ступенів також критикували за те, що вона не врахувувала, як мережі можуть розвиватися з часом.<ref>{{Cite journal|last=Falkenberg|first=Max|last2=Lee|first2=Jong-Hyeok|last3=Amano|first3=Shun-ichi|last4=Ogawa|first4=Ken-ichiro|last5=Yano|first5=Kazuo|last6=Miyake|first6=Yoshihiro|last7=Evans|first7=Tim S.|last8=Christensen|first8=Kim|date=18 June 2020|title=Identifying time dependence in network growth|journal=Physical Review Research|volume=2|issue=2|pages=023352|arxiv=2001.09118|doi=10.1103/PhysRevResearch.2.023352|doi-access=free}}</ref>

== Надмірний розподіл ступенів ==
Надмірний розподіл ступенів — це розподіл ймовірностей для вузла, досягнутого за ребром, кількості інших ребер, якi ведуть до цього вузла. <ref name=":0">{{Cite book
|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090
|title=Networks
|last=Newman
|first=Mark
|date=2018-10-18
|publisher=Oxford University Press
|volume=1
|language=en
|doi=10.1093/oso/9780198805090.001.0001
|isbn=978-0-19-880509-0
}}</ref> Іншими словами, це розподіл вихідних зв'язкiв вузла, досягнутого за зв'язком.

Припустимо, що мережа має розподіл ступенів <math>
P(k)
</math>, після вибору вузла (випадково чи ні) і переходу до одного з його сусідів (припускаючи, що він має принаймні одного сусіда), ймовірність того, що цей вузол матиме <math>
k
</math> сусідам не задається <math>
P(k)
</math>. Причиною цього є те, що кожен раз, коли якийсь вузол вибирається в гетерогенній мережі, більш ймовірно досягти хаб, дотримуючись одного з існуючих сусідів цього вузла. Істинна ймовірність того, що такі вузли мають ступінь <math>
k
</math> є <math>
q(k)
</math> яка називається ''надмірним'' ''ступенем'' цього вузла. У [[Модель конфігурації|моделі конфігурації]], кореляції між вузлами якої проігноровані і кожен вузол є з'єднаним з будь-якими іншими вузлами мережі з однаковою імовірністю, надмірний розподіл ступенів можна знайти як: <ref name=":0">{{Cite book
|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090
|title=Networks
|last=Newman
|first=Mark
|date=2018-10-18
|publisher=Oxford University Press
|volume=1
|language=en
|doi=10.1093/oso/9780198805090.001.0001
|isbn=978-0-19-880509-0
}}</ref>

<math>
q(k) = \frac{k+1}{\langle k \rangle}P(k+1),
</math>

де <math>
{\langle k \rangle}
</math> – середній ступінь моделі. Звідси випливає, що середній ступінь сусіда будь-якого вузла більший за середній ступінь цього вузла. На прикладі соціальних мереж це буде позначати, що, в середньому, у ваших друзів більше друзів, ніж у вас. Це відомо як [[парадокс дружби]]. Можна показати, що мережа може мати [[Гігантська компонента|гігантську компоненту]], якщо її середній надмірний ступень більший за одиницю:

<math>
\sum_k kq(k) > 1 \Rightarrow {\langle k^2 \rangle}-2{\langle k \rangle}>0 
</math>

Майте на увазі, що останні два рівняння виконуються лише для [[Модель конфігурації|моделі конфігурації,]] і щоб отримати надмірний розподіл ступенів для реальних мереж, кореляція ступенів повинна бути врахована. <ref name=":0">{{Cite book
|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090
|title=Networks
|last=Newman
|first=Mark
|date=2018-10-18
|publisher=Oxford University Press
|volume=1
|language=en
|doi=10.1093/oso/9780198805090.001.0001
|isbn=978-0-19-880509-0
}}</ref>

== Метод генеруючих функцій ==
[[Генератриса цілочисельної випадкової величини|Генеруючі функції]] можна використовувати для обчислення різних властивостей випадкових мереж. Використовуючи розподіл ступенів та надмірний розподіл ступенів певної мережі, <math>
P(k)
</math> і <math>
q(k)
</math> відповідно, можна записати два степеневих ряди у таких формах:

<math>
G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k 
</math> і <math>
G_1(x) = \textstyle \sum_{k} \displaystyle q(k)x^k = \textstyle \sum_{k} \displaystyle \frac{k}{\langle k \rangle}P(k)x^{k-1} 
</math>

<math>
G_1(x)
</math> також можна отримати як похідну від <math>
G_0(x)
</math> :

<math>
G_1(x) = \frac{G'_0(x)}{G'_0(1)} 
</math>

Якщо відомо генеруючу функцію для розподілу ймовірностей <math>
P(k)
</math> то можливо відновити значення <math>
P(k)
</math> шляхом диференціювання:

<math>
P(k) = \frac{1}{k!} {\operatorname{d}^k\!G\over\operatorname{d}\!x^k}\biggl \vert _{x=0}
</math>

Певні властивості, такі як моменти, можуть бути легко обчислені за допомогою ряду <math>
G_0(x) 
</math> та його похідних:

* <math>
{\langle k \rangle} = G'_0(1)
</math>
* <math>
{\langle k^2 \rangle} = G''_0(1) + G'_0(1) 
</math>

Та у загальному випадку: <ref name=":0">{{Cite book
|url=http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090
|title=Networks
|last=Newman
|first=Mark
|date=2018-10-18
|publisher=Oxford University Press
|volume=1
|language=en
|doi=10.1093/oso/9780198805090.001.0001
|isbn=978-0-19-880509-0
}}<cite class="citation book cs1" data-ve-ignore="true" id="CITEREFNewman2018">Newman, Mark (2018-10-18). [http://www.oxfordscholarship.com/view/10.1093/oso/9780198805090.001.0001/oso-9780198805090 ''Networks'']. Vol.&nbsp;1. Oxford University Press. [[Цифровий ідентифікатор об'єкта|doi]]:[[doi:10.1093/oso/9780198805090.001.0001|10.1093/oso/9780198805090.001.0001]]. [[ISBN]]&nbsp;[[Спеціальний: Книжкові джерела/978-0-19-880509-0|<bdi>978-0-19-880509-0</bdi>]].</cite></ref>

* <math>
{\langle k^m \rangle} = \Biggl[{\bigg(\operatorname{x}{\operatorname{d}\!\over\operatorname{dx}\!}\biggl)^m}G_0(x)\Biggl]_{x=1}
</math>

Для [[Розподіл Пуассона|пуассонівських]] випадкових мереж, таких як [[Модель Ердеша — Реньї|графік ER]], <math>
G_1(x) = G_0(x) 
</math>, через це теорія випадкових мереж такого типу є доволі простою. Розподіли ймовірностей для перших найближчих сусідів породжується функцією <math>
G_0(x) 
</math> та для других функцією <math>
G_0(G_1(x)) 
</math>. У загальному випадку, розподіл для <math>
m
</math>-их найближчих сусідів генерується таким чином:

<math>
G_0\bigl(G_1(...G_1(x)...)\bigr) 
</math>, де функція <math>
G_1 
</math> діє сама на себе <math>
m-1 
</math> раз. <ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|url=https://link.aps.org/doi/10.1103/PhysRevE.64.026118|journal=Physical Review E|language=en|volume=64|issue=2|pages=026118|arxiv=cond-mat/0007235|doi=10.1103/PhysRevE.64.026118|issn=1063-651X|doi-access=free}}</ref>

Середня кількість перших сусідів, <math>
c_1
</math>, є <math>
{\langle k \rangle} = {dG_0(x)\over dx}|_{x=1}
</math> а середня кількість других сусідів становить: <math>
c_2 = \biggl[ {d\over dx}G_0\big(G_1(x)\big)\biggl]_{x=1} = G_1'(1)G'_0\big(G_1(1)\big) = G_1'(1)G'_0(1) = G''_0(1)
</math>

== Розподіл ступенів для спрямованих мереж ==
[[Файл:Enwiki-degree-distribution.png|праворуч|міні|320x320пкс| Вхідний/вихідний розподіл ступенів для графіка гіперпосилання Вікіпедії (логарифмічні шкали)]]
<math>
\mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} .
</math>

<math>
\langle{k_{in}-k_{out}}\rangle =\sum_{k_{in},k_{out}} \displaystyle (k_{in}-k_{out})P({k_{in},k_{out}}) = 0 
</math> ,

<math>
 {\partial \mathcal{G}\over\partial x}\vert _{x,y=1} = {\partial \mathcal{G}\over\partial y}\vert _{x,y=1} = c,
 
</math>

* <math>
G^{in}_0(x) = \mathcal{G}(x,1)
</math>
* <math>
G^{in}_1(x) = \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1} 
</math>
* <math>
G^{out}_0(y) = \mathcal{G}(1,y)
</math>
* <math>
G^{out}_1(y) = \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1} 
</math>

== Розподіл ступенів для знакових мереж ==
У знакових мережах кожен вузол має додатний ступінь <math>
k_{
+}
</math> і від'ємний ступінь <math>
k_{-}
</math> які є відповідно додатною кількістю ребер і від’ємною кількістю ребер, з'єднаних з цим вузлом. Таким чином <math>
P(k_{+})
</math> і <math>
P(k_{-})
</math> позначають негативний розподіл ступенів та позитивний розподіл ступенів для знакових мереж. <ref name="10.1038/s41598-021-81767-7">{{Cite journal|vauthors=Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G|date=January 2021|title=Topological impact of negative links on the stability of resting-state brain network|url=|journal=Scientific Reports|doi=10.1038/s41598-021-81767-7|pmc=7838299|pmid=33500525}}</ref> <ref name="10.1016/j.physa.2014.11.062">{{Cite journal|vauthors=Ciotti V|date=2015|title=Degree correlations in signed social networks|url=https://www.sciencedirect.com/science/article/abs/pii/S0378437114010334|journal=Physica A: Statistical Mechanics and its Applications|arxiv=1412.1024|doi=10.1016/j.physa.2014.11.062}}</ref>

== Дивись також ==

* [[Теорія графів]]
* [[Складні мережі|Складна мережа]]
* [[Безмасштабна мережа]]
* [[Випадковий граф|Випадковий графік]]
* Конструкційне обрізання
{{Reflist|3}}


<nowiki>
[[Категорія:Теорія мереж]]
[[Категорія:Інваріанти графа]]
[[Категорія:Теорія графів]]</nowiki>