Utilisation de NetworkX pour étudier l'opérateur de décalage et d'autres créations mathématiques

Question

Une branche de la théorie de l'opérateur étudie l'opérateur de décalage S. Fondamentalement, étant donné un graphe avec des poids affectés à chaque sommet du graphique, l'opérateur de décalage produit un nouveau graphique en prenant la même graphique (A) et en remplaçant le poids de chaque sommet par la somme des poids des voisins du sommet. Par exemple, dans le graphique 3 (A) est remplacé par 5 + 5 + 2 + 0

A

B

Est-ce que quelqu'un sait si NetworkX peut m'aider à automatiser un tel processus pour un graphique arbitraire, G? De plus, quelles sont les limites de taille (sommets, arêtes, etc.) des graphes que je peux construire?

Answer 1

Vous devez d'abord créer un graphique et ajouter les poids des nœuds. Je nomme les nœuds avec des lettres de a à h. Pour les graphes plus grands, vous aurez besoin d'une manière différente de nommer les nœuds (donc chaque nœud a un nom unique).

Dans le code ci-dessous, je dessine également les noms des nœuds. Notez que je définis manuellement les positions des nœuds afin que vous ayez le même exemple que vous. Pour des graphes plus grands, consultez graph layouts.

import networkx as nx 
from matplotlib import pyplot as plt 

G = nx.Graph() 

nodes = [ 
    ['a', {'weight' : 5}], 
    ['b', {'weight' : 4}], 
    ['c', {'weight' : 2}], 
    ['d', {'weight' : 3}], 
    ['e', {'weight' : 5}], 
    ['f', {'weight' : 0}], 
    ['g', {'weight' : 0}], 
    ['h', {'weight' : 1}] 
] 
for node in nodes: 
    G.add_node(node[0], node[1]) # add node and node weight from list 

G.add_edges_from([ 
    ('a', 'd'), 
    ('b', 'e'), 
    ('c', 'd'), 
    ('d', 'e'), 
    ('d', 'g'), 
    ('e', 'h'), 
    ('e', 'f') 
]) 

pos = {'a' : (1, 2), 'b' : (2, 2), 'c' : (0, 1), 'd' : (1, 1), 'e' : (2, 1), 'f' : (3, 1), 'g' : (1, 0), 'h' : (2, 0)} # manual fixed positions 
plt.figure() 
nx.draw(G, pos=pos, with_labels=True, node_size=700, node_color='w') # draw node names 
plt.show() 

Sortie:

Voici le code qui dessine les poids des noeuds:

plt.figure() 
nx.draw(G, pos=pos, labels=nx.get_node_attributes(G, 'weight'), node_size=700, node_color='w') # draw node weights 
plt.show() 

Et enfin, le code pour le calcul de votre opérateur de décalage S Vous pouvez obtenir les voisins d'un nœud node avec G[node]. L'attribut weight pour certains nœuds neighbor est accessible avec G.node[neighbor]['weight']. En utilisant cette compréhension de liste et je résume la liste des poids pour tous les nœuds voisins du nœud courant. Notez que les nouveaux poids sont définis avec nx.set_node_attributes(G, 'weight', new_weights).

new_weights = {} 
for node in G.nodes(): 
    new_weights[node] = sum([G.node[neighbor]['weight'] for neighbor in G[node]]) # sum weights of all neighbors of current node 

nx.set_node_attributes(G, 'weight', new_weights) # set new weights 
plt.figure() 
nx.draw(G, pos=pos, labels=nx.get_node_attributes(G, 'weight'), node_size=700, node_color='w') # draw new node weights 
plt.show() 

graphique final: