Розріджена мережа

У науці про мережі розрі́джена мере́жа (англ. sparse network) має набагато менше з'єднань, ніж можливе максимальне число з'єднань у цій мережі (протилежністю є щі́льна мере́жа, англ. dense network). Вивчення розріджених мереж є відносно новою сферою, насамперед стимульованою вивченням реальних мереж, таких як соціальні та комп'ютерні мережі.[1]

Звісно, поняття набагато меншої кількості з'єднань є розмовним та неформальним. Хоча й можна винайти поріг для певної мережі, універсального порогу, що визначав би, що насправді означає набагато менше, не існує. В результаті, формального сенсу в розрідженості для будь-якої скінченної мережі не існує, незважаючи на поширену згоду, що більшість емпіричних мереж є справді розрідженими. Проте існує формальний сенс у розрідженості у випадку нескінченних мережних моделей, що визначається поведінкою кількості ребер (M) та/або середнього степеня (⟨k⟩), коли кількість вузлів (N) прямує до нескінченності.[2]

Визначення

Просту незважену мережу розміру ${\displaystyle N}$ називають розрідженою, якщо кількість з'єднань ${\displaystyle M}$ у ній є набагато меншою за максимально можливе число з'єднань ${\displaystyle M_{max}}$:[1]

${\displaystyle M\ll M_{max}={N \choose 2}}$.

У будь-якій заданій (реальній) мережі кількість вузлів N та з'єднань M є лише просто двома числами, тож значення знаку набагато менше (${\displaystyle \ll }$ вище) є виключно розмовним та неформальним, як і такі заяви, що «багато реальних мереж є розрідженими».

Проте, якщо ми маємо справу з синтетичною послідовністю графів ${\displaystyle G_{N}}$, або мережною моделлю, чітко визначеною для мереж ${\displaystyle G_{N}}$ будь-якого розміру N = 1,2, …, ${\displaystyle \infty }$, то ${\displaystyle \ll }$ набуває звичного формального значення:

${\displaystyle M\ll M_{max}\iff M=o(M_{max})\iff \lim _{N\rightarrow \infty }{\frac {M}{M_{max}}}=0}$.

Іншими словами, мережну послідовність або модель ${\displaystyle G_{N}}$ називають щільною або розрідженою залежно від того, чи (очікуваний) середній ступінь ${\displaystyle \langle k\rangle =2M/N}$ в ${\displaystyle G_{N}}$ масштабується лінійно, чи сублінійно з N:[2][3]

${\displaystyle G_{N}}$ є щільною (англ. dense), якщо ${\displaystyle \langle k\rangle =O(N)}$;

${\displaystyle G_{N}}$ є розрідженою (англ. sparse), якщо ${\displaystyle \langle k\rangle =o(N)}$.

Важливим підкласом розріджених мереж є мережі, середній степінь яких або є сталим, або збігається до сталого. Деякі автори називають розрідженими лише такі мережі, тоді як інші припасають для них особливі назви:[4]

${\displaystyle G_{N}}$ є істинно розрідженою (англ. truly sparse) або надзвичайно розрідженою (англ. extremely sparse) або ультрарозрідженою (англ. ultrasparse), якщо ${\displaystyle \langle k\rangle =O(1)}$.

Існують також альтернативні, більш строгі визначення розрідженості мережі, що вимагають збігання розподілу ступенів у ${\displaystyle G_{N}}$ до чітко визначеної границі при ${\displaystyle N\rightarrow \infty }$.[5] Відповідно до цього визначення, N-зірковий граф ${\displaystyle S_{N}}$, наприклад, розрідженим не є.

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

Розподіл степенів вузлів змінюється зі збільшенням зв'язності. Різні щільності ребер у складних мережах мають різний розподіл степенів вузлів, як підказує аналіз мережі Flickr.[6] Розріджено зв'язані мережі мають безмасштабний, степеневий закон розподілу. Зі збільшенням зв'язності мережі демонструють дедалі більше розходження зі степеневим законом. Одним з основних чинників, що впливають на зв'язність мережі, є схожість вузлів(інші мови). Наприклад, у соціальних мережах люди, імовірно, будуть з'єднаними між собою, якщо вони мають однакове соціальне походження, зацікавлення, смаки, переконання тощо. У контексті біологічних мереж білки або інші молекули є зв'язаними, якщо вони мають однакову або взаємодоповнювальну форму їхніх складних поверхонь.[6]

Загальна термінологія

Якщо вузли в мережах не є зваженими, то структурні складові мережі можливо показувати за допомогою матриці суміжності . Якщо більшість елементів у матриці дорівнює нулеві, таку матрицю називають розрідженою матрицею. І навпаки, якщо більшість елементів є ненульовими, то матриця є щільною. Розрідженість або щільність матриці визначається часткою нульового елемента до загальної кількості елементів у матриці. Так само в контексті теорії графів, якщо число ребер є близьким до свого максимуму, то граф буде відомим як щільний граф. Якщо число ребер є меншим за максимальне можливе число ребер, то графи цього типу називають розрідженими графами.[7]

Застосування

Розріджені мережі зустрічаються у соціальних, комп'ютерних та біологічних мережах(інші мови), також їх застосування можливо знайти у транспорті, електромережах, мережах цитування тощо. Оскільки більшість реальних мереж є великими та розрідженими, для їх розуміння та аналізу було розроблено кілька моделей.[8] Ці мережі надихнули розріджений дизайн мереж на чипі у розробці багатопроцесорної вбудованої комп'ютерної техніки .

Розріджені мережі також здешевлюють обчислення, роблячи ефективним зберігання мережі як списку суміжності(інші мови) замість матриці суміжності. Наприклад, при використанні списку суміжності ітерування над сусідами вузла можливо досягати за Ο(M/N), тоді як з матрицею суміжності його досягають за Ο(N).[2]

Примітки

1. Barabási, Albert-László (2015). Network Science. Cambridge University Press. Архів оригіналу за 10 червня 2015. Процитовано 25 травня 2015. (англ.)
2. Newman, Mark. Networks 2nd Edition. Архів оригіналу за 26 лютого 2021. Процитовано 14 лютого 2021. (англ.)
3. Bollobás, Béla (1985). Random Graphs. Academic Press. (англ.)
4. Janson, Svante (2018). On Edge Exchangeable Random Graphs. J Stat Phys. 173 (3–4): 448—484. arXiv:1702.06396. Bibcode:2018JSP...173..448J. doi:10.1007/s10955-017-1832-9. PMC 6405020. PMID 30930480. (англ.)
5. van der Hofstad, Remco (2017). Random Graphs and Complex Networks. Cambridge University Press. doi:10.1017/9781316779422. ISBN 9781316779422. (англ.)
6. Scholz, Matthias (7 січня 2015). Node similarity as a basic principle behind connectivity in complex networks. Journal of Data Mining and Digital Humanities. 2015 (77). arXiv:1010.0803. doi:10.46298/jdmdh.33. S2CID 221799. Архів оригіналу за 16 квітня 2015. Процитовано 25 травня 2015. (англ.)
7. Nykamp, Duane Q. An introduction to networks. Math Insight. Архів оригіналу за 14 травня 2015. Процитовано 25 травня 2015. (англ.)
8. Gribonval, Rémi. Sparse Models, Algorithms and Learning for Large-scale data. SMALL. Архів оригіналу за 11 липня 2020. Процитовано 25 травня 2015. (англ.)