Biased random walk on a graph

There have been written many different representations of the biased random walks on graphs based on the particular purpose of the analysis. A common representation of the mechanism for undirected graphs is as follows:^[2]

On an undirected graph, a walker takes a step from the current node, ${\displaystyle j,}$ to node ${\displaystyle i.}$ Assuming that each node has an attribute ${\displaystyle \alpha _{i},}$ the probability of jumping from node ${\displaystyle j}$ to ${\displaystyle i}$ is given by:

${\displaystyle T_{ij}^{\alpha }={\frac {\alpha _{i}A_{ij}}{\sum _{k}\alpha _{k}A_{kj}}},}$

where ${\displaystyle A_{ij}}$ represents the topological weight of the edge going from ${\displaystyle j}$ to ${\displaystyle i.}$

In fact, the steps of the walker are biased by the factor of ${\displaystyle \alpha }$ which may differ from one node to another.^[3]

Depending on the network, the attribute ${\displaystyle \alpha }$ can be interpreted differently. It might be implied as the attraction of a person in a social network, it might be betweenness centrality or even it might be explained as an intrinsic characteristic of a node. In case of a fair random walk on graph ${\displaystyle \alpha }$ is one for all the nodes.

In case of shortest paths random walks^[4] ${\displaystyle \alpha _{i}}$ is the total number of the shortest paths between all pairs of nodes that pass through the node ${\displaystyle i}$ . In fact the walker prefers the nodes with higher betweenness centrality which is defined as below:

${\displaystyle C(i)={\tfrac {{\text{Total number of shortest paths through }}i}{\text{Total number of shortest paths}}}}$

Based on the above equation, the recurrence time to a node in the biased walk is given by:^[5]

${\displaystyle r_{i}={\frac {1}{C(i)}}}$

There are a variety of applications using biased random walks on graphs. Such applications include control of diffusion,^[6] advertisement of products on social networks,^[7] explaining dispersal and population redistribution of animals and micro-organisms,^[8] community detections,^[9] wireless networks,^[10] and search engines.^[11]

• Betweenness centrality
• Community structure
• Kullback–Leibler divergence
• Markov chain
• Maximal entropy random walk
• Random walk closeness centrality
• Social network analysis
• Travelling salesman problem

• Gábor Simonyi, "Graph Entropy: A Survey". In Combinatorial Optimization (ed. W. Cook, L. Lovász, and P. Seymour). Providence, RI: Amer. Math. Soc., pp. 399–441, 1995.
• Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan, "Evaluating the Quality of a Network Topology through Random Walks" in Gadi Taubenfeld (ed.) Distributed Computing