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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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