Struktur maximal dissortativer Netzwerke

-0.4 -0.2 0 0.2 0.4 0.6

2⁶ 2⁸ 2¹⁰ 2¹² 2¹⁴ 2¹⁶ 2¹⁸ rmax

N

γ= 2.1 γ= 2.3 γ= 2.5 γ= 2.7 γ= 2.9

Abbildung 3.9: Pearson-Koeffizient rmax f¨ur maximal assortative Netzwerke als Funktion der Netzwerkgr¨oße Nund f¨ur verschiedeneγ. Alle Datenpunkte sind Mittel-werte ¨uber 100 Netzwerke mit minimalem Gradk0= 6, der Fehlerbalken gibt die Standardabweichung. Die ge-strichelten Linien sind Fits nach Gleichung (3.48). In Ubereinstimmung mit den theoretischen Ergebnissen er-¨ gibt sich f¨urγ <2.5 ein negativer Korrelationskoeffizient rmax, obwohl die zugrunde liegenden Netzwerke maximal assortativ sind.

mitk₀-Knoten verbunden. Sobald die Netzwerke groß genug sind, h¨angt der Wert von κ₀ selbst nicht mehr vonN ab, siehe Abb. 3.10(a) und (b).

F¨ur eine genauere Analyse betrachten wir nun einige Adjazenzmatrizen maximal dis-sortativer Netzwerke in Abbildung 3.11. Wir sehen f¨ur alle drei Netzwerkgr¨oßen in (a)-(c)

k_me

kme

κ0

κ0

κ1

κ1

kmax

kmax

k₀

k0

k1

k1

k₂

k2

· · ·

· · ·

· · ·

k_me

kme

κ0

κ0

κ1

κ1

kmax

kmax

k₀

k0

k1

k1

k₂

k2

· · ·

· · ·

· · ·

k_me

kme

κ₀

κ0

κ1

κ1

kmax

kmax

k₀

k0

k1

k1

k₂

k2

· · ·

· · ·

· · ·

(a)N = 256 (b)N = 512 (c) N = 1024

Abbildung 3.11.: Darstellung der AdjazenzmatrixA f¨ur dreimaximal dissortativeNetzwerke mit γ = 2.9, k0 = 6, sowie verschiedenen Gr¨oßen (a) N = 256, (b) N = 512 und (c) N = 1024.

Sind zwei Knoteni und j miteinander verbunden, so ist der entsprechende EintragAij = 1 rot dargestellt, ansonsten bleibt das Fl¨achenelement weiß. Wie in Abb. 3.7 sind die Eintr¨age der MatrixA gem¨aß der Grade der Knoten angeordnet. Zur Orientierung sind jeweils oberhalb und links der Adjazenzmatrizen Balken eingezeichnet, die Gruppen von Knoten gleichen Grades durch eine gemeinsame Farbe hervorheben. F¨ur alle Netzwerkgr¨oßen in (a)-(c) finden wir ausgepr¨agte rechteckige Strukturen. Diese repr¨asentieren Doppelschichten von Knoten, in denen Knoten kleinen Grades mit Knoten großen Grades verbunden sind.

deutlich ausgepr¨agte rechteckige Strukturen. Diese Strukturen entsprechen verschachtel-ten Doppelschichverschachtel-ten von Knoverschachtel-ten, in denen Knoverschachtel-ten niedrigen Grades mit Knoverschachtel-ten hohen Grades verbunden sind. Die ¨außerste Doppelschicht besteht aus den Knoten mit Grad k₀, die mit Knoten vom Grad κ₀ . k ≤ k_max verbunden sind. In der zweiten Doppel-schicht sind k₀+ 1-Knoten mit Knoten vom Gradκ₁ .k.κ₀ verbunden, in der dritten Schicht entsprechend k₀+ 2 Knoten mit Knoten vom Grad κ₂ .k.κ₁ usw. Zus¨atzlich zu den rechteckigen Bereichen beobachten wir bei kleinen Netzwerken in 3.11(a) und (b), dass sich in der letzten Zeile bzw. Spalte der Adjazenzmatrizen ein roter Bereich ¨uber mehrere Schichten hinweg erstreckt. Dieser Bereich entspricht dem k_max-Knoten, der so viele Verbindungen hat, dass er sich mit mehreren niedrigenk-Schichten verbinden muss.

Dadurch wird auch der Verlauf von K_nn(k) f¨ur großek bestimmt, wie er in Abb. 3.10 zu sehen ist. Sind keine Knoten mit zu großem k vorhanden, so verl¨auft Knn(k) flach, mit K_nn(k & κ₀) ≃k₀, wie etwa in Abb. 3.10(a) f¨ur γ = 2.9 zu sehen ist. Gibt es hingegen Knoten mit sehr großem k im Netzwerk, so f¨allt K_nn(k) weniger steil ab und steigt mit-unter sogar wieder kurz an f¨ur k.kmax, wie beispielsweise in den Kurven f¨ur γ = 2.1 in Abb. 3.10(c).

Im Folgenden wollen wir diese Effekte genauer betrachten und quantifizieren. Wir be-ginnen mit dem Einfluss des k_max-Knotens. F¨ur kleine Netzwerke mit N < N₁ ist der maximale Grad durch k_max = N −1 gegeben, d.h. ein Knoten diesen Grades ist mit allen ¨ubrigen Knoten des Netzwerkes verbunden. Mit der Definition von k_max aus (2.3)

bestimmt sichN₁ zu

N₁≡k

γ−1 γ−2

0 . (3.49)

Ab Netzwerkgr¨oßenN > N₁durchsetzt ein Knoten mitk_maxzwar nicht mehr das gesamte Netzwerk, aber immer noch einen großen Teil, n¨amlich alle Knoten mitk₀≤k≤k_A. Der Wert vonk_A l¨asst sich berechnen aus

kmax=

kA

X

k=k0

N_k≈ Z kA

k0

N P(k)dk= 1 1−γ

N

A k_A^1−γ−k₀^1−γ

, (3.50)

nachk_Aaufgel¨ost findet man k_A=k₀

1− 1−_N¹

k₀N^2γ−1−γ_1−γ¹

. (3.51)

Aus (3.51) erh¨alt man etwa f¨ur N = 256, γ = 2.9 und k0 = 6 den Wert kA ≈ 8, in guter ¨Ubereinstimmung mit Abb. 3.11(a), wo der k_max-Knoten bis in die k = 8 Schicht hineinragt. Im Grenzfall großer Netzwerke mitN ≫ N₁ verh¨alt sich (3.51) wie k_A ≈k₀, d.h. alle Kanten eines Knotens mit kmax f¨uhren zu Knoten mit Grad k0. In der Darstel-lung der Adjazenzmatrizen aus 3.11 bedeutet dies, dass derk_maxKnotens f¨ur großeN in die ¨außerste Doppelschicht integriert wird. Die k₀-Knoten stellen in großen Netzwerken sogar so viele Kanten, dass sie ¨uberkmax hinaus auch alle Kanten von Knoten abs¨attigen k¨onnen, deren Grad k gr¨oßer als ein bestimmtes κ₀ ist. Dies f¨uhrt zur Bildung der ¨au-ßersten Doppelschicht, wie sie weiter oben beschrieben wurde. Der Wert vonκ₀ l¨asst sich bestimmen aus

N_k0k0 =

kmax

X

k=κ0

N_kk , (3.52)

bzw.

N P(k₀)k₀ =

kmax

X

k=κ0

N P(k)k≈ Z _kmax

κ0

N P(k)k dk= 1 2−γ

N

A k_max^2−γ−κ^2−γ₀

. (3.53) Nachκ₀ aufgel¨ost ergibt sich

κ0=k0

γ−2

k0 +N^2−γγ−1_2−γ¹

. (3.54)

Aus (3.54) folgt f¨urN ≫N₂, mit

N₂≡ k₀ γ−2

^γ−1

γ−2 (3.55)

der asymptotische,N-unabh¨angige Wert κ₀ ≈κ^∞₀ ≡k

γ−1 γ−2

0 γ−2₂¹

−γ . (3.56)

F¨ur γ = 2.9 und γ = 2.5 l¨asst sich dieses Verhalten auch gut in den Abb. 3.10(a) und (b) erkennen, in denen jeweils die Werte f¨urκ^∞₀ eingezeichnet sind, wie sie sich aus (3.56)

ergeben. AbN = 2¹⁰ in (a) bzw.N = 2¹⁴in (b) sind alle Knoten mitk≥κ^∞₀ mit Knoten aus der k₀-Schicht verbunden und der mittlere Grad der n¨achsten Nachbarn ist folglich gegeben durch K_nn(k) ≃k₀. F¨ur γ = 2.1 hingegen ist nach (3.55) N₂ ≃3.6·10¹⁹ >2⁶⁴, folglich sind die in Abb. 3.10 (c) untersuchten Netzwerke noch viel zu klein, um dieses Verhalten beobachten zu k¨onnen.

Mit dem Ausdruck (3.56) f¨urκ0 kann man nun auch n¨aherungsweise die oberen Grenzen κ_n der folgenden Doppelschichten angeben. Analog zu (3.52) bestimmt sich der Wert von κ₁ aus

N_k0+1(k₀+ 1) =

κ0

X

k=κ1

N_kk , (3.57)

die h¨oheren Werteκ₂, κ₃, . . . erh¨alt man anschließend durch Iteration von (3.57) mit ent-sprechend angepassten Summationsindizes. Wie in Abb. 3.11 zu sehen ist, ist die Folge der Doppelschichten in der Mitte begrenzt durch eine einfache Schicht von Knoten mit Grad k_me. Dieser Grad ist dadurch gekennzeichnet, dass alle Knoten mit Gradk≤k_me genauso viele Kanten haben, wie die Knoten mit Grad k ≥ k_me. Durch L¨osung der impliziten Gleichung

kme

X

k=k0

N_kk=

kmax

X

k=kme

N_kk (3.58)

erh¨alt man

k_me = 2^γ−21 k₀

1 +N^2−γγ−1_2−γ¹

. (3.59)

F¨ur große Netzwerke wird dieser Ausdruck unabh¨angig vonN und man findet das asym-ptotische Verhalten

k_me≈k_me^∞ ≡2^γ−12k₀. (3.60) Dadurch ist auch die AnzahlN_d der Doppelschichten im Netzwerk, die sich aus k_me−k₀ ergibt nach oben hin begrenzt:

N_d≤max(N_d)≡k_me−k₀ ≤k^∞_me−k₀. (3.61)

Skalierung des Pearson-Koeffizienten r_min

Abschließend wollen wir nun die Skalierung des Pearson-Koeffizienten rmin f¨ur maximal dissortative Netzwerke bestimmen. Analog zum Ausdruck f¨ur maximal assortative Netz-werke in (3.32) ist r_min gegeben durch

r_min= min(A_r)−B_r

C_r−B_r . (3.62)

F¨ur die weiteren ¨Uberlegungen ist es vorteilhaft, allen Kanten eine bestimmte Richtung zuzuordnen, d.h eine bestimmte Kante m geht von einem Knoten mit Gradj_m aus und

verweist auf einen zweiten Knoten mit Grad k_m. Nun indizieren wir die Kanten so, dass die Grade der Knoten, auf die sie verweisen, ansteigen:

k₁ ≤k₂ ≤ · · · ≤k_M. (3.63) In dissortativen Netzwerken sind Knoten mit großem Grad bevorzugt mit Knoten mit kleinem Grad verbunden. Entsprechend wird auch die Summe in A_r dadurch minimiert, dass die Grade der Knoten, von denen die Kanten in (3.63) ausgehen, abnehmen. Dies entspricht gerade der umgekehrten Reihenfolge vonk₁, k₂, . . . , k_M in (3.63), also

j_m=J_m≡k_M−m, (3.64)

und

J1≥J2≥ · · · ≥JM. (3.65) In Netzwerken, in denen Selbst- und Mehrfachverbindungen zugelassen sind, ist es im-mer m¨oglich, ein gegebenen Netzwerk so umzuordnen, dass (3.63)–(3.65) erf¨ullt sind. Im Gegensatz zu assortativen Netzwerken sind in dissortativen Netzwerken Mehrfachverbin-dungen nicht problematisch, da es sehr viele Knoten kleinen Grades gibt, die sich mit den wenigen Knoten hohen Grades verbinden k¨onnen, ohne dass Mehrfachverbindungen notwendig w¨urden. Im Grenzfall großer Netzwerke verschwindet der Anteil von Mehrfach-verbindungen und wir k¨onnen (3.63)–(3.65) auch f¨ur einfache Netzwerke verwenden. Mit (3.63) und (3.64) erhalten wir

min(A_r) =

M

X

m=1

k_mJ_m=

M

X

m=1

k_mk_M−m. (3.66)

Der Termk_mk_M−m ¨andert sich nicht, wenn manm durchM−m ersetzt und es folgt min(Ar) = 2

M

X

m=M/2

kmJm= 2

M

X

m=M/2

kmkM−m. (3.67) Die Faktoren J_m =k_M−m sind auch ihrer Gr¨oße nach geordnet und erf¨ullen die Unglei-chungen

J_M/2 =k_M/2 ≥Jm ≥JM =k0 f¨ur M/2≤m≤M . (3.68) Mit Hilfe dieser Ungleichungen k¨onnen wir folgende untere und obere Schranken f¨ur min(A_r) in (3.67) ableiten:

2k_M/2

M

X

m=M/2

k_m≥min(A_r)≥2k₀

M

X

m=M/2

k_m. (3.69)

Per Konstruktion ist dabei der Wert vonk_M/2 gegeben durch den mittleren Gradk_me, f¨ur den alle Knoten mit Gradk < k_me genauso viele Kanten haben, wie die Knoten mit Grad k > k_me. Den Wert vonk_me hatten wir bereits in (3.59) abgeleitet:

k_me = 2^γ−21 k₀

1 +N^2γ−1−γ_2−γ¹

. (3.70)

F¨ur großeN ergibt sich aus (3.70) das Verhalten

k_me ≈2^γ−21 k₀N^γ−11 f¨ur 1< γ <2 (3.71)

≈2^γ−21 k₀ f¨ur 2< γ . (3.72)

Die Summe ¨uber M/2 Kanten in (3.69) kann wieder in eine Summe ¨uber Grade umge-wandelt werden:

M

X

m=M/2

k_m=

kmax

X

k=kme

N P(k)k² ≈ Z kmax

kme

N P(k)k²dk= N A

1

3−γ k_max^3−γ−k_me^2−γ

, (3.73) zusammen mit dem asymptotischen Verhalten f¨urk_me in (3.72) finden wir

M

X

m=M/2

k_m∼k²₀N^γ−12 f¨ur 1< γ <3 (3.74)

∼k₀N f¨ur 3< γ . (3.75)

Nun k¨onnen wir das asymptotische Verhalten vonkmeundPM

m=M/2km in (3.71)–(3.72) und (3.74)–(3.75) mit den beiden Ungleichungen in (3.69) kombinieren. Zun¨achst f¨ugen wir (3.71) und (3.74) in (3.69) ein und erhalten

c₁k₀³N^γ−13 ≥min(A_r)≥c₂k₀³N^γ−12 (3.76) f¨ur 1< γ <2, mit den beiden von γ abh¨angigen Konstantenc₁ und c₂. Hieraus folgt f¨ur großeN das asymptotische Verhalten

min(A_r)∼k₀³N^ζ f¨ur 1< γ <2 (3.77) wobei der Exponentζ die Ungleichungen

2

γ−1 ≤ζ ≤ 3

γ −1 (3.78)

erf¨ullt. Mit den Relationen (3.72) und (3.74), zusammen mit den Ungleichungen (3.69) erhalten wir

c^′₁k³₀N^γ−21 ≥min(A_r)≥c₂k₀³N^γ−21 (3.79) f¨ur 2< γ <3, also

min(A_r)∼k³₀N^γ−12 f¨ur 2< γ <3. (3.80) F¨ur den Bereich γ > 3 kombinieren wir schließlich (3.72) und (3.75) mit (3.69) und erhalten

min(A_r)∼k³₀N f¨ur 3< γ . (3.81) Mit (3.77)–(3.81) haben wir nun das asymptotische Verhalten von min(A_r) f¨ur große N bestimmt. Zusammen mit den Ausdr¨ucken f¨ur B_r und C_r in (3.33)–(3.37) k¨onnen wir

jetzt die Skalierung des Pearson-Koeffizienten r_min f¨ur maximal dissortative Netzwerke nach (3.62) angeben:

r_min∼















−const₁(γ, k₀) f¨ur γ <2

−N^2−γγ−1 f¨ur 2< γ <3

−N^γ−4γ−1 f¨ur 3< γ <4

−const₂(γ, k₀) f¨ur γ >4

(3.82)

F¨ur 2 < γ < 4 folgt aus (3.82), dass der Korrelationskoeffizient im Grenzfall großer Netzwerke zu Null geht. Abbildung 3.12 zeigt r_min als Funktion der Netzwerkgr¨oße f¨ur verschiedeneγ, wie es aus Simulationen hervorgeht, die gestrichelten Linien sind Fits nach (3.82).

-0.8 -0.6 -0.4 -0.2 0

2⁶ 2⁸ 2¹⁰ 2¹² 2¹⁴ 2¹⁶ rmin

N

γ= 2.1 γ= 2.3 γ= 2.5 γ= 2.7 γ= 2.9

Abbildung 3.12: Pearson-Koeffizient rmin f¨ur maximal dissortative Netzwerke als Funktion der Netzwerkgr¨oße Nund f¨ur verschiedeneγ. Alle Datenpunkte sind Mittel-werte ¨uber 100 Netzwerke mit minimalem Gradk0= 6, der Fehlerbalken gibt die Standardabweichung. Die ge-strichelten Linien sind Fits nach Gleichung (3.82). In Ubereinstimmung mit der Theorie geht¨ rminf¨ur alle be-trachteten Werte vonγf¨ur große Netzwerke zu Null.

ドキュメント内 Jörg Menche diss menche (ページ 39-45)