Do you want to end up with a permutation of the adjacency matrix of the graph you started with? If you are on python you could use a Integer Array Indexing (https://docs.scipy.org/doc/numpy-1.10.0/reference/arrays.indexing.html#integer-array-indexing) and implement a swap very easily. Or should this be a subgraph of the existing graph, then you could perform a random walk (http://graphstream-project.org/doc/Algorithms/Random-walks-on-graphs/)
It can be the case if the graph belong to the family of graphs very explicit. I recommend you to go trough the paper of SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON on EXPANDER GRAPHS AND THEIR APPLICATIONS .