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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.