Hálózati fontosság növelése: PageRank optimalizálás mint Markov döntési probléma

Csáji, Balázs Csanád (2017) Hálózati fontosság növelése: PageRank optimalizálás mint Markov döntési probléma. In: XXXII. Magyar Operációkutatás Konferencia, 2017. június 14-16., Cegléd.

Text (Extended Abstract) CsBCs-RageRank-Optimization-OpKut-2017.pdf - Other Restricted to Registered users only Download (111kB)

Abstract

Egy standard (centralitási) mérték irányított gráfok csúcsainak fontosságának mérésére a PageRank módszer, amit például a Google is alkalmaz web-keresések fontosság szerinti sorba rendezéséhez. A PageRank fogalmát mind lineáris algebrai mind valószínűségszámítási fogalmakkal bevezethetjük. Ez utóbbi terminológiáját használva, egy csúcs PageRank-je nem más, mint a gráfon értelmezett véletlen bolyongás stacionárius (egyensúlyi) eloszlása az adott csúcsra vonatkozóan. Egy természetes kérdés, hogy egy (adott) irányított gráfban hogyan tudjuk maximalizálni egy (adott) csúcs fontosságát (PageRank-jét), ha az élek egy (adott) részhalmazát megváltoztathatjuk, azaz eldönthetjük, hogy a halmazból mely élek szerepeljenek a gráfban és melyek ne. Az előadásban megmutatjuk, hogy ez probléma (hatékonyan) visszavezethető egy Markov döntési problémára, konkrétan egy sztochasztikus legrövidebb út feladatra. Ennek egy következménye, hogy a probléma polinomiális időben megoldható és például lineáris programozási feladatként is felírható. Az előadásban bevezetünk még egy alternatív mohó algoritmust is, amely szintén polinomiális időben oldja meg a PageRank maximalizálás feladatot, valamint megmutatjuk, hogy a feladat további gyenge korlátozások mellett (például egymást kizáró élek) NP-nehézzé válik.

Actions (login required)

Edit Item