Розподіл степенів

При дослідженні графів та мереж, степінь вузла в мережі — це кількість зв'язків з іншими вузлами, а розподіл степенів — це розподіл ймовірностей цих степенів усією мережею.

Визначення

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

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

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

Спостережувані розподіли степенів

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

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(або розподіл Пуассона в межах великого n, якщо середній степінь ${\displaystyle \langle k\rangle =p(n-1)}$ є фіксованим). Однак більшість реальних мереж мають розподіл степенів, що дуже відрізняються від попереднього. Більшість із них мають значне відхилення праворуч, що позначає, що більша кількість вузлів мають низький степінь, та лише невелика кількість, відома як «хаби», мають високий степінь. Стверджувалося, що певні мережі, зокрема Інтернет, Всесвітня мережа та деякі соціальні мережі, мають розподіл степенів, які приблизно відповідають степеневому закону: ${\displaystyle P(k)\sim k^{-\gamma }}$, де γ — константа. Такі мережі називаються безмасштабними мережами та вони привертають особливу увагу своїми структурними та динамічними властивостями.^[1][2][3][4] Однак дослідження широкого кола реальних мереж показує, що безмасштабні мережі, якщо їх оцінювати за допомогою точних статистичних показників зустрічаються рідко.^[5] Деякі дослідники заперечують ці висновки, стверджуючи, що визначення, які було використано у дослідженні, є невідповідно жорсткими,^[6] у той час, як інші стверджують, що точна функціональна форма розподілу степенів менш важлива, ніж знання того, чи є розподіл степенів розподілом з товстим хвостом^[en] чи ні.^[7] Надмірну інтерпретацію конкретних форм розподілу степенів також критикували за те, що вона не враховувала, як мережі можуть розвиватися з часом.^[8]

Надмірний розподіл степенів

Надмірний розподіл степенів — це розподіл ймовірностей, для вузла, досягнутого за ребром, кількості інших ребер, які ведуть до цього вузла.^[9] Іншими словами, це розподіл вихідних зв'язків вузла, досягнутого за ребром.

Припустимо, що мережа має розподіл степенів ${\displaystyle P(k)}$, після вибору вузла (випадково чи ні) і переходу до одного з його сусідів (припускаючи, що він має принаймні одного сусіда), ймовірність того, що цей вузол матиме ${\displaystyle k}$ сусідів не визначається ${\displaystyle P(k)}$. Причиною цього є те, що кожен раз, коли якийсь вузол вибирається в гетерогенній мережі, більш ймовірно досягти хабу, дотримуючись одного з наявних сусідів цього вузла. Справжня ймовірність того, що такі вузли мають степінь ${\displaystyle k}$ є ${\displaystyle q(k)}$ яка називається надмірним степенем цього вузла. У моделі конфігурації^[en], кореляції між вузлами, які проігноровані, і кожним вузлом, стосовно якого припускається, що його можна з'єднанати з будь-якими іншими вузлами мережі з однаковою імовірністю, надмірний розподіл степенів можна записати у такому вигляді:^[9]

${\displaystyle q(k)={\frac {k+1}{\langle k\rangle }}P(k+1),}$

де ${\displaystyle {\langle k\rangle }}$ — середній степінь моделі. Звідси випливає, що середній степінь сусіда будь-якого вузла є більшим за середній степінь цього вузла. На прикладі соціальних мереж це буде означати, що, у середньому, у ваших друзів більше друзів, ніж у вас. Це відомо як парадокс дружби. Можна показати, що мережа може мати гігантську компоненту, якщо її середній надмірний степінь більший за одиницю: ${\displaystyle \sum _{k}kq(k)>1\Rightarrow {\langle k^{2}\rangle }-2{\langle k\rangle }>0}$

Майте на увазі, що останні два рівняння виконуються лише для моделі конфігурації^[en], і щоб отримати надмірний розподіл степенів для реальних мереж, кореляція степенів повинна бути врахована.^[9]

Метод твірних функцій

Твірні функції можна використовувати для обчислення певних властивостей випадкових мереж. Використовуючи розподіл степенів та надмірний розподіл степенів певної мережі, ${\displaystyle P(k)}$ і ${\displaystyle q(k)}$ відповідно, можна записати два степеневих ряди в такому вигляді:

${\displaystyle G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}}$ і ${\displaystyle 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}}$

${\displaystyle G_{1}(x)}$ також можна отримати використовуючи похідну ${\displaystyle G_{0}(x)}$ :

${\displaystyle G_{1}(x)={\frac {G'_{0}(x)}{G'_{0}(1)}}}$

Якщо твірна функція для розподілу ймовірностей ${\displaystyle P(k)}$ відома, то можливо відновити значення ${\displaystyle P(k)}$ шляхом диференціювання:

${\displaystyle P(k)={\frac {1}{k!}}{\operatorname {d} ^{k}\!G \over \operatorname {d} \!x^{k}}{\biggl \vert }_{x=0}}$

Певні властивості, такі як моменти, можуть бути легко обчислені за допомогою ряду ${\displaystyle G_{0}(x)}$ та його похідних:

• ${\displaystyle {\langle k\rangle }=G'_{0}(1)}$
• ${\displaystyle {\langle k^{2}\rangle }=G''_{0}(1)+G'_{0}(1)}$

Та у загальному випадку:^[9]

• ${\displaystyle {\langle k^{m}\rangle }={\Biggl [}{{\bigg (}\operatorname {x} {\operatorname {d} \! \over \operatorname {dx} \!}{\biggl )}^{m}}G_{0}(x){\Biggl ]}_{x=1}}$

Для пуассонівських випадкових мереж, таких як графік ER, ${\displaystyle G_{1}(x)=G_{0}(x)}$, через це теорія випадкових мереж такого типу є доволі простою. Розподіли ймовірностей для перших найближчих сусідів породжується функцією ${\displaystyle G_{0}(x)}$ та для других функцією ${\displaystyle G_{0}(G_{1}(x))}$. У загальному випадку, розподіл для ${\displaystyle m}$-их найближчих сусідів генерується таким чином:

${\displaystyle G_{0}{\bigl (}G_{1}(...G_{1}(x)...){\bigr )}}$, де функція ${\displaystyle G_{1}}$ діє сама на себе ${\displaystyle m-1}$ раз.^[10]

Середня кількість перших сусідів, ${\displaystyle c_{1}}$, є ${\displaystyle {\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}}$ а середня кількість других сусідів дорівнює: ${\displaystyle 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)}$

Розподіл степенів для орієнтованих мереж

Вхідний/вихідний розподіл степенів для графіка гіперпосилання Вікіпедії (логарифмічні шкали)

В орієнтованій мережі кожен вузол має певний вхідний степінь ${\displaystyle k_{in}}$ і певний вихідний степінь ${\displaystyle k_{out}}$, що дорівнюють кількості вхідних та вихідних ребер відповідно. Якщо ${\displaystyle P(k_{in},k_{out})}$ це ймовірність того, що випадково вибраний вузол має вхідний степінь ${\displaystyle k_{in}}$ і вихідний степінь ${\displaystyle k_{out}}$, тоді твірну функцію, призначену цьому спільному розподілу ймовірностей, можна записати з двома змінними ${\displaystyle x}$ і ${\displaystyle y}$ у вигляді: ${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}.}$

Оскільки кожне ребро в орієнтованій мережі має виходити з одного вузла та входити в інший, то середня кількість ребер, що входять у вузол, дорівнює нулю. Тому

${\displaystyle \langle {k_{in}-k_{out}}\rangle =\sum _{k_{in},k_{out}}\displaystyle (k_{in}-k_{out})P({k_{in},k_{out}})=0}$,

це означає, що твірна функція повинна задовольняти умові:

${\displaystyle {\partial {\mathcal {G}} \over \partial x}\vert _{x,y=1}={\partial {\mathcal {G}} \over \partial y}\vert _{x,y=1}=c,}$

де ${\displaystyle c}$ — середній степінь (як вхідний, так і вихідний) усіх вузлів у мережі; ${\displaystyle \langle {k_{in}}\rangle =\langle {k_{out}}\rangle =c.}$

Використовуючи функцію ${\displaystyle {\mathcal {G}}(x,y)}$, знов можна знайти твірну функцію для розподілу вхідного/вихідного степенів та надмірного розподілу вхідного/вихідного степенів, як і раніше. ${\displaystyle G_{0}^{in}(x)}$ можна визначити як твірну функцію кількості вхідних ребер для випадково вибраного вузла, та ${\displaystyle G_{1}^{in}(x)}$ можна визначити як кількість вхідних ребер до вузла, отриманого шляхом переходу за випадковим ребром. Також можна визначити твірні функції ${\displaystyle G_{0}^{out}(y)}$ і ${\displaystyle G_{1}^{out}(y)}$ для числа вихідних ребер з такого вузла:^[10]

• ${\displaystyle G_{0}^{in}(x)={\mathcal {G}}(x,1)}$
• ${\displaystyle G_{1}^{in}(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$
• ${\displaystyle G_{0}^{out}(y)={\mathcal {G}}(1,y)}$
• ${\displaystyle G_{1}^{out}(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

Тут, середня кількість перших сусідів ${\displaystyle c}$, або як було введено раніше ${\displaystyle c_{1}}$, дорівнює ${\displaystyle {\partial {\mathcal {G}} \over \partial x}{\biggl \vert }_{x,y=1}={\partial {\mathcal {G}} \over \partial y}{\biggl \vert }_{x,y=1}}$ та середня кількість других сусідів, досяжних з випадково вибраного вузла, визначається так: ${\displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={\partial ^{2}{\mathcal {G}} \over \partial x\partial y}{\biggl \vert }_{x,y=1}}$. Оскільки ці рівняння симетричні відносно ${\displaystyle x}$ та ${\displaystyle y}$, то вони визначають також значення для перших та других сусідів, з яких можна досягти випадкового вузла.^[10]

Розподіл степенів для мереж зі знаком

У знакових мережах кожен вузол має додатний степінь ${\displaystyle k_{+}}$ і від'ємний степінь ${\displaystyle k_{-}}$, які є відповідно додатною кількістю ребер і від'ємною кількістю ребер, з'єднаних з цим вузлом. Таким чином ${\displaystyle P(k_{+})}$ і ${\displaystyle P(k_{-})}$ позначають негативний розподіл степенів та позитивний розподіл степенів для мереж зі знаком.^[11][12]

Див. також

• Теорія графів
• Складна мережа
• Безмасштабна мережа
• Випадковий графік
• Структурне відсікання^[en]

Посилання

1. Barabási, Albert-László; Albert, Réka (15 жовтня 1999). Emergence of Scaling in Random Networks. Science. 286 (5439): 509—512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342. 
2. Albert, Réka; Barabási, Albert-László (11 грудня 2000). Topology of Evolving Networks: Local Events and Universality (PDF). Physical Review Letters. 85 (24): 5234—5237. arXiv:cond-mat/0005085. Bibcode:2000PhRvL..85.5234A. doi:10.1103/physrevlett.85.5234. ISSN 0031-9007. PMID 11102229. 
3. Dorogovtsev, S. N.; Mendes, J. F. F.; Samukhin, A. N. (21 травня 2001). Size-dependent degree distribution of a scale-free growing network. Physical Review E. 63 (6): 062101. arXiv:cond-mat/0011115. Bibcode:2001PhRvE..63f2101D. doi:10.1103/physreve.63.062101. ISSN 1063-651X. PMID 11415146. 
4. Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). Scale-free behavior of networks with the copresence of preferential and uniform attachment rules. Physica D: Nonlinear Phenomena. 371: 1—12. arXiv:1704.08597. Bibcode:2018PhyD..371....1P. doi:10.1016/j.physd.2018.01.005. 
5. Broido, Anna D.; Clauset, Aaron (4 березня 2019). Scale-free networks are rare. Nature Communications (англ.). 10 (1): 1017. doi:10.1038/s41467-019-08746-5. ISSN 2041-1723. PMC 6399239. 
6. Voitalov, Ivan; van der Hoorn, Pim; van der Hofstad, Remco; Krioukov, Dmitri (18 жовтня 2019). Scale-free networks well done. Physical Review Research. 1 (3): 033034. doi:10.1103/PhysRevResearch.1.033034. 
7. Holme, Petter (4 березня 2019). Rare and everywhere: Perspectives on scale-free networks. Nature Communications (англ.). 10 (1): 1016. Bibcode:2019NatCo..10.1016H. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568. 
8. Falkenberg, Max; Lee, Jong-Hyeok; Amano, Shun-ichi; Ogawa, Ken-ichiro; Yano, Kazuo; Miyake, Yoshihiro; Evans, Tim S.; Christensen, Kim (18 червня 2020). Identifying time dependence in network growth. Physical Review Research. 2 (2): 023352. arXiv:2001.09118. doi:10.1103/PhysRevResearch.2.023352. 
9. Newman, Mark (18 жовтня 2018). Networks (англ.). Т. 1. Oxford University Press. doi:10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0. 
10. Newman, M. E. J.; Strogatz, S. H.; Watts, D. J. (24 липня 2001). Random graphs with arbitrary degree distributions and their applications. Physical Review E (англ.). 64 (2): 026118. arXiv:cond-mat/0007235. doi:10.1103/PhysRevE.64.026118. ISSN 1063-651X. 
11. Saberi M; Khosrowabadi R; Khatibi A; Misic B; Jafari G (January 2021). Topological impact of negative links on the stability of resting-state brain network. Scientific Reports. doi:10.1038/s41598-021-81767-7. PMC 7838299. PMID 33500525. 
12. Ciotti V (2015). Degree correlations in signed social networks. Physica A: Statistical Mechanics and its Applications. arXiv:1412.1024. doi:10.1016/j.physa.2014.11.062. 

• Albert, R.; Barabasi, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics. 74 (1): 47—97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47. 
• Dorogovtsev, S.; Mendes, J. F. F. (2002). Evolution of networks. Advances in Physics. 51 (4): 1079—1187. arXiv:cond-mat/0106144. Bibcode:2002AdPhy..51.1079D. doi:10.1080/00018730110112519. 
• Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review. 45 (2): 167—256. arXiv:cond-mat/0303516. Bibcode:2003SIAMR..45..167N. doi:10.1137/S003614450342480.