Random Walk Algorithm
Jump to navigation
Jump to search
A Random Walk Algorithm is an algorithm that is based on a random walk probabilistic model.
- Context:
- It can range from being a Random-Walk-based Natural Language Processing Algorithm to being a Random-Walk-based Image Processing Algorithm.
- Example(s):
- Random Walk with Restart Algorithm such as:
- a Random Walk NLP Algorithm such as:
- a Random-Walk-based Image Processing Algorithm such as:
- …
- Counter-Example(s):
- See: Image Segmentation, Graph Random Walk, Page Rank Algorithm, Semantic Similarity, Align-Disambiguate-Walk Semantic Similarity System, Word Sense Disambiguation Algorithm.
References
2019
- (Valdeolivas, 2019) ⇒ Alberto Valdeolivas, Laurent Tichit, Claire Navarro, Sophie Perrin, Gaelle Odelin, Nicolas Levy, Pierre Cau, Elisabeth Remy, and Anais Baudot (2019). "Random walk with restart on multiplex and heterogeneous biological networks". In: Bioinformatics, Volume 35, Issue 3.
- QUOTE: In this study, we extended the RWR algorithm to multiplex and heterogeneous networks.
(...)
The source code is available on GitHub at: https://github.com/alberto-valdeolivas/RWR-MH.
In addition, an R package is freely available through Bioconductor at: http://bioconductor.org/packages/RandomWalkRestartMH/.
- QUOTE: In this study, we extended the RWR algorithm to multiplex and heterogeneous networks.
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/random_walker_algorithm Retrieved:2015-5-22.
- The random walker algorithm is an algorithm for image segmentation. In the first description of the algorithm,[1] a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. This computation may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a graph, in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs [2]). Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a data fidelity term (e.g., an intensity prior).[3] It has also been extended to other applications. The algorithm was initially published as a conference paper [4] and later as a journal paper.
- ↑ L. Grady: Random Walks for Image Segmentation, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 28, No. 11, pp. 1768–1783, Nov., 2006.
- ↑ P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984
- ↑ Leo Grady: Multilabel Random Walker Image Segmentation Using Prior Models, Proceedings of of CVPR, Vol. 1, pp. 763–770, 2005. [1]
- ↑ Leo Grady, Gareth Funka-Lea: Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials, Proceedings of of the 8th ECCV Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, pp. 230–245, 2004.
2013
- (Pilehvar et al., 2013) ⇒ Mohammad Taher Pilehvar, David Jurgens, and Roberto Navigli. (2013). “Align, Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity.” In: Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL 2013) Volume 1: Long Papers.
- QUOTE: Given a particular node (sense) in the network, repeated random walks beginning at that node will produce a frequency distribution over the nodes in the graph visited during the walk. To extend beyond a single sense, the random walk may be initialized and restarted from a set of senses (seed nodes), rather than just one; this multi-seed walk produces a multinomial distribution over all the senses in WordNet with higher probability assigned to senses that are frequently visited from the seeds.
2009
- (Ramage et al., 2009) ⇒ Daniel Ramage, Anna N. Rafferty, and Christopher D. Manning. (2009). “Random Walks for Text Semantic Similarity.” In: Proceedings of the 2009 Workshop on Graph-based Methods for Natural Language Processing.