Biased random walk on a graph

Network science
Theory
Graph Complex network Contagion Small-world Scale-free Community structure Percolation Evolution Controllability Graph drawing Social capital Link analysis Optimization Reciprocity Closure Homophily Transitivity Preferential attachment Balance theory Network effect Social influence
Network types
Informational (computing) Telecommunication Transport Social Scientific collaboration Biological Artificial neural Interdependent Semantic Spatial Dependency Flow
Graphs
Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Multi Random Weighted
Metrics Algorithms
Centrality Degree Betweenness Closeness PageRank Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Watts–Strogatz Exponential random (ERGM) Hyperbolic (HGN) Hierarchical Stochastic block model Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various potential new states; unlike in a pure random walk, the probabilities of the potential new states are unequal.

Biased random walks on a graph provide an approach for the structural analysis of undirected graphs in order to extract their symmetries when the network is too complex or when it is not large enough to be analyzed by statistical methods. The concept of biased random walks on a graph has attracted the attention of many researchers and data companies over the past decade especially in the transportation and social networks.^[1]

Model

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, , to node . Assuming that each node has an attribute , the probability of jumping from node to is given by:

, where represents the topological weight of the edge going from to .

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

Depending on the network, the attribute 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. It is obvious that in case of a fair random walk on graph is one for all the nodes.
In case of shortest paths random walks^[4] is the total number of the shortest paths between all pairs of nodes that pass through the node . In fact the walker prefers the nodes with higher betweenness centrality which is defined as below:

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

Applications

Variety of applications by using biased random walks on graphs have been developed; 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] search engines^[11] and so on.

See also

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

References

External links

• 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