Maximal entropy random walk (MERW) is a popular type of biased random walk on a graph, in which transition probabilities are chosen accordingly to the principle of maximum entropy, which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While standard random walk chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing entropy rate, MERW maximizes it globally (average entropy production) by assuming uniform probability distribution among all paths in a given graph.
MERW is used in various fields of science. A direct application is choosing probabilities to maximize transmission rate through a constrained channel, analogously to Fibonacci coding. Its properties also made it useful for example in analysis of complex networks,[1] like link prediction,[2] community detection,[3]
robust transport over networks[4] and centrality measures.[5] Also in image analysis, for example for detecting visual saliency regions,[6] object localization,[7] tampering detection[8] or tractography problem.[9]
^Jin-Gang Yu; Ji Zhao; Jinwen Tian; Yihua Tan (2014). "Maximal Entropy Random Walk for Region-Based Visual Saliency". IEEE Transactions on Cybernetics. 44 (9). Institute of Electrical and Electronics Engineers (IEEE): 1661–1672. doi:10.1109/tcyb.2013.2292054. ISSN2168-2267. PMID25137693. S2CID20962642.
^Korus, Pawel; Huang, Jiwu (2016). "Improved Tampering Localization in Digital Image Forensics Based on Maximal Entropy Random Walk". IEEE Signal Processing Letters. 23 (1). Institute of Electrical and Electronics Engineers (IEEE): 169–173. Bibcode:2016ISPL...23..169K. doi:10.1109/lsp.2015.2507598. ISSN1070-9908. S2CID16305991.