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

У науці про мережі розрі́джена мере́жа (англ. 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]