Struktur maximal assortativer Netzwerke

F¨ur einen ersten Einblick in die Struktur maximal assortativer Netzwerke betrachten wir f¨ur einige Beispiele die in Abschnitt 2.1 eingef¨uhrte Adjazenzmatrix A, siehe Abb. 3.7.

Wie in der Bildunterschrift n¨aher erl¨autert wird, wurden die Eintr¨ageA_ij der Matrix dabei so angeordnet, dass die Gradstruktur der Netzwerke sichtbar wird. In dieser Darstellung sehen wir deutlich von einander abgegrenzte quadratische Bereiche. Diese Bereiche repr¨a-sentieren Schichten von Knoten gleichen Grades, die untereinander verbunden sind, siehe auch [66]. Ein Vergleich der Abbildungen 3.7(a)-(c) zeigt, dass die Anzahl solcher Schich-ten mit der Netzwerkgr¨oße ansteigt. Weiterhin finden wir in den Adjazenzmatrizen f¨ur große Grade k.k_max einen ausgeschmierten Bereich, in dem Knoten hohen Grades mit einer ganzen Reihe von Knoten unterschiedlichen Grades verbunden sind. Je nach Netz-werkgr¨oße ist dieser Bereich unterschiedlich stark ausgepr¨agt, je kleiner das Netzwerk, desto st¨arker.

F¨ur eine genauere Betrachtung zeigt Abbildung 3.8 den mittleren Grad K_nn der n¨ach-sten Nachbarn eines beliebigen Knotens mit Grad kf¨ur Netzwerke verschiedener Gr¨oßen N und Exponentenγ. Die Mehrzahl der Kurven weist einen Bereich kleiner Gradek≤k_s auf, f¨ur die K_nn(k) ≃ k gilt. Dies entspricht wieder den eben beschriebenen Schichten von Knoten, innerhalb derer die Knoten alle ihre Kanten mit Knoten gleichen Grades

”s¨attigen“ k¨onnen. Wir sehen ebenfalls deutlich, dass der Wert vonk_smitN w¨achst. Dem Bereich k ≤ k_s schließt sich ein Bereich von k Werten an, f¨ur die K_nn(k) > k gilt. Die entsprechenden Knoten sind also nicht mehr ausschließlich mit anderen Knoten gleichen Grades verbunden, sondern auch mit Kanten von Knoten gr¨oßeren Grades. Diese Kan-ten kommen von den KnoKan-ten, die einen sehr hohen Grad haben, gleichzeitig aber nicht zahlreich genug sind, um sich nur mit ihresgleichen zu verbinden, sodass sie Kanten in Schichten mit Knoten mit niedrigeremk

”exportieren“ m¨ussen. Wie im Vorherigen bereits erl¨autert, f¨uhrt dies zu der dissortativen Flanke in K_nn f¨ur große k, wie sie auch wieder

k_max

kmax

k0

k0

k0+1

k0+1

k0+2

k0+2

· · ·

· · ·

k_max

kmax

k0

k0

k0+1

k0+1

k0+2

k0+2

· · ·

· · ·

k_max

kmax

k0

k0

k0+1

k0+1

k0+2

k0+2

· · ·

· · ·

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

Abbildung 3.7.: Darstellung der AdjazenzmatrixA f¨ur drei maximal assortative Netzwerke mit γ = 2.5, 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ß. Um die Gradstruktur der Netzwerke sichtbar zu machen, wurden die Eintr¨age der Matrix A gem¨aß der Grade der Knoten angeordnet. Oben links beginnend wurden zun¨achst die Verbindungen aller Knoten mit Gradk0 dargestellt, danach diejenigen der Knoten mitk0+ 1, anschließen Knoten mitk0+ 2 usw., die letzte Zeile, bzw. Spalte repr¨asentiert die Verbindungen deskmax-Knotens. Zur Orientierung sind jeweils oberhalb und links der Adjazenzmatrizen Balken eingezeichnet, die Gruppen von Knoten gleichen Grades durch eine gemeinsame Farbe hervorheben. Aufgrund der Symmetrie Aij = Aji der Adjazenzmatrix sind die Abbildungen symmetrisch bez¨uglich der Hauptdiagonalen. In allen drei F¨allen (a)-(c) sind eindeutig Schichten von Knoten gleichen Grades erkennen, die untereinander verbunden sind. Die Anzahl dieser Schichten nimmt dabei mit steigender Netzwerkgr¨oße von (a) nach (c) zu.

in Abb. 3.8 f¨ur alle Kurven zu beobachten ist. Der Vergleich der drei Teilabbildungen verdeutlicht den Einfluss des Exponenten γ auf den Verlauf von K_nn(k). W¨ahrend sich f¨urγ = 2.5 in (b) ab einer Netzwerkgr¨oße von N = 2¹⁰ Schichten mitKnn(k) = k aus-bilden, ist f¨ur γ = 2.1 in (c) der dissortative Teil von K_nn so dominant, dass keine der Kurven einen derartigen Bereich mehr aufweist. Im Folgenden wollen wir einige analyti-sche ¨Uberlegungen anstellen, um die Struktur maximal assortativer Netzwerke genauer zu verstehen.

Skalenfreie Netzwerke zeichnen sich durch eine nichtverschwindende Anzahl von Knoten mit sehr vielen Kanten aus. Es gibt allerdings viel zu wenige solcher Knoten, als dass sie sich in assortativen Netzwerken nur miteinander verbinden k¨onnten. Auf der anderen Seite gibt es eine große Zahl von Knoten mit kleinem Grad, die man theoretisch nur unterein-ander verkn¨upfen k¨onnte. Zwischen diesen beiden Extremen liegt der Grad ˆk, bei dem die Anzahl von KnotenN_kˆ genau ausreicht, um einen sog. vollst¨andigen Graphen zu bilden, in dem jeder Knoten mit allen anderen Knoten verbunden ist. Im gesamten Netzwerk gibt esN_kˆˆk Kanten, die von Knoten mit Grad ˆk abgehen. Wenn alle entsprechenden Knoten miteinander verbunden einen vollst¨andigen Graphen bilden, gilt

N_ˆkˆk

2 =N_ˆk(N_ˆk−1)

2 , (3.13)

oder

ˆk=N_ˆk−1. (3.14)

10¹ 10² 10³

10¹ 10² 10³

Knn

ks k

Knn(k) =k N= 2¹⁸ N= 2¹⁴ N= 2¹⁰ N= 2⁷

10¹ 10² 10³ 10⁴

10¹ 10² 10³ 10⁴ Knn

k ks

Knn(k) =k N= 2¹⁸ N= 2¹⁴ N= 2¹⁰ N= 2⁷

10¹ 10² 10³ 10⁴ 10⁵

10¹ 10² 10³ 10⁴ 10⁵ Knn

k

Knn(k) =k N= 2¹⁸ N= 2¹⁴ N= 2¹⁰ N= 2⁷

(a)γ = 2.9 (b) γ= 2.5 (c)γ = 2.1

Abbildung 3.8.: Mittlerer Grad Knn n¨achster Nachbarn von Knoten mit Grad k f¨ur maximal assortativeNetzwerke. Die einzelnen Kurven innerhalb einer Teilabbildung zeigen die Daten ver-schiedener Netzwerkgr¨oßen N bei gleichem Exponenten γ: (a) γ = 2.9, (b) γ = 2.5, sowie (c) γ= 2.1. In (a) und (b) gibt es f¨ur gen¨ugend große Netzwerke einen Bereich kleiner Gradek≤ks, f¨ur die Knn(k) = kgilt. F¨ur N = 2¹⁸ ist dieser Wert von ks jeweils eingezeichnet. F¨ur gen¨ugend großekweisen Kurven einen dissortativen Bereich auf, in demKnnmit steigendem kabf¨allt. Alle Kurven sind Mittelwerte ¨uber 100 Netzwerke mit minimalem Gradk0= 6. Die maximal assortative Konfiguration wurde erzielt durch 1000M-faches Umordnen mitp= 1, siehe Abschnitt 3.3.

Die Anzahl der Knoten eines bestimmten Grades ist gegeben durch

N_k=N P(k), (3.15)

setzt man (3.15) in (3.13) ein und n¨ahert N_ˆk−1 durchN_kˆ, erh¨alt man schließlich ˆk=

N A

_γ+1¹

. (3.16)

Knoten mitk≤ˆk k¨onnen theoretisch ausschließlich mit Knoten gleichen Grades verbun-den werverbun-den. Knoten mit k > ˆk hingegen k¨onnen von ihrenN_kk Kanten nurN_k(N_k−1) mit anderen Knoten mit Grad k verbinden, den Rest m¨ussen sie mit Knoten mit ande-rem Grad verbinden. F¨ur das gesamte Netzwerk ergibt sich somit folgende Anzahl M_ean Kanten, die

”exportiert“ werden m¨ussen:

Me≡

kmax

X

k=ˆk

N_kk−N_k(N_k−1)

≈ Z _kmax

ˆk

N_kk−N_k(N_k−1) dk=

Z _kmax

ˆk

N P(k)k−N P(k) N P(k)−1 dk

= _2−γ^{1 N}_Ah

k₀^2−γN^2γ−1−γ − ^N_A^2−γ_γ+1i

−_1−2γ^{1 N}_A2h

k^1−2γ₀ N^{1γ−1−2γ} − ^N_A^1−2γ_γ+1 i

−_1−γ^{1 N}A

h

k^1−γ₀ N^1γ−−γ1 − ^NA

^1−γ_γ+1i

(3.17) Betrachtet man nur die f¨ur großeN f¨uhrenden Terme in den eckigen Klammern in (3.17), so erh¨alt man f¨urγ >2 schließlich

M_e≈ 1

γ−2− 1 2γ−1

N A

_γ+1³

(3.18)

f¨ur die Anzahl an Kanten, die von Knoten mit k > kˆ ausgehend mit Knoten mit k ≤ ˆk verbunden werden m¨ussen. Dadurch verringert sich die Anzahl der Kanten M_s, die ausschließlich unter Knoten gleichen Grades verbunden werden k¨onnen:

Ms ≡M_k≤ˆk−Me, (3.19)

wobeiM_k≤ˆk die Anzahl aller Kanten ist, die von Knoten mitk≤kˆ ausgehen:

M_k≤ˆk=

ˆk

X

k=k0

N_kk≈ Z ˆk

k0

N P(k)k dk= 1

γ−2 k₀^2−γN A −

N A

_γ+1³ !

(3.20) Zusammen mit dem Ausdruck f¨urMe in (3.18) ergibt sich daraus f¨urMs in (3.19)

M_s= k₀^2−γ γ−2

N A −

2

γ−2 − 1 2γ−1

N A

³

γ+1

. (3.21)

Dieser Ausdruck wird erst positiv ab einer bestimmten Netzwerkgr¨oßeN_b, die vonγ und k₀ abh¨angt:

N_b= k²₀ γ−1

3γ 2γ −1

^γ+1_γ−2

(3.22) F¨ur Netzwerke mit N < N_b ist die Zahl der Kanten, die von Knoten mit k > kˆ ex-portiert werden so groß, dass sich keine Schicht kleiner Grade k ≤ k_s ausbilden kann, innerhalb derer Knoten ausschließlich mit Knoten gleichen Grades verbunden sind. Tabel-le 3.1 gibt die ZahTabel-lenwerte, wie sie sich aus (3.22) ergeben f¨ur Netzwerke mit denselben Parametern wie in Abb. 3.8. Anhand dieser Tabelle l¨asst sich verstehen, dass f¨urγ = 2.9

γ N_b

2.9 250

2.5 1956 2.1 ≃4.3·10¹⁰

Tabelle 3.1: Zahlenwerte aus (3.22) f¨ur die Netzwerkgr¨oßeNb, ab der sich Schichten von Knoten mit kleinemk ausbilden k¨onnen, die ausschließlich untereinander verbunden sind. Vergleiche mit den Kurven f¨ur Knn(k) in Abb. 3.8, die f¨ur Netzwerke mit denselben Parametern erstellt wurden.

in Teilabbildung 3.8(a) alle Netzwerkgr¨oßen einen Bereich kleiner Grade zeigen, die sich selbst s¨attigen k¨onnen, w¨ahrend es f¨ur γ = 2.1 in (c) keine solche Schichten gibt, da die gr¨oßten simulierten Netzwerke mit N = 2¹⁸ = 262144 immer noch viel kleiner sind als N_b≃4.3·10¹⁰.

Mit Hilfe vonM_e l¨asst sich nun auch eine Absch¨atzung f¨urk_s angeben, also den Grad, bis zu dem in einem maximal assortativen Netzwerk alle Knoten sich untereinander mit Knoten gleichen Grades verbinden k¨onnen. F¨ur diesen Bereich stehen insgesamtMs Kan-ten zur Verf¨ugung, d.h. es gilt

M_s=

ks

X

k=k0

N_kk≈ Z ks

k0

N P(k)k dk= N A

1 γ−2

k^2−γ₀ −k^2−γ_s

(3.23) Nachk_s aufgel¨ost erh¨alt man daraus mitM_s aus (3.21)

k_s=k

γ−1 γ+1

0 (γ−1)^γ+11 3γ

2γ−1 _2−γ¹

N^γ+11 , (3.24)

was gut mit den Werten aus den Simulationen ¨ubereinstimmt, siehe Abb. 3.8, wo f¨ur γ = 2.5 und γ = 2.9 jeweils die Werte aus (3.24) f¨ur N = 2¹⁸ eingezeichnet sind. Wie aus (3.24) in ¨Ubereinstimmung mit den Simulationen weiterhin hervorgeht, w¨achstk_s mit der Netzwerkgr¨oße, es bilden sich mit wachsendemN also mehr und mehr Schichten von Knoten aus, die ihre Kanten vollst¨andig assortativ mit Knoten gleichen Grades s¨attigen k¨onnen.

Skalierung des Pearson-Koeffizienten r_max

Nach der ausf¨uhrlichen Diskussion der Eigenschaften von K_nn(k) wollen wir nun unter-suchen, wie sich derPearson-Koeffizientr bei maximal assortativen Netzwerken verh¨alt.

Wir beginnen nochmals mit der Definition vonr aus (3.5):

r = PM

m=1j_mk_m−_M¹ PM

m=1k_m2

P_M

m=1k²_m− _M¹ P_M

m=1k_m2 (3.25)

Im gesamten Netzwerk gibt es N_k = N P(k) Knoten mit Grad k und somit N P(k)k Kanten, die von ihnen abgehen. Die Summen ¨uber alle KantenMin (3.25) k¨onnen dadurch umgeschrieben werden in Summen ¨uber alle Grade:

M

X

m=1

k_m =

kmax

X

k=k0

N P(k)k²=Nhk²i^N (3.26)

M

X

m=1

k_m² =

kmax

X

k=k0

N P(k)k³=Nhk³i^N (3.27) Mit diesen beiden Beziehungen (3.26) und (3.27) k¨onnen wir den Assortativit¨atskoeffizi-enten (3.25) nun in Abh¨angigkeit der Momente der Gradverteilung schreiben und erhalten

r≡A_r−B_r

C_r−B_r, (3.28)

mit

A_r≡

M

X

m=1

j_mk_m, (3.29)

B_r≡N²

Mhk²iN², (3.30)

und

C_r≡Nhk³i^N. (3.31)

Die Momente der Gradverteilung h¨angen nicht von der Assortativit¨at des Netzwerkes ab, der einzige Term, der sich dadurch in (3.28) ¨andert ist A_r. Die maximale Assortativit¨at l¨asst sich somit ausdr¨ucken als

r_max= max(A_r)−B_r

C_r−B_r . (3.32)

Aus den Ausdr¨ucken f¨urM in (2.12), sowie den Momenten der Verteilung in (2.11) folgt, dassB_r in (3.30) im Grenzfall großer Netzwerke skaliert wie

B_r ∼k³₀N^γ−31 f¨ur 1< γ <2 (3.33)

∼k³₀N^5−γγ−1 f¨ur 2< γ <3 (3.34)

∼k³₀N f¨ur 3< γ . (3.35) Das Verhalten vonC_r ist gegeben durch

C_r∼k₀³N^γ−31 f¨ur 1< γ <4 (3.36)

∼k₀³N f¨ur 4< γ . (3.37) Den ¨Uberlegungen zur Struktur maximal assortativer Netzwerke folgend, sch¨atzen wir die Summe max(A_r) durch drei einzelne Teilsummen ab:

max(A_r) =b₁+b₂+b₃ (3.38)

Den Beitragb1 bilden die Schichtenk≤ks, in denen Knoten ausschließlich mit gleicharti-gen Knoten verbunden sind. Den zweiten Beitragb₂ stellt der Teil der Kanten der Knoten mitk≥k, die Knoten gleichen Grades zu vollst¨andigen Graphen verbinden. Den letztenˆ Teilb3 bilden schließlich die exportierten Kanten.

Wir beginnen mit Beitragb₁. In der Schicht der Knoten mitk≤k_sgibt es jeweils ¹₂N_kk Kanten, an deren beiden Enden sich Knoten mit Gradk befinden. Ihr Beitrag zu A_r ist also

b₁≡

ks

X

k=k0

1

2N_kk k² ≈ Z _ks

k0

1

2N P(k)k³dk

= 1

2(4−γ) 3γ

2γ−1

^4−γ_2−γ N A

_γ+1⁵

− k₀^4−γ 2(4−γ)

N

A . (3.39) Den zweiten Beitrag bilden die ¹₂N_k(N_k−1) Kanten aus kompletten Graphen, die jeweils zwei Knoten mit Gradk verbinden:

b2≡

kmax

X

k=ˆk 1

2N_k(N_k−1)k² ≈

kmax

X

k=ˆk 1

2N_k²k² ≈ Z kmax

ˆk 1

2 N P(k)2

k²dk

= 1

2(2γ −3)

"

N A

⁵

γ+1

− k₀^3−2γ A² N^γ−11

#

(3.40) Der dritte Beitragb₃besteht aus denM_eKanten, die die Knoten mitk >ˆknicht unterein-ander verbinden k¨onnen. Wir sch¨atzen ihren Anteil an max(Ar) ab, indem wir annehmen, dass diese Kanten von Knoten mit Grad ˆk < k ≤ k_max ausgehend sich mit Knoten mit Gradks< k≤kˆ verbinden. Der mittlere Grad am Ende einer beliebigen Kante in diesen beiden Schichten ist gegeben durch

k_s< k≤ˆk

M, bzw. durchˆk < k≤k_max

M. In dieser groben N¨aherung ist der Anteil dieser Kanten an max(Ar) also gegeben durch

b₃≡M_e

k_s< k≤ˆk

M

k < kˆ ≤k_max

M. (3.41)

Die Mittelwerte in (3.41) berechnen sich nach k₁ < k≤k₂

M ≡ R_k2

k1 P_M(k)k dk Rk2

k1 PM(k)dk , (3.42)

mit der Definition f¨urP_M(k) aus (2.5) folgt k_s< k≤kˆ

M = γ−2 3−γ

2γ−1 γ+ 1 1−

3γ 2γ−1

^3−γ₂

−γ

! N A

_γ+1¹

(3.43) und

ˆk < k≤k_max

M = γ−2

3−γ A^2γ+1−γk^3−γ₀ N

5−γ

γ2−1 . (3.44)

Zusammen mit M_e aus (3.18) ergibt sich aus (3.43) und (3.44) f¨urb₃ in (3.41) b₃ =k^3−γ₀ γ−2

(3−γ)² 1− 2

3 − 1 3γ

^3−γ_γ−2!

A^−γ+2γ+1N

3γ+1

γ2−1. (3.45) F¨uhrt man die drei Beitr¨age aus (3.39) (3.40) und (3.45) zusammen, erh¨alt man f¨ur große Netzwerke schließlich folgendes Verhalten von max(A_r) in (3.38):

max(A_r)≈αN^γ+15 +βN^γ+15 +δN

3γ+1

γ2−1 , (3.46)

mit den drei γ−und k₀−abh¨angigen Konstanten α, β und δ. Ein Vergleich der einzelnen Betr¨age liefert

max(A_r)∼ (N

3γ+1

γ2−1 f¨urγ <3,

N^γ+15 f¨urγ >3. (3.47) Nun k¨onnen wir mit (3.32), (3.34), (3.36) und (3.47) das Verhalten des Korrelationskoef-fizienten r_max f¨ur große Netzwerke angeben:

r_max∼







−N^{−γ−2γ−1} f¨urγ <−¹₂ +q

17 4 , N^−γ21−1 f¨ur−¹₂ +q

17

4 < γ <3. (3.48) Nach (3.48) verschwindet r_max im Grenzfall großer Netzwerke. Man beachte außerdem, dass der Wert von r_max negativ ist f¨urγ <−¹₂ +

q17

4 ≃2.56. Gem¨aß der Definition von Assortativit¨at ¨uber das Vorzeichen desPearson-Koeffizienten ist es in diesem Bereich von γalsounm¨oglich, ¨uberhaupt ein assortatives Netzwerk herzustellen. F¨ur diese Werte vonγ ist der dissortative Anteil inK_nn(k) so dominant, dass er im Korrelationskoeffizientenr_max den assortativen Teil ¨uberwiegt, vergleiche auch mit Abb. 3.8. Obwohl die Absch¨atzungen, die zu (3.48) gef¨uhrt haben, ¨uberaus grob sind, l¨asst sich eine recht gute ¨Ubereinstimmung zu den Werten aus Simulationen feststellen. Abbildung 3.9 zeigt r_max als Funktion der Netzwerkgr¨oße N f¨ur verschiedene Werte von γ. F¨ur γ = 2.1 und γ = 2.3 liegt rmax

tats¨achlich eindeutig im negativen Bereich,γ = 2.5 ist leicht positiv undγ = 2.7 γ = 2.9 eindeutig positiv. Die gestrichelten Linien sind Fits nach (3.48), f¨ur gen¨ugend große N stimmen sie gut mit den gemessenen Daten ¨uberein.

-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.

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