Rzadka sieć - Sparse network

W nauce o sieciach rzadka sieć ma znacznie mniej łączy niż możliwa maksymalna liczba łączy w tej sieci (odwrotnością jest gęsta sieć ). Badanie sieci rzadkich jest stosunkowo nowym obszarem stymulowanym głównie przez badanie sieci rzeczywistych, takich jak sieci społecznościowe i komputerowe.

Pojęcie znacznie mniejszej liczby linków jest oczywiście potoczne i nieformalne. Chociaż można wymyślić próg dla konkretnej sieci, nie ma uniwersalnego progu określającego, co faktycznie oznacza znacznie mniej . W rezultacie nie ma formalnego poczucia rzadkości w przypadku jakiejkolwiek skończonej sieci, pomimo powszechnej zgody, że większość sieci empirycznych jest rzeczywiście rzadka. Istnieje jednak formalne poczucie rzadkości w przypadku nieskończonych modeli sieci, determinowane przez zachowanie liczby krawędzi (M) i/lub średniego stopnia (<k>) wraz ze wzrostem liczby węzłów (N) do nieskończoności.

Definicje

Prosta nieważona sieć o rozmiarze nazywana jest rzadką, jeśli liczba łączy w niej jest znacznie mniejsza niż maksymalna możliwa liczba łączy : ${\ Displaystyle N}$${\ Displaystyle M}$${\displaystyle M_{maks}}$

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

W dowolnej (rzeczywistej) sieci liczba węzłów N i połączeń M to tylko dwie liczby, dlatego znaczenie znacznie mniejszego znaku ( powyżej) jest czysto potoczne i nieformalne, podobnie jak stwierdzenia typu „wiele rzeczywistych sieci jest rzadkich. " ${\displaystyle \ll}$

Jeśli jednak mamy do czynienia z syntetyczną sekwencją grafów , lub modelem sieci, który jest dobrze zdefiniowany dla sieci o dowolnym rozmiarze N = 1,2,..., , wówczas uzyskuje on swoje zwykłe formalne znaczenie: ${\ Displaystyle G_ {N}}$${\ Displaystyle G_ {N}}$${\displaystyle \infty}$${\displaystyle \ll}$

${\ Displaystyle M \ ll M_ {maks} \ iff M = o (M_ {maks}) \ iff \ lim _ {N \ rightarrow \ infty} {\ Frac {M} {M_ {maks}}} = 0}$.

Innymi słowy, sekwencja lub model sieci nazywa się gęstą lub rzadką w zależności od tego, czy (oczekiwany) średni stopień w skalach liniowo lub podliniowo z N : ${\ Displaystyle G_ {N}}$${\ Displaystyle \ langle k \ rangle = 2 M/N}$${\ Displaystyle G_ {N}}$

${\ Displaystyle G_ {N}}$ jest gęsty, jeśli ; ${\ Displaystyle \ langle k \ rangle = O (N)}$

${\ Displaystyle G_ {N}}$ jest rzadki, jeśli . ${\ Displaystyle \ langle k \ rangle = o (N)}$

Ważną podklasą sieci rzadkich są sieci, których średni stopień jest albo stały, albo jest zbieżny do stałej. Niektórzy autorzy nazywają tylko takie sieci rzadkimi, inni rezerwują dla nich specjalne nazwy:

${\ Displaystyle G_ {N}}$ jest naprawdę rzadki lub wyjątkowo rzadki lub ultrarzadki, jeśli . ${\ Displaystyle \ langle k \ rangle = O (1)}$

Istnieją również alternatywne, bardziej rygorystyczne definicje rzadkości sieci, wymagające zbieżności rozkładu stopni w dobrze zdefiniowanym limicie przy . Zgodnie z tą definicją, na przykład wykres N-gwiazdowy nie jest rzadki. ${\ Displaystyle G_ {N}}$${\displaystyle N\rightarrow \infty}$ ${\ Displaystyle S_ {N}}$

Rozkład stopni węzła

Rozkład stopni węzła zmienia się wraz ze wzrostem łączności. Różne gęstości łączy w złożonych sieciach mają różny rozkład stopni węzłów, jak sugeruje Analiza sieci Flickr. Słabo połączone sieci mają bezskalową dystrybucję zgodnie z prawem energetycznym. Wraz z rosnącą łącznością sieci wykazują coraz większą rozbieżność z prawem energetycznym. Jednym z głównych czynników wpływających na łączność sieciową jest podobieństwo węzłów . Na przykład w sieciach społecznościowych ludzie mogą być ze sobą połączeni, jeśli mają wspólne pochodzenie społeczne, zainteresowania, gusta, przekonania itp. W kontekście sieci biologicznych białka lub inne cząsteczki są ze sobą powiązane, jeśli mają dokładne lub komplementarne dopasowanie ich złożonych powierzchni.

Wspólna terminologia

Jeśli węzły w sieci nie są ważone, elementy strukturalne sieci można wyświetlić za pomocą macierzy sąsiedztwa . Jeśli większość elementów w macierzy wynosi zero, taka macierz nazywana jest macierzą rzadką . Natomiast jeśli większość elementów jest niezerowa, to macierz jest gęsta . Rzadkość lub gęstość matrycy jest identyfikowana przez ułamek pierwiastka zerowego do całkowitej liczby pierwiastków w matrycy. Podobnie w kontekście teorii grafów , jeśli liczba połączeń jest bliska maksimum, wówczas graf nazwano by gęstym grafem . Jeśli liczba linków jest mniejsza niż maksymalna liczba linków, tego typu wykresy są określane jako rzadki wykres .

Aplikacje

Rzadkie sieci można znaleźć w sieciach społecznościowych , komputerowych i biologicznych , a jej zastosowania można znaleźć w transporcie , liniach energetycznych, sieciach cytowań itp. Ponieważ większość rzeczywistych sieci jest duża i rzadka, opracowano kilka modeli, aby zrozumieć i analizuj je. Sieci te zainspirowały rzadki projekt sieci na chipie w wieloprocesorowej, wbudowanej inżynierii komputerowej .

Rzadkie sieci powodują również tańsze obliczenia, ponieważ przechowywanie sieci jako listy sąsiedztwa , a nie macierzy sąsiedztwa, jest wydajne . Na przykład podczas korzystania z listy sąsiedztwa iteracja po sąsiadach węzła może być osiągnięta w O(M/N), podczas gdy jest to osiągane w O(N) z macierzą sąsiedztwa.

Bibliografia