Maximal entropy random walk

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]

Additionally, it recreates some properties of quantum mechanics, suggesting a way to repair the discrepancy between diffusion models and quantum predictions, like Anderson localization.[10]

  1. ^ Sinatra, Roberta; Gómez-Gardeñes, Jesús; Lambiotte, Renaud; Nicosia, Vincenzo; Latora, Vito (2011). "Maximal-entropy random walks in complex networks with limited information" (PDF). Physical Review E. 83 (3): 030103. arXiv:1007.4936. Bibcode:2011PhRvE..83c0103S. doi:10.1103/PhysRevE.83.030103. ISSN 1539-3755. PMID 21517435. S2CID 6984660.
  2. ^ Li, Rong-Hua; Yu, Jeffrey Xu; Liu, Jianquan (2011). Link prediction: the power of maximal entropy random walk (PDF). Association for Computing Machinery Conference on Information and Knowledge Management. p. 1147. doi:10.1145/2063576.2063741. S2CID 15309519. Archived from the original (PDF) on 12 February 2017.
  3. ^ Ochab, J.K.; Burda, Z. (2013). "Maximal entropy random walk in community detection". The European Physical Journal Special Topics. 216 (1): 73–81. arXiv:1208.3688. Bibcode:2013EPJST.216...73O. doi:10.1140/epjst/e2013-01730-6. ISSN 1951-6355. S2CID 56409069.
  4. ^ Chen, Y.; Georgiou, T.T.; Pavon, M.; Tannenbaum, A. (2016). "Robust transport over networks". IEEE Transactions on Automatic Control. 62 (9): 4675–4682. arXiv:1603.08129. Bibcode:2016arXiv160308129C. doi:10.1109/TAC.2016.2626796. PMC 5600536. PMID 28924302.
  5. ^ Delvenne, Jean-Charles; Libert, Anne-Sophie (2011). "Centrality measures and thermodynamic formalism for complex networks". Physical Review E. 83 (4): 046117. arXiv:0710.3972. Bibcode:2011PhRvE..83d6117D. doi:10.1103/PhysRevE.83.046117. ISSN 1539-3755. PMID 21599250. S2CID 25816198.
  6. ^ 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. ISSN 2168-2267. PMID 25137693. S2CID 20962642.
  7. ^ L. Wang, J. Zhao, X. Hu, J. Lu, Weakly supervised object localization via maximal entropy random walk, ICIP, 2014.
  8. ^ 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. ISSN 1070-9908. S2CID 16305991.
  9. ^ Galinsky, Vitaly L.; Frank, Lawrence R. (2015). "Simultaneous Multi-Scale Diffusion Estimation and Tractography Guided by Entropy Spectrum Pathways". IEEE Transactions on Medical Imaging. 34 (5). Institute of Electrical and Electronics Engineers (IEEE): 1177–1193. doi:10.1109/tmi.2014.2380812. ISSN 0278-0062. PMC 4417445. PMID 25532167.
  10. ^ Burda, Z.; Duda, J.; Luck, J. M.; Waclaw, B. (23 April 2009). "Localization of the Maximal Entropy Random Walk". Physical Review Letters. 102 (16): 160602. arXiv:0810.4113. Bibcode:2009PhRvL.102p0602B. doi:10.1103/physrevlett.102.160602. ISSN 0031-9007. PMID 19518691. S2CID 32134048.