Ta witryna wykorzystuje cookies. Więcej informacji można znaleźć na stronie Polityka dotycząca cookies i podobnych technologii. ZAMKNIJ Zamknij ostrzeżenie dotyczące cookies

Piotr Szczepański obronił rozprawę doktorską

piotr_szczepanski

P.Szczepański

W dniu 31 maja 2016 roku Piotr Szczepański obronił rozprawę doktorską pt. "Fast Algorithms for Game-Theoretic Centrality Measures ". Polski tytuł rozprawy "Szybkie algorytmy do obliczania teoriogrowych miar centralności ", rozprawa jest napisana w języku angielskim. Promotorem rozprawy był prof. dr hab. inż. Mieczysław Muraszkiewicz.

W niniejszej rozprawie autor porusza problem złożoności obliczeniowej teoriogrowych centralności. W teoriogrowym podejściu do analizy sieci traktujemy wierzchołki jako graczy w koalicyjnej grze, w której wartość koalicji wierzchołków wynika ze struktury sieci. W takiej grze ważność każdego wierzchołka może być określona przez dowolne rozwiązanie gry koalicyjnej (w szczególności przez wartość Shapleya). Z jednej strony zaletą takiego podejścia do centralności jest fakt, że ranking wierzchołków wynika nie tylko z indywidualnej roli każdego wierzchołka, lecz także z tego, ile dany wierzchołek wnosi do roli każdego podzbioru wierzchołków w grafie. Jednakże z drugiej strony liczenie rozwiązań gier koalicyjnych jest bardzo trudne. Główną kontrybucją tej rozprawy jest pokazanie, jak liczyć w czasie wielomianowym teoriogrowe centralności dla wielu różnych rozwiązań gier koalicyjnych. W tej pracy autor skupia się na szybkim liczeniu teoriogrowych centralności opartych na wartości Shapleya i jej różnych rozszerzeń. W szczególności analizuje on obliczeniowe własności Półwartości, będące uogólnieniem wartości Shapleya, i koalicyje Półwartości, będące uogólnieniem wartości Owena. Dodaktowo, autor dowodzi #P-trudności liczenia wartości Shapleya w grach spójnościowych i proponuje szybki algorytm radzący sobie z tym problemem. Na zakończenie, w pracy analizowane są uogólnione gry koalicyjne, w których koleność graczy wyznacza wartość koalicji. Autor proponuje nową, zwięzłą reprezentację tych gier, która pozwala na obliczanie w czasie wielomianowym ze względu na wielkość reprezentacji dwóch dedytkowanych tym grom rozszerzeń wartości Shapley.

In this dissertation, we analyze the computational properties of game-theoretic centrality measures. The key idea behind game-theoretic approach to network analysis is to treat nodes as players in a cooperative game, where the value of each coalition of nodes is determined by certain graph properties. Next, the centrality of any individual node is determined by a chosen game-theoretic solution concept (notably, the Shapley value) in the same way as the payoff of a player in a cooperative game. On one hand, the advantage of game-theoretic centrality measures is that nodes are ranked not only according to their individual roles but also according to how they contribute to the role played by all possible subsets of nodes. On the other hand, the disadvantage is that the game-theoretic solution concepts are typically computationally challenging. The main contribution of this dissertation is that we show that a wide variety of game-theoretic solution concepts on networks can be computed in polynomial time. Our focus is on centralities based on the Shapley value and its various extensions, such as the Semivalues and Coalitional Semivalues. Furthermore, we prove #P-hardness of computing the Shapley value in connectivity games and propose an algorithm to compute it. Finally, we analyse computational properties of generalized version of cooperative games in which order of player matters. We propose a new representation for such games, called generalized marginal contribution networks, that allows for polynomial computation in the size of the representation of two dedicated extensions of the Shapley value to this class of games.

 

Ostatnia modyfikacja: wtorek, 31 maja 2016, 14:08:47, Bożenna Skalska

x x Aktualności (2) - wg daty publikacji

‹‹ Maj 2016 ››
Pon Wt Śr Czw Pt So N
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31