import networkx as nx import matplotlib.pyplot as plt from random import randint import numpy as np import matplotlib import matplotlib.gridspec as gridspec from matplotlib.ticker import NullFormatter nullfmt = NullFormatter() # Keine Labels im Netzwerkplot #Von https://de.wikibooks.org/wiki/Algorithmensammlung:_Statistik:_Binomialkoeffizient def binomialkoeffizient(n, k): if k == 0: return 1 if 2*k > n: ergebnis = binomialkoeffizient(n, n-k) else: ergebnis = n - k + 1 for i in range(2, k+1): # i in [2; k] ergebnis *= (n-k+i) # Selbstmultiplikation ergebnis /= i # Achtung: Ergebnis ist eine Kommazahl! return int(ergebnis) #Analytische Verteilungsfunktion eines zufaelligen Netzwerkes def P(n,kmin,kmax,p): ergebnis=[] for k in range(kmin,kmax): ergebnis.append(binomialkoeffizient(n-1,k)*p**k*(1-p)**(n-1-k)) return ergebnis #plot settings params = { 'figure.figsize' : [5, 8.5], 'text.usetex' : True, 'legend.fontsize' : 12 } matplotlib.rcParams.update(params) ###################################################################### #Beginn des eigentlichen Python Programms "Small World Netzwerk" ###################################################################### av_deg=[]#Erzeugung einer Liste zum Speichern der gemittelten Verteilungsfunktion #Erzeugung des regulaeren Netzwerkes zum Anfangszeitpunkt t=0 #Jeder Knoten ist mit seinem naechsten und uebernaechsten Nachbarn verbunden G=nx.Graph() #Anzahl der Knoten NKn = 80 G.add_nodes_from(range(NKn)) for i in range(NKn - 2): G.add_edge(i, i + 1) G.add_edge(i, i + 2) i = i + 1 G.add_edge(NKn - 2, NKn - 1) G.add_edge(NKn - 2, 0) G.add_edge(NKn - 1, 0) G.add_edge(NKn - 1, 1) #Berechnung der durchschnittlichen Warscheinlichkeit das Knoten KnA mit KnB verbunden ist p = (2*G.number_of_edges()/float(NKn*(NKn-1))) #In jedem Iterationsschritt wird nun eine zufaellig ausgewaehlte Kante herausgenommen #und neu, auf zufaellige Weise mit einem Netwerkknoten verbunden npoints = 60 # Berechnung des durchschnittlichen Cluster Koeffizienten und der durchschnittliche kuerzesten Verbindungsstrecke zwischen zwei Knoten properties = np.zeros([npoints,2]) C_0 = nx.average_clustering(G) l_0 = nx.average_shortest_path_length(G) properties[0][0] = 1 properties[0][1] = 1 #Plot-Grid plt.figure(0) gs = gridspec.GridSpec(3, 1, height_ratios=[1,1,2.8], hspace=0.15) ax1 = plt.subplot(gs[0]) ax2 = plt.subplot(gs[1]) ax3 = plt.subplot(gs[2]) for it in range(1,npoints): #Liste der Knotengrade degree_sequence = [] for n in G.nodes(): degree_sequence.append(G.degree(n)) av_deg.extend(degree_sequence) maxk = np.max(degree_sequence) #Darstellung des normierten durchschnittlichen Cluster Koeffizienten und der durchschnittliche kuerzesten Verbindungsstrecke zwischen zwei Knoten ax1.plot(range(0,it),properties[0:it,0], c="black",label=r'$\rm C_t/C_0 $') ax1.plot(range(0,it),properties[0:it,1], c="red",label=r'$\rm l_t/l_0$') #Erzeugung des Bildes der Verteilungsfunktion der Knotengrade P(k) (analytisch,simulativ) ax2.plot(range(0,int(maxk+2),1),np.array(P(NKn,0,int(maxk+2),p)), linewidth=1, linestyle='-', c="black") ax2.hist(degree_sequence,bins=range(0,int(maxk+2),1),density=1, align="left" ,histtype='bar', color="blue", alpha=0.5) #Achsenbeschriftung ax1.set_ylabel(r'$\rm C_t/C_0 \,\, l_t/l_0$') ax2.set_ylabel(r'$\rm P(k)$') ax3.yaxis.set_major_formatter(nullfmt) ax3.xaxis.set_major_formatter(nullfmt) ax1.set_xlim(0,npoints) ax1.set_ylim(0,1) ax1.legend(shadow=False, frameon=False) ax2.set_xlim(1,maxk+1) ax2.set_ylim(0,1) #Erzeugung des Netzwerk-Bildes node_size = 150 node_alpha = 0.3 node_color = "red" edge_thickness = 0.4 edge_alpha = 0.7 edge_color = "blue" node_text_size = 9 text_font = "sans-serif" graph_pos = nx.shell_layout(G) nx.draw_networkx_nodes(G, graph_pos, node_size = node_size, alpha = node_alpha, node_color = node_color) nx.draw_networkx_edges(G, graph_pos, width = edge_thickness, alpha = edge_alpha, edge_color = edge_color) nx.draw_networkx_labels(G, graph_pos, font_size = node_text_size, font_family = text_font) # Plotten der Netzwerkeigenschaften in das Bild textstr = r'$N='+str(NKn)+', C='+str(round(nx.average_clustering(G),2))+', l='+str(round(nx.average_shortest_path_length(G),2))+'$' props = dict(boxstyle='round', facecolor='white', alpha=0.92) plt.text(0, -1.46, textstr, fontsize=12, verticalalignment='bottom', horizontalalignment='center', bbox=props) #Speicherung des Bildes als .png Datei saveFig="./img-" + "{:0>3d}".format(it) + ".png" plt.savefig(saveFig, dpi=200,bbox_inches="tight",pad_inches=0.05,format="png") # Die einzelnen Bilder koennen dann in eine Animation zusammengefuegt werden. # z.B. mit folgende Shell-Befehl: ffmpeg -framerate 3 -i './img-%03d.png' network.mp4 # Loeschung einer alten Kante und Erzeugung einer neuen mit zufaelliger Anordnung NewEdge = 0 while NewEdge == 0: KnA = randint(0, NKn-1) NeigList = list(G.neighbors(KnA)) Neig = randint(0, len(NeigList)-1) KnB = NeigList[Neig] KnC = randint(0, NKn-1) if KnA != KnC and list(G.edges()).count((KnA,KnC)) == 0 and list(G.edges()).count((KnC,KnA)) == 0 and KnB != KnC: G.remove_edge(KnA, KnB) G.add_edge(KnA, KnC) NewEdge = 1 # Berechnung des durchschnittlichen Cluster Koeffizienten und der durchschnittliche kuerzesten Verbindungsstrecke zwischen zwei Knoten (normierte Werte) properties[it][0] = nx.average_clustering(G)/C_0 properties[it][1] = nx.average_shortest_path_length(G)/l_0 #Loeschen des Bildes ax1.clear() ax2.clear() ax3.clear() #Auflistung einiger das Netzwerk bestimmender Groessen # print "######### number of nodes" , NKn # print "average_clustering:" , nx.average_clustering(G) # print "clustering:" , list(nx.clustering(G).values()) # print "triangles:" , list(nx.triangles(G).values()) # print "degree:" , list(nx.degree(G)) # print "shortest_path from 0 to NKn-1:" , nx.shortest_path(G,0,NKn-1) # print "radius:" , nx.radius(G) # print "diameter:" , nx.diameter(G) # print "eccentricity:" , list(nx.eccentricity(G).values()) # print "center:" , nx.center(G) # print "periphery:" , nx.periphery(G) # print "density:" , nx.density(G) # print "neighbors node 0:" , list(G.neighbors(0)) # print "######### ######### #########"