Maximal entropy random walk: Difference between revisions

Revision as of 13:30, 22 January 2022

Revision as of 20:47, 3 October 2022

Line 2:

'''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,<ref name="SinatraGómez-Gardeñes2011">{{cite journal|last1=Sinatra|first1=Roberta|last2=Gómez-Gardeñes|first2=Jesús|last3=Lambiotte|first3=Renaud|last4=Nicosia|first4=Vincenzo|last5=Latora|first5=Vito|title=Maximal-entropy random walks in complex networks with limited information|journal=Physical Review E|volume=83|issue=3|pages=030103|year=2011|issn=1539-3755|doi=10.1103/PhysRevE.83.030103|pmid=21517435|url=http://www.robertasinatra.com/pdf/sinatra_maximal_entropy.pdf|bibcode=2011PhRvE..83c0103S|arxiv=1007.4936|s2cid=6984660 }}</ref> like link prediction,<ref name="LiYu2011">{{cite conference|last1=Li|first1=Rong-Hua|last2=Yu|first2=Jeffrey Xu|last3=Liu|first3=Jianquan|title=Link prediction: the power of maximal entropy random walk|year=2011|pages=1147|doi=10.1145/2063576.2063741|s2cid=15309519 |url=https://pdfs.semanticscholar.org/f185/bc2499be95b4312169a7e722bac570c2d509.pdf|archive-url=https://web.archive.org/web/20170212090812/https://pdfs.semanticscholar.org/f185/bc2499be95b4312169a7e722bac570c2d509.pdf|url-status=dead|archive-date=2017-02-12|conference=Association for Computing Machinery Conference on Information and Knowledge Management|conference-url=http://www.cikm2011.org/}}</ref> community detection,<ref name="OchabBurda2013">{{cite journal|last1=Ochab|first1=J.K.|last2=Burda|first2=Z.|title=Maximal entropy random walk in community detection|journal=The European Physical Journal Special Topics|volume=216|issue=1|year=2013|pages=73–81|issn=1951-6355|doi=10.1140/epjst/e2013-01730-6|arxiv=1208.3688|bibcode=2013EPJST.216...73O|s2cid=56409069 }}</ref>

robust transport over networks<ref name="CGPT2016">{{cite journal|last1=Chen|first1=Y.|last2=Georgiou|first2=T.T.|last3=Pavon|first3=M.|last4=Tannenbaum|first4=A.|title=Robust transport over networks|journal=IEEE Transactions on Automatic Control|volume=62|issue=9|year=2016|pages=4675–4682|doi=10.1109/TAC.2016.2626796|pmid=28924302|pmc=5600536|arxiv=1603.08129|bibcode=2016arXiv160308129C}}</ref> and [[centrality]] measures.<ref name="DelvenneLibert2011">{{cite journal|last1=Delvenne|first1=Jean-Charles|last2=Libert|first2=Anne-Sophie|title=Centrality measures and thermodynamic formalism for complex networks|journal=Physical Review E|volume=83|issue=4|pages=046117|year=2011|issn=1539-3755|doi=10.1103/PhysRevE.83.046117|pmid=21599250|arxiv=0710.3972|bibcode=2011PhRvE..83d6117D|s2cid=25816198 }}</ref> Also in [[image analysis]], for example for detecting visual saliency regions,<ref name=saliency>{{cite journal | title=Maximal Entropy Random Walk for Region-Based Visual Saliency | journal=IEEE Transactions on Cybernetics | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=44 | issue=9 | year=2014 | issn=2168-2267 | doi=10.1109/tcyb.2013.2292054 | pmid=25137693 | pages=1661–1672| last1=Jin-Gang Yu | last2=Ji Zhao | last3=Jinwen Tian | last4=Yihua Tan | s2cid=20962642 }}</ref> object localization,<ref name=local>[https://ieeexplore.ieee.org/abstract/document/6678551/ L. Wang, J. Zhao, X. Hu, J. Lu, ''Weakly supervised object localization via maximal entropy random walk''], ICIP, 2014.</ref> tampering detection<ref name=tamp>{{cite journal | lastlast1=Korus | firstfirst1=Pawel | last2=Huang | first2=Jiwu | title=Improved Tampering Localization in Digital Image Forensics Based on Maximal Entropy Random Walk | journal=IEEE Signal Processing Letters | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=23 | issue=1 | year=2016 | issn=1070-9908 | doi=10.1109/lsp.2015.2507598 | pages=169–173| bibcode=2016ISPL...23..169K | s2cid=16305991 }}</ref> or [[tractography]] problem.<ref name=trac>{{cite journal | lastlast1=Galinsky | firstfirst1=Vitaly L. | last2=Frank | first2=Lawrence R. | title=Simultaneous Multi-Scale Diffusion Estimation and Tractography Guided by Entropy Spectrum Pathways | journal=IEEE Transactions on Medical Imaging | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=34 | issue=5 | year=2015 | issn=0278-0062 | doi=10.1109/tmi.2014.2380812 | pmid=25532167 | pmc=4417445 | pages=1177–1193}}</ref>

Additionally, it recreates some properties of [[quantum mechanics]], suggesting a way to repair the discrepancy between [[diffusion]] models and quantum predictions, like [[Anderson localization]].<ref name=prl>{{cite journal | lastlast1=Burda | firstfirst1=Z. | last2=Duda | first2=J. | last3=Luck | first3=J. M. | last4=Waclaw | first4=B. | title=Localization of the Maximal Entropy Random Walk | journal=Physical Review Letters | volume=102 | issue=16 | date=2009-04-23 | issn=0031-9007 | doi=10.1103/physrevlett.102.160602 | pmid=19518691 | page=160602| bibcode=2009PhRvL.102p0602B | arxiv=0810.4113 | s2cid=32134048 }}</ref>

== Basic model ==