how can I shuffle node labels and get a new weight vector using NumPy in Python?-CodePudding

The

The vector that I create is [5, 3, 4, 1, 2, 7] as ordered based on node number in ascending order. Now, if I swap the node labels of nodes 1 and 4, I can obtain the following graph;

In this scenerio, the vector that I should have is [2, 7, 4, 1, 5, 3]. My question is if I have an n by m NumPy array, where n is the number of graphs and m is the number of edges, how can I shuffle the node labels for each row and get the updated array efficiently?

Suppose I have a set of graphs consisting of four nodes as shown below. My intention is to randomly shuffle node labels in each network and then get an updated weights accordingly in a same size array.

np.random.seed(2) arr = np.random.randint(10, size=(5, 6)) arr array([[8, 8, 6, 2, 8, 7], [2, 1, 5, 4, 4, 5], [7, 3, 6, 4, 3, 7], [6, 1, 3, 5, 8, 4], [6, 3, 9, 2, 0, 4]])

CodePudding user response：

You can do it like this:

import numpy as np def get_arr_from_edges(a): n = int(np.sqrt(len(a)*2)) 1 mask = np.tri(n, dtype=bool, k=-1) out = np.full((n, n), np.nan) out[mask.T] = a out = out.T out[mask.T] = a return out def get_edges_from_arr(a): mask = np.tri(a.shape[0], dtype=bool, k=-1) out = a[mask.T] return out def swap_nodes(a, nodes): temp = a[:, nodes[0] - 1, :].copy() a[:, nodes[0] - 1, :] = a[:, nodes[1] - 1, :] a[:, nodes[1] - 1, :] = temp temp = a[:, :, nodes[0] - 1].copy() a[:, :, nodes[0] - 1] = a[:, :, nodes[1] - 1] a[:, :, nodes[1] - 1] = temp return a arr = np.array([ [8, 8, 6, 2, 8, 7], [2, 1, 5, 4, 4, 5], [7, 3, 6, 4, 3, 7], [6, 1, 3, 5, 8, 4], [6, 3, 9, 2, 0, 4], ]) nodes_to_swap = (1, 4) # initialize node-arr node_arrs = np.apply_along_axis(get_arr_from_edges, axis=1, arr=arr) # swap nodes node_arrs = swap_nodes(node_arrs, nodes_to_swap) # return rempapped edges edges = np.array([get_edges_from_arr(node_arr) for node_arr in node_arrs]) print(edges)

Gives the following result:

[[8 7 6 2 8 8] [4 5 5 4 2 1] [3 7 6 4 7 3] [8 4 3 5 6 1] [0 4 9 2 6 3]]

The idea is to build a connection-matrix from the edges, where the edge-number is saved at the indices of the two nodes.

Then you just swap the columns and rows according to the nodes you want to swap (this property is non-transitive, so if you want to swap multiple node-pairs then order matters!).

After that you read out the remapped edges from the upper triangle of the array with the swapped columns and rows (this is basically the inverse of the first step).

I am sure that there are some more optimizations left using numpys vast functionality.

CodePudding user response：

Here we first write a function for shuffling a weight vecotr, which is similar to MangoNrFive's idea:

Calculate the number of points according to the length of the vector

Create an adjacency matrix, fill in the weights in the upper triangular order, and make them symmetrical by transposing and adding

Generate a point number vector and shuffle

Take out the corresponding row of the adjacency matrix according to the point number after the shuffle, and then take out the corresponding column from result, and then get the weight after the shuffle from the upper triangle

def shuffle_1d(weights): n_points = math.isqrt(1 8 * len(weights)) // 2 1 matrix = np.zeros((n_points, n_points), dtype=int) triu_indices = np.triu_indices(n_points, 1) matrix[triu_indices] = weights matrix = matrix.T indices = np.random.permutation(n_points) return matrix[indices][:, indices][triu_indices]

For the weights of multiple graphs, this will be a two-dimensional matrix. A simple way is to apply the above function to each row of the matrix, and then turn the resulting list into an array. This is not a sufficiently efficient method, so I implemented the corresponding two-dimensional method. For a 15 * 6 matrix, its performance is about 5 times faster than the above method:

def shuffle_2d(weights): n_graph, n_weights = weights.shape n_points = math.isqrt(1 8 * n_weights) // 2 1 matrix = np.zeros((n_graph, n_points, n_points), dtype=int) triu_row, triu_col = np.triu_indices(n_points, 1) graph_indices = np.arange(n_graph)[:, None] matrix[graph_indices, triu_row, triu_col] = weights matrix = matrix.transpose(0, -1, 1) rng = np.random.default_rng() indices = np.tile(np.arange(n_points), (n_graph, 1)) rng.permuted(indices, axis=1, out=indices) return matrix[graph_indices, indices][graph_indices, :, indices][graph_indices, triu_row, triu_col]

Some test:

>>> weight array([5, 3, 4, 1, 2, 7]) >>> shuffle_1d(weight) array([1, 7, 3, 2, 5, 4]) >>> weights = np.array([weight] * 3) >>> np.array([shuffle_1d(w) for w in weights]) array([[7, 1, 3, 2, 4, 5], [2, 7, 4, 1, 5, 3], [7, 4, 2, 3, 1, 5]]) >>> shuffle_2d(weights) array([[5, 4, 3, 2, 1, 7], [3, 4, 5, 7, 1, 2], [4, 5, 3, 2, 7, 1]]) >>> weights = np.array([weight] * 16) >>> timeit(lambda: np.array([shuffle_1d(w) for w in weights]), number=1000) 0.5988643999444321 >>> timeit(lambda: shuffle_2d(weights), number=1000) 0.09754280000925064