I have an undirected graph $G$ and when performing a random walk on the graph $G$, I visit a node $u$ with probability proportional to $d_{u}$ where $d_u$ is degree of node $u$.
I know there exists ways like Metropolis Hastings to redefine edge probabilities such that the probability of visiting a node is 1/|V|.
Given that I have another quality value $q_u$ of every node, is there a way to redefine the edge probabilities so I sample nodes with probability proportional to $q_{u}$.
I know I can do the sampling of nodes uniformly first and then do rejection sampling but I wanted to know if there is a way to directly do the sampling from the graph by changing transition probabilities online.
Presumably all $q_u > 0$. Assuming your graph is connected, and you allow the process to sometimes stay at a vertex rather than jump, it is possible. Let $p_{ij}$ be the transition probability for moving from $i$ to $j$ ($0$ unless either $\{i,j\}$ is an edge or $i=j$). Your process will be reversible if for each edge $\{i,j\}$, $q_i p_{ij} = q_j p_{ji}$. This would be satisfied if $p_{ij} = q_j$ for all edges $\{i,j\}$, but that might make the sum of transition probabilities leaving some nodes $> 1$. Therefore if $M = \max_i \sum_{j \in N(i)} q_j$, we take $$\eqalign{p_{ij} &= q_j/M\cr p_{ii} &= 1 - \sum_{j \in N(i)} q_j/M}$$