Model konfiguracji

Rysunek 1. Sekwencja stopni i różne realizacje sieci w modelu konfiguracyjnym

W nauce o sieciach model konfiguracji jest metodą generowania losowych sieci z danej sekwencji stopni . Jest szeroko stosowany jako model referencyjny dla rzeczywistych sieci społecznościowych , ponieważ umożliwia modelarzowi uwzględnienie dowolnych rozkładów stopni.

Uzasadnienie modelu

W modelu konfiguracyjnym stopień każdego wierzchołka jest z góry zdefiniowany, zamiast mieć rozkład prawdopodobieństwa, z którego wybierany jest dany stopień. W przeciwieństwie do modelu Erdősa-Rényiego , sekwencja stopni modelu konfiguracyjnego nie jest ograniczona do rozkładu Poissona , model pozwala użytkownikowi nadać sieci dowolny pożądany rozkład stopni.

Algorytm

Poniższy algorytm opisuje generację modelu:

1. Weź sekwencję stopni, tj. Przypisz stopień do każdego wierzchołka. ${\ displaystyle k_ {i}}$ Stopnie wierzchołków są reprezentowane jako półogniwa lub odcinki pośrednie. $($ aby móc wykres Sekwencja stopni może być wyprowadzona z rozkładu teoretycznego lub może reprezentować rzeczywistą sieć (określoną na podstawie macierzy sąsiedztwa sieci).
2. Wybierz równomiernie losowo dwa odcinki i połącz je, aby utworzyć krawędź. $kolejną$ parę z pozostałych połącz je Kontynuuj, aż skończą się końcówki. Rezultatem jest sieć z predefiniowaną sekwencją stopni. Realizacja sieci zmienia się wraz z kolejnością wybierania końcówek, mogą one obejmować cykle (b), pętle własne (c) lub wielokrotne łącza (d) (rysunek 1). Jednak oczekiwana liczba pętli własnych i multilinków spada do zera w N → ∞.

Pętle własne, wielokrawędziowe i implikacje

Algorytm opisany powyżej dopasowuje dowolne kody pośredniczące z takim samym prawdopodobieństwem. Jednorodny rozkład dopasowania jest ważną właściwością z punktu widzenia obliczania innych cech generowanych sieci. Proces generowania sieci nie wyklucza zdarzenia wygenerowania pętli własnej lub multilinku. Gdybyśmy zaprojektowali proces, w którym pętle własne i wielokrawędziowe nie są dozwolone, dopasowanie odcinków końcowych nie przebiegałoby zgodnie z równomiernym rozkładem.

Oczekiwana łączna liczba multilinków w sieci z modelem konfiguracji wynosiłaby:

${\ Displaystyle {\ Frac {1} {2}} {\ Duży [} {\ Frac {\ langle {k ^ {2}} \ rangle}} {\ kąt k\zakres }}-1{\duży ]}^{2}}$

gdzie ${\ Displaystyle \ langle {k ^ {n}} \ rangle}$ jest n-tym momentem rozkładu stopni. Dlatego średnia liczba pętli własnych i multilinków jest stała dla niektórych dużych sieci, a gęstość pętli własnych i multilinków, czyli liczba na węzeł, spada do zera, gdy N → ∞ $N \rightarrow \ infty}$ tak długo, jak ${\ Displaystyle \ langle {k ^ {2}} \ rangle}$ jest stała i skończona. W przypadku niektórych $zrobić$ stopni potęgowych, w których drugi moment jest rozbieżny, gęstość multi-linków może nie zniknąć lub może to .

Dalszą konsekwencją pętli własnych i wielu krawędzi jest to, że nie wszystkie możliwe sieci są generowane z takim samym prawdopodobieństwem. Ogólnie rzecz biorąc, wszystkie możliwe realizacje można wygenerować przez permutację końcówek wszystkich wierzchołków w każdy możliwy sposób. Liczba permutacji ${\ Displaystyle k_ {i}!}$$ja$ wynosi , więc liczba realizacji sekwencji stopni wynosi ${\ Displaystyle N \ {k_ {i} \} = \ prod _ {i} k_ {i}!$ } Oznaczałoby to, że każda realizacja zachodzi z takim samym prawdopodobieństwem. Jednak pętle własne i wielokrawędziowe mogą zmienić liczbę realizacji, ponieważ permutacja krawędzi własnych może skutkować niezmienioną realizacją. Biorąc pod uwagę, że liczba pętli własnych i wielokrotnych połączeń znika wraz z $,$ prawdopodobieństw różnych realizacji będzie niewielka, ale obecna.

Nieruchomości

Prawdopodobieństwo krawędzi

Odgałęzienie węzła $jesteśmy$$połączyć$ z innymi $odgałęzienia$ jest i musimy wykluczyć ten, w którym obserwowanie). Wierzchołek ma $pośredniczące ,$$z$ można połączyć węzeł z takim samym prawdopodobieństwem $.$ Prawdopodobieństwo, że odcinek węzła $m$$}} 2m-1}}}$ jednego z tych $Displaystyle {\ Frac {k_ {j$ , wynosi . Ponieważ węzeł $1 {$ odcinki $displaystyle$$} displaystyle {\ Frac {k_ {i} k_ {j}} {2m-1}}}$ prawdopodobieństwo połączenia z $i}$ wynosi $displaystyle$ ( ${j}} {2m}}}$ k_ wystarczająco duży ${\ displaystyle m}$ ). $,$ jako prawdopodobieństwo tylko wtedy, gdy krawędzi między węzły ${\ displaystyle i}$ i ${\ displaystyle j}$ . Należy zauważyć, że ten wzór nie ma zastosowania w przypadku krawędzi własnych.

Biorąc pod uwagę model konfiguracji z rozkładem stopni , prawdopodobieństwo losowo wybranego węzła ${\ displaystyle$ stopień wynosi $displaystyle p_ {k} }$$} p$$p_ { k$ . Ale gdybyśmy wzięli jeden z wierzchołków, do których możemy dojść po jednej z krawędzi i , prawdopodobieństwo posiadania stopnia k wynosi ${\ Displaystyle {\ Frac {k} {2m}}\times np_{k}={\frac {kp_{k}}{\left\langle k\right\rangle }}}$ . $stopniu$ Prawdopodobieństwo dotarcia do węzła o $k$ węzły ) na ${\ displaystyle kp_ {k}}$ w przeciwieństwie do stopnia typowego węzła z ${\ displaystyle p_ {k}}$ . Zatem oczekuje się, że sąsiad typowego węzła będzie miał wyższy stopień niż sam typowy węzeł. Ta cecha modelu konfiguracyjnego dobrze opisuje zjawisko „moi przyjaciele mają więcej przyjaciół niż ja”.

Współczynnik skupienia

Współczynnik grupowania (średnie prawdopodobieństwo, że sąsiedzi węzła są połączeni) oblicza się w przybliżeniu w następujący sposób: do sol $displaystyle C_ {g}}$

$\ suma _ {k_ {i}, k_{j}=1}^{\infty}q_{k_{i}}q_{k_{j}}{\frac {(k_{i}-1)(k_{j}-1)}{2m} },}$

gdzie ${\ Displaystyle q_ {k}}$ oznacza prawdopodobieństwo, że losowa krawędź osiągnie wierzchołek stopnia $,$ współczynniki postaci " ${\ Displaystyle k_ {i} -1 }$ " zamiast " pojawiają się, ponieważ jeden odcinek pośredni został uwzględniony przez fakt, że są to sąsiedzi $wspólnego$ Ocena powyższego skutkuje

${\ Displaystyle C_ {g} = {\ Frac {1} {2m}} \ lewo [\ suma _ {k = 0} ^ {\ infty} (k-1) q_ {k} \ prawo] ^ {2} .}$

Używając ${\ Displaystyle q_ {k} = kp_ {k} / \ langle k \ rangle}$ i ${\ Displaystyle 2m = N \ langle k \ rangle}$ p ${\ displaystyle p_ {k}}$ oznaczający rozkład stopni, $średni stopień$ liczbę wierzchołków, powyższe staje się ${\ displaystyle p_ {k}}$

${\ Displaystyle C_ { g}={\frac {1}{N\langle k\rangle ^{3}}}\left[\sum _{k=1}^{\infty}(k-1)kP(k)\right] ^{2}={\frac {\left(\langle k^{2}\rangle -\langle k\rangle \right)^{2}}{N\langle k\rangle ^{3}}},}$

gdzie ${\ Displaystyle \ langle k ^ {2} \ rangle}$ oznaczający drugi moment rozkładu stopni. Zakładając, że $i$$\ langle k ^ {2} \ rangle}$ są , powyższe zachowuje się jak

$\ Displaystyle C_ {g} \ sim {\ Frac {\ operatorname {const} {N}}}$

gdzie stała zależy od ${\ displaystyle p_ {k}}$ . $W$$ten$ sposób współczynnik mały w

Gigantyczny składnik

W modelu konfiguracyjnym istnieje gigantyczny komponent (GC), jeśli

${\ Displaystyle \ langle k ^ {2} \ rangle -2 \ langle k \ rangle > 0,}$

gdzie ${\ Displaystyle \ langle k \ rangle}$ i ${\ Displaystyle \ langle k ^ {2} \ rangle}$ to pierwszy i drugi moment rozkładu stopni . Oznacza to, że próg krytyczny zależy wyłącznie od wielkości, które są jednoznacznie określone przez rozkład stopni. ${\ displaystyle p_ {k}}$ .

Model konfiguracji generuje lokalnie sieci drzewiaste, co oznacza, że ​​każde lokalne sąsiedztwo w takiej sieci przyjmuje postać drzewa. Dokładniej, jeśli zaczniesz w dowolnym węźle w sieci i utworzysz zbiór wszystkich węzłów w odległości $mniejszej$ od tego węzła początkowego, zbiór z prawdopodobieństwem dążącym do 1 jako n → ∞ przyjmie re {\ displaystyle d} forma drzewa. ${\ Displaystyle c_ {2} = \ langle k ^ {2} \ rangle - \ langle k \ rangle.}$ strukturach drzewiastych liczba drugich sąsiadów uśredniona w całej wynosi $k$

Wtedy ogólnie średnią liczbę na odległość można zapisać jako: ${\ displaystyle d}$

${\ Displaystyle c_ {d} = \ lewo ({\ Frac {c_ {2}} {c_ {1}}} \ prawej) ^ {d-1} c_ {1}.}$

$,$ że ​​jeśli stosunek jest może mieć gigantyczny składnik. Jest to znane jako kryterium Molloya-Reeda. Intuicja stojąca za tym kryterium jest taka, że ​​​​jeśli istnieje gigantyczna składowa (GC), to średni stopień losowo wybranego wierzchołka ${\ displaystyle i}$ połączonym komponencie powinien wynosić co najmniej 2. Kryterium Molloya-Reeda można również wyrazić jako ja : ${\ Displaystyle \ suma _ {i} k_ {i} (k_ {i} -2)> 0},$ co implikuje, że chociaż rozmiar GC może zależeć p ${\ displaystyle p_ {0}}$ i ${\ displaystyle p_ {2}}$ liczba węzłów stopnia 0 i 2 nie ma wpływu na istnienie gigantycznego komponentu

Średnica

Model konfiguracji może przyjąć dowolny rozkład stopni i pokazuje efekt małego świata , ponieważ do wiodącej kolejności średnica modelu konfiguracji wynosi po prostu ${\ Displaystyle d = {\ frac {\ln(N)}{\ln(c_{2}/c_{1})}}}$ .

Elementy o skończonej wielkości

$nieskończoności$ liczba wierzchołków dąży do , prawdopodobieństwo znalezienia dwóch gigantycznych komponentów znika. Oznacza to, że w systemie rzadkim model składa się z jednego gigantycznego komponentu (jeśli taki istnieje) i wielu połączonych komponentów o skończonych rozmiarach. Rozmiary połączonych komponentów są charakteryzowane przez ich rozkład wielkości $prawdopodobieństwo$ , że losowo próbkowany wierzchołek należy do połączonego komponentu o $n.}$$\$ Istnieje zgodność między rozkładem stopni rozkładem wielkości ${\ Displaystyle w_ {n}.}$ Gdy całkowita liczba wierzchołków dąży do nieskończoności, zachodzi następująca zależność: ${\ Displaystyle N \ rightarrow \ infty}$

${\ Displaystyle w_ {n} = {\ rozpocząć {przypadki} {\ Frac {\ langle k \rangle }{n-1}}u_{1}^{*n}(n-2),&n>1,\\p_{0}&n=1,\end{przypadki}}}$

gdzie $},}$${\ Displaystyle u_ {1} (k): = {\ Frac {k + 1} {\ langle k \ rangle}} p_ {k$$}$ oznacza splotu n $displaystyle n$ -krotnie . Co więcej ${\ Displaystyle |\ langle k ^ {2} \ rangle -2 \ langle k \ rangle |}$ wyraźne $,$$i$ gdy jest bliskie zeru. Wyrażenia analityczne dla $displaystyle$ asymptot zależą od skończoności momentów wykładnika ogona rozkładu stopni (gdy $funkcje$$p_ {k$ \ ciężki ogon) i znak kryterium Molloya-Reeda. Poniższa tabela podsumowuje te relacje (stałe są podane w).

momenty ${\ displaystyle p_ {k}}$	ogon ${\ displaystyle p_ {k}}$	${\ Displaystyle {\ tekst {znak}} (\ langle k ^ {2} \ rangle -2 \ langle k \ rangle)}$	${\ Displaystyle w_ {n}, \; n \ gg 1, \; \ alfa = \ beta -2}$
${\ Displaystyle \ langle k ^ {3} \ rangle <\ infty}$	lekki ogon	-1 lub 1	${\ Displaystyle C_ {1} e ^ {-C_ {2} n} n ^ {- 3/2}}$
		0	${\ Displaystyle C_ {1} n ^ {- 3/2}}$
	ciężki ogon, ${\ Displaystyle \ beta > 4}$	-1	${\ Displaystyle C_ {3} n ^ {- \ alfa -1}}$
		0	${\ Displaystyle C_ {1} n ^ {- 3/2}}$
		1	${\ Displaystyle C_ {1} e ^ {-C_ {2} n} n ^ {- 3/2}}$
${\ Displaystyle \ langle k ^ {3} \ rangle = \ infty,}$ ${\ Displaystyle \ langle k ^ {2} \ rangle <\ infty,}$	ciężki ogon, ${\ Displaystyle \ beta = 4}$	-1	${\ Displaystyle C_ {3} n ^ {- \ alfa -1}}$
		0	$n}}}}$
		1	$} }e^{-C_{2}'{\frac {n}{\log n}}}}$
	ciężki ogon, ${\ Displaystyle 3 <\ beta <4}$	-1	${\ Displaystyle C_ {3} n ^ {- \ alfa -1}}$
		0	${\ Displaystyle C_ {4} n ^ {- {\ Frac {1} {\ alfa}} -1}}$
		1	${\ Displaystyle C_ {5} e ^ {-C_ {6} n} n ^ {- 3/2}}$
${\ Displaystyle \ langle k ^ {2} \ rangle = \ infty,}$ ${\ Displaystyle \ langle k \ rangle <\ infty,}$	ciężki ogon, ${\ Displaystyle \ beta = 3}$	1	${\ Displaystyle C_ {7} e ^ {-C_ {8} -C_ {9} n ^ {\ Frac {2} {\ pi}} }n^{{\frac {1}{\pi}}-2}}$
	ciężki ogon, ${\ Displaystyle 2 <\ beta <3}$	1	${\ Displaystyle C_ {10} e ^ {-C_ {11} n} n ^ {- 3/2}}$

Modelowanie

Porównanie z rzeczywistymi sieciami

Trzy ogólne właściwości złożonych sieci to heterogeniczny rozkład stopni, krótka średnia długość ścieżki i wysokie skupienie. Mając możliwość zdefiniowania dowolnej sekwencji stopni, pierwszy warunek może być spełniony projektowo, ale jak pokazano powyżej, globalny współczynnik grupowania jest odwrotną funkcją rozmiaru sieci, więc w przypadku sieci o dużej konfiguracji klastrowanie jest zwykle małe. Ta cecha modelu bazowego jest sprzeczna ze znanymi właściwościami sieci empirycznych, ale rozszerzenia modelu mogą rozwiązać ten problem (patrz ). $pierwiastek kwadratowy$ do drzewa, pod warunkiem, że średnia rozkładu nadmiaru stopni jest stała lub rośnie wolniej niż z liczby łączy . Innymi słowy, ten model zapobiega tworzeniu się podstruktur, takich jak pętle w limicie dużego rozmiaru. Zanikanie współczynnika grupowania jest szczególnym przypadkiem tego bardziej ogólnego wyniku. Podczas gdy właściwość drzewa sprawia, że ​​model jest mało realistyczny, tak wiele obliczeń, takich jak metody funkcji generującej , jest możliwych dzięki tej funkcji dla modelu konfiguracyjnego.

Zastosowanie: obliczanie modułowości

Model konfiguracyjny jest stosowany jako punkt odniesienia przy obliczaniu modułowości sieci . Modułowość mierzy stopień podziału sieci na moduły. Oblicza się to w następujący sposób:

${\ Displaystyle Q = {\ Frac {1} {2L}} \ suma _ {i \ neq j}{\Bigl (}A_{ij}-{\frac {k_{i}k_{j}}{2L}}{\Bigr)}\delta (C_{i},C_{j})}$

w którym $)$ sąsiedztwa sieci jest porównywana z prawdopodobieństwem posiadania krawędzi między węzłami $( w zależności od ich stopni$ w modelu konfiguracji ( szczegóły w modułowości strony ) .

Model konfiguracji ukierunkowanej

W DCM (model konfiguracji ukierunkowanej) każdemu węzłowi przypisana jest pewna liczba półkrawędzi zwanych ogonami i głowami. Następnie ogony i głowy są dopasowywane równomiernie losowo, aby utworzyć skierowane krawędzie. Rozmiar gigantycznego komponentu, typowa odległość i średnica DCM zostały zbadane matematycznie. Przeprowadzono również szeroko zakrojone badania dotyczące losowych spacerów w DCM. DCM wymodelował niektóre rzeczywiste złożone sieci, takie jak sieci neuronowe, finansowe i społecznościowe.

Model konfiguracji ukierunkowanej