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¶
(Wintersemester 2020/21)¶
von Dr.phil.nat. Dr.rer.pol. Matthias Hanauske¶
Frankfurt am Main 02.11.2020¶
Zweiter Vorlesungsteil:¶
Einführung in die Theorie der komplexen Netzwerke¶
Einführung¶
Eine bedeutende Einschränkung der deterministischen, evolutionären Spieltheorie ist deren zugrundeliegende Netzwerkstruktur (Netzwerktopologie). Die jeweiligen Spieler der betrachteten Population suchen in jeder Spielperiode einen neuen Spielpartner, wobei sie hierbei zufällig vorgehen (zufälliges Netzwerk) und vom Prinzip her mit jedem Spieler innerhalb der Population potentiell das zugrundeliegende Spiel spielen können (vollständig verbundenes Netzwerk). In Bimatrix Spielen suchen sich die Spieler der Teilpopulation A einen zufälligen Spielpartner aus Gruppe B (bzw. umgekehrt). Betrachtet man sich jedoch real existierende sozio-ökonomische Netzwerke, so zeigt sich, dass diese Annahme oft nicht erfüllt ist. Personen kennen oft nur eine Teilmenge von Spielern innerhalb der Population (kein vollständig verbundenes Netzwerk) und die Wahl der potentiellen Spielpartner erfolgt oft auch nicht nach zufälligen Mustern.
Die Theorie der komplexen Netzwerke bildet die Grundlage zur Beschreibung einer Vielzahl von unterschiedlichen biologischen und sozio-ökonomischen Systemen. Die formale/mathematische Beschreibung komplexer Netzwerke ist der Graphentheorie zuzuordnen. In dieser auf graphentheoretischen Grundlagen basierenden mathematischen Beschreibung der komplexen Netzwerke werden physikalische bzw. soziale Interaktionen durch Verbindungskanten zwischen den jeweiligen Netzwerkknoten beschrieben. Die theoretische Netzwerkforschung befasst sich mit der Entstehung und Beschreibung dieser Netzwerke. Bei einigen Modellnetzwerken können analytische Ergebnisse gewonnen werden. Die Anwendung der Theorie auf real existierende Netzwerkstrukturen ist ein sehr aktuelles interdisziplinäres Forschungsgebiet. Neben sozialen Netzwerken wie z.B. wissenschaftliche Kollaborationen, Koautorenschaften und Zitationsverflechtungen wissenschaftlicher Artikel, Kommunikationsnetzwerken wie dem Internet und diversen weiteren sozio-ökonomischen Netzwerkstrukturen werden mithilfe des mathematischen Modells der komplexen Netzwerke auch biologische Netzwerken wie z.B. neuronale oder Proteinnetzwerke beschrieben und analysiert.
Im Folgenden werden die Grundlagen der Theorie der komplexen Netzwerke an mehreren einfachen Beispielen beschrieben. Mittels Python und der Programmbibliothek NetworkX ( https://networkx.github.io/ ) kann man in relativ einfacher Weise die unterschiedlichen Arten von komplexen Netzwerken grafisch darstellen und analysieren.
Da die Theorie der komplexen Netzwerke aus dem mathematischen Zweig der Graphentheorie entstanden ist, benutzt sie nicht die mathematischen Vokabeln der Spieltheorie. Man spricht z.B. nicht von Spielern, sondern von Knoten (bzw. Vertices). Die Verbindungen zwischen den Knoten werden als Kanten (bzw. Links) bezeichnet. Während die Spieler eines (klassischen) evolutionären Spiels mit allen anderen Spielern der Population in Kontakt treten können, ist dies bei einem Spiel auf einem komplexen Netzwerk im Allgemeinen nicht möglich.
Komplexe Netzwerke lassen sich wie folgt untergliedern:
- Handelt es sich nur um eine Knotenart (Spielergruppe), oder besteht das Netzwerk aus mehreren Knotenarten (z.B. Bi-Matrix Spiele).
- Sind die Kanten (Verbindungslinien zwischen den Knoten) gerichtet oder ungerichtet.
- Besitzen die Kanten zahlenmäßige Gewichtungen oder geben sie einfach an, ob ein Knoten mit einem anderen verbunden oder nicht verbunden ist.
- Gibt es zeitliche Veränderungen des Netzwerks; ist die Anzahl der Knoten konstant oder wächst bzw. schrumpft sie im Laufe der Zeit.
Man unterscheidet somit gerichtete/ungerichtete und gewichtete/ungewichtete Netzwerke, multipartite Netzwerke (Netzwerke mit verschiedenen Knotenarten, z.B. bei Bi-Matrix Spielen). Zusätzlich werden grob vier unterschiedliche Netzwerk-Topologien klassifiziert: die zufälligen, die kleine Welt, die exponentiellen und die skalenfreien Netzwerke.
Unser erstes Beispiel betrachtet ein ungerichtetes und ungewichtetes zufälliges Netzwerk bestehend aus nur einer Knotenart. Es werden 25 Knoten ($N=25$) in zufälliger Weise miteinander verbunden, wobei die Anzahl der Links (edges) 50 sein soll ($L=50$) und Mehrfachverbindungen nicht erlaubt sind.
import networkx as nx
from random import randint
G=nx.Graph()
#G=nx.DiGraph()#Gerichteter Graph
N = 25
L = 50
G.add_nodes_from(range(0,N,1))
j=0
while j < L:
KnA = randint(0, N-1)
KnB = randint(0, N-1)
if KnA != KnB and list(G.edges()).count((KnA,KnB))==0 and list(G.edges()).count((KnB,KnA))==0:
G.add_edge(KnA,KnB)
j=j+1
G.nodes()
G.edges()
Der Knotengrad $k_i$
Der Knotengrad des Knotens $i$ ($i \in [0,29]$) ist gleich der Anzahl der Kanten, die der Knoten $i$ besitzt. Bei gerichteten Netzwerken unterscheidet man zwischen dem eingehenden $k^{\rm in}_i$ und ausgehenden Knotengrad $k^{\rm out}_i$. Bei gewichteten Netzwerken summiert man über die Zahlenfaktoren der gewichteten Kanten.
#G.in_degree()
#G.out_degree()
G.degree()
Der Knotengrad des Knotens $i=4$ beträgt z.B. $k_4=5$, da er mit 5 anderen Knoten (Knoten 2, 5, 9, 12 und 18) verbunden ist; man sagt er hat drei Nachbarn.
G.degree()[4]
list(G.neighbors(4))
Der durchschnittliche Knotengrad $ {<} k {>} $
Der durchschnittliche Knotengrad eines ungerichteten Netzwerks ${<} k {>}$ ist gegeben durch ${<} k {>}=\frac{1}{N} \sum_{i=1}^N k_i=\frac{2 L}{N}$, wobei $L=50$ die gesamte Anzahl der Links (Kanten) des Netzwerks ist. In unserem Beispiel erhalten wir ${<} k {>}=\frac{2 \cdot 50}{20} \approx 4$
sumki=0
for i in G.nodes():
sumki=sumki+G.degree()[i]
avki=sumki/N
avki
Die Nachbarschaftsmatrix (Adjazenzmatrix) $A_{ij}$
Die Nachbarschaftsmatrix des Netzwerkes beschreibt, welche Knoten des Graphen durch eine Kante verbunden sind. Zeigt eine Kante von Knoten j auf den Knoten i, dann ist der zugehörige Matrixwert $A_{ij}=1$, wohingegen ein Eintrag $A_{ij}=0$ bedeutet, dass keine Kante von j nach i zeigt. Bei ungerichteten Netzwerken ist die Nachbarschaftsmatrix symmetrisch. Der Knotengrad $k_i$ des Knotens i (bzw. $k^{\rm in}_i$ und $k^{\rm out}_i$ bei gerichteten Graphen) lässt sich mittels der Nachbarschaftsmatrix wie folgt bestimmen: $k_i=\sum_{j=1}^N A_{ij}$ ($k^{\rm in}_i=\sum_{j=1}^N A_{ij}$ und $k^{\rm out}_i=\sum_{j=1}^N A_{ji}$ bei gerichteten Graphen), wobei die gesamte Anzahl der Kanten sich wie folgt bestimmen lässt: $L=\sum_{i,j=1}^N A_{ij}/2$ und die Größe $N$ die Anzahl der Knoten des Netzwerkes bezeichnet. In gewichteten Netzwerken sind die Einträge der Nachbarschaftsmatrix nicht mehr auf Null und Eins beschränkt $A_{ij}=w_{ij}$.
import sympy as sym
sym.init_printing()
AdjMat=nx.adjacency_matrix(G)
A=sym.Matrix(AdjMat.todense())
A
Den Knotengrad des Knotens $i=4$ ($k_4=\sum_{l=1}^N A_{4l}$) kann man wie folgt mittels der Nachbarschaftsmatrix berechnen:
l = sym.symbols('l')
sym.Sum(A[4, l], (l, 0, N-1)).doit()
Die gesamte Anzahl der Kanten $L$ kann man wie folgt mittels der Nachbarschaftsmatrix berechnen: $L=\sum_{l,m=1}^N A_{lm}/2$
m = sym.symbols('m')
sym.Sum(sym.Sum(A[m, l], (l, 0, N-1)), (m, 0, N-1)).doit()/2
Die kürzeste Verbindungsstrecke zwischen zwei Knoten $ d_{ij} $
Die Anzahl der Kanten, die in einem Verbindungsweg von Knoten $i$ zum Knoten $j$ durchlaufen wird, hängt vom gewählten Pfad ab. Die kürzeste Verbindungsstrecke $ d_{ij} $ kann hierbei im Allgemeinen auf unterschiedlichen Wegen realisiert sein, wobei der Pfad keine Schleifen enthalten darf und sich nicht kreuzen darf. Der kürzeste Verbindungsweg von Knoten 0 zu Knoten 10 ist in unserem Beispiel der folgende Weg:
nx.shortest_path(G,0,10)
, so dass sich der folgende Wert für $ d_{01} $ berechnet:
len(nx.shortest_path(G,0,10))-1
Durchschnittliche kürzeste Verbindungsstrecke $l$ zwischen zwei Knoten
Mittelt man die kürzeste Verbindungsstrecke zwischen zwei Knoten $ d_{ij} $ über alle Knoten des Netzwerkes, erhält man die durchschnittliche kürzeste Verbindungsstrecke $l$ zwischen zwei Knoten.
print(nx.average_shortest_path_length(G))
Durchmesser des Netzwerks $d_{\rm max}$
Der Durchmesser des Netzwerks gibt die maximale kürzeste Kantenlänge zwischen zwei beliebigen Knoten des Netzwerkes an: $d_{\rm max}=\frac{{\rm log}(\frac{N}{{<} k {>}})}{{\rm log}(\frac{{<} k^2 {>} - {<} k {>}}{{<} k {>}})}+1\quad$, wobei $N$ die Anzahl der Knoten des Netzwerkes darstellt. Falls es einen oder mehrere isolierte Knoten im Netzwerk gibt, ist der Durchmesser des Netzwerks nicht berechenbar, bzw. $d_{\rm max}=\infty$.
nx.diameter(G)
dmax=0
dmaxi=0
dmaxj=0
for i in G.nodes():
for j in G.nodes():
shortpath=len(nx.shortest_path(G,i,j))-1
if shortpath>dmax:
dmax=shortpath
dmaxi=i
dmaxj=j
dmax
nx.shortest_path(G,dmaxi,dmaxj)
Der Clusterkoeffizient $C_i$
Der lokale Clusterkoeffizient gibt die Wahrscheinlichkeit an, dass zwei nächste Nachbarn eines Knotens ebenfalls nächste Nachbarn untereinander sind. Für einen speziellen Knoten $i$ berechnet er sich mittels: $C_i=\frac{2L_i}{k_i(k_i-1)}$, wobei $L_i$ die Anzahl der Kanten darstellt, die die nächsten Nachbarn des Knoten i miteinander verbinden. $C_i$ ist somit der Quotienten aus der Anzahl der Kanten, die zwischen seinen $k_i$ nächsten Nachbarn tatsächlich verlaufen ($L_i$), und der Anzahl an Kanten, die zwischen diesen Nachbarn maximal verlaufen könnten $\frac{1}{2}k_i(k_i-1)$.
Liste der Nachbarn eines Knotens (z.B. Knoten 7):
list(G.neighbors(7))
Lokaler Clusterkoeffizient des Knotens 7 ($C_7$):
nx.clustering(G)[7]
Der globale Clusterkoeffizient $C$ des Netzwerks
Der globale Wert $C$ des Clusterkoeffizienten ist der Mittelwert aller $C_i$'s ($C = \frac{1}{N} \sum_{i=1}^N C_i \,$) und stellt demnach eine Art von der Enge der Nachbarschaftsbeziehungen des Netzwerks dar.
nx.average_clustering(G)
C=0
for i in range(0,N,1):
C=C+nx.clustering(G)[i]
C=C/N
C
Die Verteilungsfunktion der Knotengrade $P(k)=N(k)/N$
Die Verteilungsfunktion der Knotengrade $P(k)$ (bzw. $N(k)$) ist eine wichtige, das Netzwerk charakterisierende Größe. Sie gibt an, wie groß der Anteil an Netzwerkknoten mit Knotengrad k ist. Bei realen (endlichen) Netzwerken ist diese Funktion keine kontinuierliche, sondern eine diskrete Funktion $P(k)\approx P_k$. Bezeichnen wir mit $N_k$ die Anzahl der Knoten mit Knotengrad $k$, so gilt $P_k=\frac{N_k}{N}$. Es gilt $\sum_{k=0}^\infty P_k=1$ und der durchschnittliche Knotengrad berechnet sich wie folgt $ {<} k {>} = \sum_{k=0}^\infty k P_k$ .
degree_sequence = []
for i in G.nodes():
degree_sequence.append(G.degree(i))
maxk=max(degree_sequence)
import matplotlib.pyplot as plt
import matplotlib
params = {
'figure.figsize' : [8,5],
# 'text.usetex' : True,
'axes.titlesize' : 14,
'axes.labelsize' : 16,
'xtick.labelsize' : 14 ,
'ytick.labelsize' : 14
}
matplotlib.rcParams.update(params)
plt.xlabel(r"$\rm k$")
plt.ylabel(r'$\rm N(k)$')
plt.hist(degree_sequence,bins=range(0,int(maxk+2),1), align="left" ,histtype='bar', color="blue", alpha=0.4, edgecolor="black");
Im Folgenden werden wir das erstellte Beispielnetzwerk visualisieren. Zunächst müssen wir dafür ein Layout wählen, da man die Position der Knoten im Raum auf unterschiedlichste Art und Weise anordnen kann. Man kann die Knoten eines Graphen sowohl im zweidimensionalen, als auch im dreidimensionalen Raum positionieren. Der im Folgenden verwendete Fruchterman-Reingold Layout ist eine Darstellungsmöglichkeit bei dem alle Kanten mehr oder weniger gleich lang sind und es so wenige sich kreuzende Kanten wie möglich gibt. Zunächst betrachten wir den zweidimensionalen Fall:
pos=nx.fruchterman_reingold_layout(G)
#Weitere Layouts zur Visualisierung
#kamada_kawai_layout
#bipartite_layout
#circular_layout
#kamada_kawai_layout , Position nodes using Kamada-Kawai path-length cost-function: Energy-based approach: Kamada and Kawai use a spring approach with the key concept that Euclidean distance in the layout should approximate the graph-theoretic distance, i.e.the shortest path length between two nodes.
#random_layout
#rescale_layout
#shell_layout , Knotenkreis mit edges
#spring_layout , Position nodes using Fruchterman-Reingold force-directed algorithm of the Force-directed graph drawing: position the nodes in two-dimensional space is set so that all the edges are of more or less equal length and there are as few crossing edges as possible.
#spectral_layout , nur Knoten
#planar_layout ,
#fruchterman_reingold_layout
Wir stellen uns das Netzwerk zunächst mittels der in NetworkX definierten Visualisierungsfunktion "draw_networkx" und matplotlib dar.
params = {
'figure.figsize' : [11,7],
# 'text.usetex' : True,
'axes.titlesize' : 14,
'axes.labelsize' : 16,
'xtick.labelsize' : 14 ,
'ytick.labelsize' : 14
}
matplotlib.rcParams.update(params)
#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);
Die Visualisierung kann man auch mittels der "Plotly Python Open Source Graphing Library" erstellen. In dieser Bibliothek ist es möglich interaktive Abbildungen in Python darzustellen ( siehe https://plotly.com/python/ ). Wir ordnen jedem Knoten ein Textfeld zu, sodass der Benutzer (wenn er mit der Maus auf den Knoten zeigt) die Knotennummer und den zugehörigen Knotengrad sieht. Zusätzlich veranschaulichen wir die unterschiedlichen Knotengrade der Knoten mittels verschiedener Farben.
import plotly.graph_objects as go
node_x=[pos[k][0] for k in range(N)]
node_y=[pos[k][1] for k in range(N)]
edge_x = []
edge_y = []
for edge in G.edges():
edge_x+=[pos[edge[0]][0],pos[edge[1]][0], None]
edge_y+=[pos[edge[0]][1],pos[edge[1]][1], None]
node_trace = go.Scatter(
x=node_x, y=node_y,
mode='markers',
hoverinfo='text',
marker=dict(
showscale=True,
# colorscale options
#'Greys' | 'YlGnBu' | 'Greens' | 'YlOrRd' | 'Bluered' | 'RdBu' |
#'Reds' | 'Blues' | 'Picnic' | 'Rainbow' | 'Portland' | 'Jet' |
#'Hot' | 'Blackbody' | 'Earth' | 'Electric' | 'Viridis' |
colorscale='YlGnBu',
reversescale=True,
color=[],
size=10,
colorbar=dict(
thickness=15,
title='Knotengrad',
xanchor='left',
titleside='right'
),
line_width=1))
edge_trace = go.Scatter(
x=edge_x, y=edge_y,
line=dict(width=0.5, color='grey'),
hoverinfo='none',
mode='lines')
node_text = []
for node in G.nodes():
node_text.append('Knoten '+str(node)+', Knotengrad = '+str(degree_sequence[node]))
node_trace.marker.color = degree_sequence
node_trace.text = node_text
fig = go.Figure(data=[edge_trace, node_trace],
layout=go.Layout(
showlegend=False,
hovermode='closest',
margin=dict(b=20,l=5,r=5,t=40),
xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
yaxis=dict(showgrid=False, zeroline=False, showticklabels=False))
)
fig.show()
Eine dreidimensionale Darstellung des Beispielnetzwerkes erfolgt in ähnlicher Weise:
pos3d=nx.fruchterman_reingold_layout(G,dim=3)
node_x=[pos3d[k][0] for k in range(N)]
node_y=[pos3d[k][1] for k in range(N)]
node_z=[pos3d[k][2] for k in range(N)]
edge_x = []
edge_y = []
edge_z = []
for edge in G.edges():
edge_x+=[pos3d[edge[0]][0],pos3d[edge[1]][0], None]
edge_y+=[pos3d[edge[0]][1],pos3d[edge[1]][1], None]
edge_z+=[pos3d[edge[0]][2],pos3d[edge[1]][2], None]
labels=[]
group=[]
for node in G.nodes():
labels.append('Knoten '+str(node)+', Knotengrad = '+str(degree_sequence[node]))
group.append(degree_sequence[node])
edge_trace=go.Scatter3d(x=edge_x,
y=edge_y,
z=edge_z,
mode='lines',
line=dict(color='black', width=1.1),
hoverinfo='none'
)
node_trace=go.Scatter3d(x=node_x,
y=node_y,
z=node_z,
mode='markers',
name='actors',
marker=dict(symbol='circle',
size=6,
color=group,
colorscale='YlGnBu',
line=dict(color='black', width=0.8)
),
text=labels,
opacity=0.9,
hoverinfo='text'
)
Zusätzlich veranschaulichen wir den Durchmesser des Netzwerks (maximale kürzeste Kantenlänge zwischen zwei beliebigen Knoten des Netzwerkes) mittels einer roten Verbindungslinie.
diam_x= []
diam_y= []
diam_z= []
diameter=nx.diameter(G)
tracediam=nx.shortest_path(G,dmaxi,dmaxj)
tracediam[0]
i=0
while i < diameter:
diam_x+=[pos3d[tracediam[i]][0],pos3d[tracediam[i+1]][0], None]
diam_y+=[pos3d[tracediam[i]][1],pos3d[tracediam[i+1]][1], None]
diam_z+=[pos3d[tracediam[i]][2],pos3d[tracediam[i+1]][2], None]
i+=1
diam_trace=go.Scatter3d(x=diam_x,
y=diam_y,
z=diam_z,
mode='lines',
line=dict(color='red', width=1.5),
hoverinfo='none'
)
axis=dict(showbackground=False,
backgroundcolor="white",
showline=False,
zeroline=False,
showgrid=True,
gridcolor="rgb(244, 233, 245)",
showticklabels=False,
showaxeslabels=False,
)
layout = go.Layout(
width=700,
height=700,
showlegend=False,
scene=dict(
xaxis=dict(axis),
yaxis=dict(axis),
zaxis=dict(axis),
),
margin=dict(b=20,l=10,r=10,t=10),
hovermode='closest',
)
data=[node_trace,edge_trace,diam_trace]
fig=go.Figure(data=data, layout=layout)
fig.show()
#Auflistung einiger das Netzwerk bestimmender Groessen
#print("######### number of nodes: "+str(NKn))
#print("average_clustering: "+str(nx.average_clustering(G)))
#print("clustering: "+str(list(nx.clustering(G).values())))
#print("triangles: "+str(list(nx.triangles(G).values())))
#print("degree: "+str(list(nx.degree(G))))
#print("shortest_path from 0 to NKn-1: "+str(nx.shortest_path(G,0,NKn-1)))
#print("radius: "+str(nx.radius(G)))
#print("diameter: "+str(nx.diameter(G)))
#print("eccentricity: "+str(list(nx.eccentricity(G).values())))
#print("center: "+str(nx.center(G)))
#print("periphery: "+str(nx.periphery(G)))
#print("density: "+str(nx.density(G)))
#print("neighbors node 0: "+str(list(G.neighbors(0))))