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:{{cite journal|last1=J. Gómez-Gardeñes |author2=V. Latora|title=Entropy rate of diffusion processes on complex networks|journal=Physical Review E|date=Dec 2008 |doi= 10.1103/PhysRevE.78.065102 |pmid=19256892|volume=78|issue=6|page=065102| arxiv=0712.0278| bibcode=2008PhRvE..78f5102G|s2cid=14100937}}

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

:$T\_\{ij\}^\backslash alpha=\backslash frac\{\backslash alpha\_i\; A\_\{ij\}\}\{\backslash sum\_\{k\}\; \backslash alpha\_k\; A\_\{kj\}\},$

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

In fact, the steps of the walker are biased by the factor of $\backslash alpha$ which may differ from one node to another.{{cite journal |author=R. Lambiotte |author2=R. Sinatra |author3=J.-C. Delvenne |author4=T.S. Evans |author5=M. Barahona |author6=V. Latora|title=Flow graphs: interweaving dynamics and structure| journal = Physical Review E|date=Dec 2010|doi=10.1103/PhysRevE.84.017102|pmid=21867345|volume=84|issue=1|page=017102|arxiv=1012.1211|bibcode=2011PhRvE..84a7102L|s2cid=2286264}}

Depending on the network, the attribute $\backslash 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 $\backslash alpha$ is one for all the nodes.

In case of shortest paths random walks{{cite book|author=Blanchard, P |author2=Volchenkov, D|title=Mathematical Analysis of Urban Spatial Networks| date=2008|doi=10.1007/978-3-540-87829-2| url= https://www.researchgate.net/publication/233971652|publisher=Springer |isbn=978-3-540-87828-5 |via=ResearchGate}} $\backslash alpha\_i$ is the total number of the shortest paths between all pairs of nodes that pass through the node $i$. In fact the walker prefers the nodes with higher betweenness centrality which is defined as below:

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

Based on the above equation, the recurrence time to a node in the biased walk is given by:{{cite book |author1=Volchenkov D |author2=Blanchard P|title=Fair and biased random walks on undirected graphs and related entropies|date=2011|publisher=Birkhäuser|page=380|url=http://pub.uni-bielefeld.de/publication/1997352|isbn=978-0-8176-4903-6}}

:$r\_i=\backslash frac\{1\}\{C(i)\}$

There are a variety of applications using biased random walks on graphs. Such applications include control of diffusion,{{cite book|last1=Chung, Zhao| first1= Fan, Wenbo|chapter=PageRank and Random Walks on Graphs|title=Fete of Combinatorics and Computer Science | date=2010|doi=10.1007/978-3-642-13580-4_3|pages=43–62| series= Bolyai Society Mathematical Studies| volume= 20| isbn= 978-3-642-13579-8| citeseerx= 10.1.1.157.7116| s2cid= 3207094}} advertisement of products on social networks,{{cite book|last1=Adal, K.M.|chapter=Biased random walk based routing for mobile ad hoc networks|pages=1–6|date=June 2010|doi=10.1109/ICIAS.2010.5716181|isbn=978-1-4244-6623-8|title=2010 International Conference on Intelligent and Advanced Systems|s2cid=16113377}} explaining dispersal and population redistribution of animals and micro-organisms,{{cite journal |author=Kakajan Komurov |author2=Michael A. White |author3=Prahlad T. Ram|title=Use of Data-Biased Random Walks on Graphs for the Retrieval of Context-Specific Networks from Genomic Data|journal=PLOS Comput Biol|date=Aug 2010 |pmc=2924243 |pmid=20808879|doi=10.1371/journal.pcbi.1000889|volume=6|issue=8|pages=e1000889|bibcode=2010PLSCB...6E0889K |doi-access=free }} community detections,{{cite journal|last1=J.K. Ochab |author2=Z. Burda|title=Maximal entropy random walk in community detection|journal=The European Physical Journal Special Topics|date=Jan 2013|doi=10.1140/epjst/e2013-01730-6|volume=216|pages=73–81|arxiv=1208.3688|bibcode=2013EPJST.216...73O|s2cid=56409069}} wireless networks,{{cite journal| last1=Beraldi |first1=Roberto| title= Biased Random Walks in Uniform Wireless Networks|journal=IEEE Transactions on Mobile Computing|volume=8|issue=4|pages=500–513|date=Apr 2009|doi=10.1109/TMC.2008.151|s2cid=13521325}} and search engines.{{cite journal |author=Da-Cheng Nie |author2=Zi-Ke Zhang |author3=Qiang Dong |author4=Chongjing Sun |author5=Yan Fu|title=Information Filtering via Biased Random Walk on Coupled Social Network|journal=The Scientific World Journal|volume=2014|page=829137|date=July 2014|doi=10.1155/2014/829137|pmid=25147867|pmc=4132410|doi-access=free}}

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

{{Reflist}}

• Gábor Simonyi, [http://www.renyi.hu/~simonyi/grams.pdf "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, [http://homepages.laas.fr/gtredan/pdf/baDiscEvaluatingQuality.pdf "Evaluating the Quality of a Network Topology through Random Walks"] in Gadi Taubenfeld (ed.) Distributed Computing

Category:Network theory

Category:Social networks

Category:Social systems

Category:Social information processing