Rzadka sieć

W nauce o sieciach rzadka sieć ma znacznie mniej połączeń niż możliwa maksymalna liczba łączy w tej sieci (przeciwieństwem jest gęsta sieć ). Badanie sieci rzadkich jest stosunkowo nowym obszarem, stymulowanym przede wszystkim badaniem 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, który określałby, co znacznie mniej . W rezultacie nie ma formalnego poczucia rzadkości dla żadnej 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, określone 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$ rzadką, jeśli liczba linków w niej jest znacznie mniejsza niż maksymalna możliwa liczba linków $Displaystyle M_ {max$$}$ :

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

W dowolnej (rzeczywistej) sieci liczba węzłów N i łączy M to tylko dwie liczby, dlatego znaczenie $)$ mniejszego znaku ( powyżej jest czysto potoczne i nieformalne, podobnie jak stwierdzenia takie jak „wiele prawdziwych sieci jest rzadkich”.

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}$ { \ $displaystyle$ ..., wtedy ${\ displaystyle \ ll}$ osiąga swoje zwykłe znaczenie formalne: ${\ displaystyle \ infty}$

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

Innymi słowy, sekwencja lub model sieci $jest$ lub rzadkim , w zależności od tego, czy (oczekiwany) średni stopień ${\ Displaystyle \ langle k \ rangle = 2M / N}$ w skaluje się liniowo lub podliniowo z N : sol ${\ 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ą rzadkich sieci są sieci, których średni stopień jest albo stały, albo zbieżny do stałej. Niektórzy autorzy nazywają tylko takie sieci rzadkimi, podczas gdy inni rezerwują dla nich specjalne nazwy:

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

$N \ rightarrow \ infty$ wymagające zbieżności rozkładu stopni w dobrze określonej granicy w $displaystyle$ . Zgodnie z tą definicją, $wykres$ -gwiazdkowy nie jest rzadki.

Dystrybucja stopni węzłów

Rozkład stopni węzłów zmienia się wraz ze wzrostem łączności. Jak sugeruje analiza sieci Flickr, różne gęstości łączy w złożonych sieciach mają różną dystrybucję stopni węzłów. Słabo połączone sieci mają mocy bez skali . Wraz ze wzrostem łączności sieci wykazują coraz większą rozbieżność z prawem energetycznym. Jednym z głównych czynników wpływających na łączność sieci jest podobieństwo węzłów . Na przykład w sieciach społecznościowych , ludzie prawdopodobnie będą ze sobą powiązani, jeśli mają wspólne pochodzenie społeczne, zainteresowania, upodobania, przekonania itp. W kontekście sieci biologicznych białka lub inne cząsteczki są połączone, jeśli mają dokładne lub uzupełniające dopasowanie swoich złożonych powierzchni.

Wspólna terminologia

Jeśli węzły w sieciach nie są ważone, elementy strukturalne sieci można przedstawić za pomocą macierzy sąsiedztwa . Jeśli większość elementów w macierzy jest równa zero, taka macierz jest nazywana macierzą rzadką . W przeciwieństwie do tego, jeśli większość elementów jest różna od zera, to macierz jest gęsta . Rzadkość lub gęstość macierzy jest identyfikowana przez ułamek elementu zerowego do całkowitej liczby elementów w macierzy. Podobnie w kontekście teorii grafów , jeśli liczba powiązań jest bliska maksimum, wówczas graf byłby znany jako graf gęsty . Jeśli liczba łączy jest mniejsza niż maksymalna liczba łączy, tego typu grafy są określane jako rzadkie grafy .

Aplikacje

Sieć rzadką można znaleźć w sieciach społecznościowych , komputerowych i biologicznych , a jej zastosowania można znaleźć w transporcie , liniach energetycznych, sieciach cytatów itp. Ponieważ większość rzeczywistych sieci jest duża i rzadka, opracowano kilka modeli, aby zrozumieć i je analizować. Sieci te zainspirowały rzadkie sieci na chipie w wieloprocesorowej inżynierii komputerów wbudowanych .

Sieci rzadkie powodują również tańsze obliczenia, dzięki czemu przechowywanie sieci jako listy sąsiedztwa zamiast macierzy sąsiedztwa jest bardziej efektywne . Na przykład, używając listy sąsiedztwa, iterację po sąsiadach węzła można osiągnąć w O(M/N), podczas gdy jest to osiągane w O(N) z macierzą sąsiedztwa.