Biased random walk on a graph

Short description: Structural analysis of a network

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
* on-Chip

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
* Fitness model
* Watts–Strogatz
* Exponential random (ERGM)
* Random geometric (RGG)
* Hyperbolic (HGN)
* Hierarchical
* Stochastic block
* Maximum entropy
* Soft configuration
* LFR Benchmark

Dynamics

* Boolean network
* agent based
* Epidemic/SIR

* Lists
* Categories

* Topics
* Software
* Network scientists

* Category:Network theory
* Category:Graph theory

* v
* t
* e

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]

## Contents

* 1 Model
* 2 Applications
* 3 See also
* 4 References
* 5 External links

## 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, [math]\displaystyle{ j, }[/math] to node [math]\displaystyle{ i. }[/math] Assuming that each node has an attribute [math]\displaystyle{ \alpha_i, }[/math] the probability of jumping from node [math]\displaystyle{ j }[/math] to [math]\displaystyle{ i }[/math] is given by:

[math]\displaystyle{ T_{ij}^\alpha=\frac{\alpha_i A_{ij}}{\sum_{k} \alpha_k A_{kj}}, }[/math]

where [math]\displaystyle{ A_{ij} }[/math] represents the topological weight of the edge going from [math]\displaystyle{ j }[/math] to [math]\displaystyle{ i. }[/math]

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

Depending on the network, the attribute [math]\displaystyle{ \alpha }[/math] 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 [math]\displaystyle{ \alpha }[/math] is one for all the nodes.

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

[math]\displaystyle{ C(i)=\tfrac{\text{Total number of shortest paths through } i}{\text{Total number of shortest paths}} }[/math]

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

[math]\displaystyle{ r_i=\frac{1}{C(i)} }[/math]

## Applications

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]

## See also

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

## References

1. ↑ Roberta Sinatra; Jesús Gómez-Gardeñes; Renaud Lambiotte; Vincenzo Nicosia; Vito Latora (March 2011). "Maximal-entropy random walks in complex networks with limited information". Physical Review E 83 (3): 030103. doi:10.1103/PhysRevE.83.030103. PMID 21517435. Bibcode: 2011PhRvE..83c0103S.
2. ↑ J. Gómez-Gardeñes; V. Latora (Dec 2008). "Entropy rate of diffusion processes on complex networks". Physical Review E 78 (6): 065102. doi:10.1103/PhysRevE.78.065102. PMID 19256892. Bibcode: 2008PhRvE..78f5102G.
3. ↑ R. Lambiotte; R. Sinatra; J.-C. Delvenne; T.S. Evans; M. Barahona; V. Latora (Dec 2010). "Flow graphs: interweaving dynamics and structure". Physical Review E 84 (1): 017102. doi:10.1103/PhysRevE.84.017102. PMID 21867345. Bibcode: 2011PhRvE..84a7102L.
4. ↑ Blanchard, P; Volchenkov, D (2008). Mathematical Analysis of Urban Spatial Networks. Springer. doi:10.1007/978-3-540-87829-2. ISBN 978-3-540-87828-5. https://www.researchgate.net/publication/233971652.
5. ↑ Volchenkov D; Blanchard P (2011). Fair and biased random walks on undirected graphs and related entropies. Birkhäuser. p. 380. ISBN 978-0-8176-4903-6. http://pub.uni-bielefeld.de/publication/1997352.
6. ↑ Chung, Zhao, Fan, Wenbo (2010). "PageRank and Random Walks on Graphs". Fete of Combinatorics and Computer Science. Bolyai Society Mathematical Studies. 20. pp. 43–62. doi:10.1007/978-3-642-13580-4_3. ISBN 978-3-642-13579-8.
7. ↑ Adal, K.M. (June 2010). "Biased random walk based routing for mobile ad hoc networks". 2010 International Conference on Intelligent and Advanced Systems. pp. 1–6. doi:10.1109/ICIAS.2010.5716181. ISBN 978-1-4244-6623-8.
8. ↑ Kakajan Komurov; Michael A. White; Prahlad T. Ram (Aug 2010). "Use of Data-Biased Random Walks on Graphs for the Retrieval of Context-Specific Networks from Genomic Data". PLOS Comput Biol 6 (8): e1000889. doi:10.1371/journal.pcbi.1000889. PMID 20808879. Bibcode: 2010PLSCB...6E0889K.
9. ↑ J.K. Ochab; Z. Burda (Jan 2013). "Maximal entropy random walk in community detection". The European Physical Journal Special Topics 216: 73–81. doi:10.1140/epjst/e2013-01730-6. Bibcode: 2013EPJST.216...73O.
10. ↑ Beraldi, Roberto (Apr 2009). "Biased Random Walks in Uniform Wireless Networks". IEEE Transactions on Mobile Computing 8 (4): 500–513. doi:10.1109/TMC.2008.151.
11. ↑ Da-Cheng Nie; Zi-Ke Zhang; Qiang Dong; Chongjing Sun; Yan Fu (July 2014). "Information Filtering via Biased Random Walk on Coupled Social Network". The Scientific World Journal 2014: 829137. doi:10.1155/2014/829137. PMID 25147867.

## 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Biased random walk on a graph. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Biased_random_walk_on_a_graph&oldid=3430926"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template