Physik der sozio-ökonomischen Systeme mit dem Computer

(Physics of Socio-Economic Systems with the Computer)

Vorlesung gehalten an der J.W.Goethe-Universität in Frankfurt am Main

(Sommersemester 2024)

von Dr.phil.nat. Dr.rer.pol. Matthias Hanauske

Frankfurt am Main 21.06.2024

Aufgabe 14

Erzeugen Sie ein exponentielles Netzwerk. Zur Zeit t=0 besteht das Netzwerk aus lediglich zwei Knoten (Knoten 0 und Knoten 1), welche durch eine ungerichtete Kante miteinander verbunden sind. Diesem Netzwerk fügt man nun bei jeder Iteration einen weiteren Knoten hinzu und verbindet diesen in zufälliger Weise mit einem der Knoten des bestehenden Netzwerkes. Im Laufe der Zeit entwickelt sich ein exponentielles Netzwerk, wobei dieses Netzwerk nach $N_{it}$ Iterationen aus $N = N_{it} + 2$ Knoten und $m = N_{it} + 1$ Kanten besteht. Aufgabe 14.1.

Aufgabe 14.1.

a)

Stellen Sie das exponentielle Netzwerk mittels NetworkX für $N = 100$ (mit Kennzeichnung der Knotennummern) und $N = 1000$ (ohne Kennzeichnung der Knotennummern) im 'shell_layout', 'fruchterman_reingold_layout' und 'kamada_kawai_layout' dar.

b)

Erstellen Sie, für die beiden in Aufgabe 14.1. erzeugten Netzwerke, ein Diagramm (Scatter-Plot: plt.scatter(...)), welches den Knotengrad $k$ in Abhängigkeit von der Knotennummer darstellt. Welche Eigenschaft von exponentielle Netzwerken kann man mittels dieser Abbildung deutlich erkennen?

Aufgabe 14.2.

Erstellen Sie ein exponentielles Netzwerk mit $N = 300000$ Knoten. Zeigen Sie, dass die Verteilungsfunktion der Knotengrade für exponentielle Netzwerke dem folgenden analytischen Zusammenhang folgt: $P(k)=2^{-k} \quad.$ Stellen Sie dazu $\hbox{log}_2 \!\left( P(k) \right)$ in Abhängigkeit vom Knotengrad $k$ in einem Scatter-Plot dar und überprüfen Sie den analytischen Zusammenhang mittels einer linearen Regression (z.B. mittels der Funktion polyfit(...) des 'NumPy' Moduls).

Musterlösung Aufgabe 14

Musterlösung Aufgabe 14.1.a) (N=100)

import networkx as nx
from random import randint
import numpy as np

G = nx.Graph()
# Zwei Knoten am Anfang
G.add_nodes_from([0,1])
G.add_edge(0,1) # Eine Kante am Anfang

N_it = 98
for it in range(N_it):
    #Hinzufuegen eines weiteren Knotens zum existierenden Netzwerk
    G.add_node(it+2)
    #Erzeugung einer zufaelligen Kante vom neuen Knoten zum existierenden Netzwerk
    G.add_edge(it+2 , randint(0, it + 1))
print("Anzahl der Knoten: " + str(len(G.nodes)))
print("Anzahl der Kanten: " + str(len(G.edges)))

Anzahl der Knoten: 100
Anzahl der Kanten: 99

import matplotlib.pyplot as plt 
import matplotlib

params = {
    'figure.figsize'    : [12,8],
    'axes.titlesize' : 14,
    'axes.labelsize' : 16,  
    'xtick.labelsize' : 14 ,
    'ytick.labelsize' : 14 
}
matplotlib.rcParams.update(params) 

pos = nx.shell_layout(G)

#Erzeugung des Netzwerk-Bildes  
node_size = 150
node_alpha = 0.3
node_color = "red"
edge_tickness = 0.4
edge_alpha = 0.7
edge_color = "blue"
node_text_size = 9
text_font = "sans-serif"
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color)
nx.draw_networkx_labels(G,pos,font_size=node_text_size,font_family=text_font);

pos = nx.fruchterman_reingold_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color)
nx.draw_networkx_labels(G,pos,font_size=node_text_size,font_family=text_font);

pos = nx.kamada_kawai_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color)
nx.draw_networkx_labels(G,pos,font_size=node_text_size,font_family=text_font);

Musterlösung Aufgabe 14.1.b) (N=100)

degree_sequence = np.array(G.degree)[:,1]
plt.ylabel('Knotengrad k')
plt.xlabel('Knotennummer')
plt.scatter(range(len(G.nodes)),degree_sequence,color="blue");

Die obere Abbildung zeigt, dass in exponentiellen Netzwerken die am Anfang erzeugten Knoten (kleine Knotennummer) im Mittel einen höheren Knotengrad besitzen.

Musterlösung Aufgabe 14.1.a) (N=1000)

G = nx.Graph()
# Zwei Knoten am Anfang
G.add_nodes_from([0,1])
G.add_edge(0,1) # Eine Kante am Anfang

N_it = 1000 - 2
for it in range(N_it):
    #Hinzufuegen eines weiteren Knotens zum existierenden Netzwerk
    G.add_node(it+2)
    #Erzeugung einer zufaelligen Kante vom neuen Knoten zum existierenden Netzwerk
    G.add_edge(it+2 , randint(0, it + 1))
print("Anzahl der Knoten: " + str(len(G.nodes)))
print("Anzahl der Kanten: " + str(len(G.edges)))

Anzahl der Knoten: 1000
Anzahl der Kanten: 999

node_size = 12
pos = nx.shell_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color);

pos = nx.fruchterman_reingold_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color);

pos = nx.kamada_kawai_layout(G)
nx.draw_networkx_nodes(G,pos,node_size=node_size,alpha=node_alpha, node_color=node_color)
nx.draw_networkx_edges(G,pos,width=edge_tickness, alpha=edge_alpha,edge_color=edge_color);

Musterlösung Aufgabe 14.1.b) (N=1000)

degree_sequence = np.array(G.degree)[:,1]
plt.ylabel('Knotengrad k')
plt.xlabel('Knotennummer')
plt.scatter(range(len(G.nodes)),degree_sequence,color="blue",s=1);

Die obere Abbildung zeigt, dass in exponentiellen Netzwerken die am Anfang erzeugten Knoten (kleine Knotennummer) im Mittel einen höheren Knotengrad besitzen.

Musterlösung Aufgabe 14.2.

G = nx.Graph()
# Zwei Knoten am Anfang
G.add_nodes_from([0,1])
G.add_edge(0,1) # Eine Kante am Anfang

N_it = 300000 - 2
for it in range(N_it):
    #Hinzufuegen eines weiteren Knotens zum existierenden Netzwerk
    G.add_node(it+2)
    #Erzeugung einer zufaelligen Kante vom neuen Knoten zum existierenden Netzwerk
    G.add_edge(it+2 , randint(0, it + 1))
print("Anzahl der Knoten: " + str(len(G.nodes)))
print("Anzahl der Kanten: " + str(len(G.edges)))

Anzahl der Knoten: 300000
Anzahl der Kanten: 299999

degree_sequence = np.array(G.degree)[:,1]
max_k = np.max(degree_sequence)

plt.xlabel('Knotengrad k')
plt.ylabel(r'$\rm P(k)$')
plt.hist(degree_sequence,bins=range(1,int(max_k+2),1),density="True");
plt.yscale('log')

x_hist = []
y_hist_log = []
for i in range(1,max_k+1):
    y = np.count_nonzero(degree_sequence == i)
    if y != 0:
        x_hist.append(i)
        y_hist_log.append(np.log2(y/len(G.nodes)))
Lin_fit = np.polyfit(x_hist,y_hist_log,1)

plt.ylabel(r'$\rm log_2(P(k))$')
plt.xlabel('Knotengrad k')
plt.plot(x_hist,Lin_fit[0]*np.array(x_hist) + Lin_fit[1],color="red")
plt.scatter(x_hist,y_hist_log,color="blue");

print("Steigung: " + str(Lin_fit[0]))
print("y-Achsenabschnitt: " + str(Lin_fit[1]))

Steigung: -0.982872974594841
y-Achsenabschnitt: -0.10247210499940534

Die Ergebnisse der linearen Regression stimmen gut mit der analytischen Verteilungsfunktion $P(k)=2^{-k}$ überein.

$\hbox{log}_2 \!\left( P(k) \right) = - k \quad \rightarrow $ Steigung = -1 und y-Achsenabschnitt = 0 .