Using NetworkX to Study the Shift Operator and other Mathematical Creations

Question

A branch of operator theory studies the shift operator S. Basically, given a graph with weights assigned to each vertex of the graph, the shift operator produces a new graph by taking the same graph (A) and replacing the weight of each vertex with the sum of the weights of the vertex's neighbors. For example, 3 in graph (A) is replaced by 5 + 5 + 2 + 0.

A

B

Does anyone know if networkx can help me automate such a process for an arbitrary graph, G? Also, what are the limits in size (vertexes, edges, etc) of graphs that I may construct?

I am sure networkx can be used to do this. It should simply require looping through the network and assigning a new weight to each node (being careful to not overwrite the old weight until you've completed this). What have you tried so far? — Joel

edo edo · Accepted Answer · 2017-06-23T13:28:26

First you need to create a graph and add the node weights. I name the nodes with letters from a to h. For larger graphs you'll need a different way of naming nodes (so each node has a unique name).

In the code bellow I also draw the node names. Note that I manually set the node positions so I have the same example as you. For larger graphs check out 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()

Output:

Here is the code which draws the node weights:

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()

And finally the code for calculating your shift operator S. You can get the neighbors of some node node with G[node]. The weight attribute for some node neighbor can be accessed with G.node[neighbor]['weight'].

Using that and list comprehension I sum the list of weights for all neighbor nodes of the current node. Note that the new weights are set with 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()

Final graph:

Using NetworkX to Study the Shift Operator and other Mathematical Creations

1 Answers