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

Просту незважену мережу розміру ${\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]