Fast Algorithms for Game-Theoretic Centrality Measures

Piotr Lech Szczepański

Abstract

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.
Rodzaj dyplomuPraca doktorska
Autor Piotr Lech Szczepański (WEiTI / II)
Piotr Lech Szczepański
- Instytut Informatyki
Tytuł w języku polskimSzybkie algorytmy do obliczania teoriogrowych miar centralności
Języken angielski
Jednostka dyplomującaWydział Elektroniki i Technik Informacyjnych (WEiTI)
Dyscyplina naukiinformatyka / dziedzina nauk technicznych / obszar nauk technicznych
Data rozpoczęcia17-12-2013
Data obrony31-05-2016
Data zakończenia 21-06-2016
Promotor Mieczysław Muraszkiewicz (WEiTI / II)
Mieczysław Muraszkiewicz
- Instytut Informatyki
, Michalak Tomasz
Michalak Tomasz
-
Recenzenci zewnętrzni Piotr Faliszewski
Piotr Faliszewski
-

Mikołaj Morzy
Mikołaj Morzy
-
Wyróżnienietak
Paginacja 168
Słowa kluczowe w języku polskimwartość Shapleya, wartość Owena, Półwartości, sieci społecznościowe, miary centralności
Słowa kluczowe w języku angielskimthe Shapley value, the Owen value, Semivalues, social networks, centrality measures
Streszczenie w języku polskimW 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.
Klasyfikacja PKT4100
Klasyfikacja KBN28-Informatka
Klasyfikacja europejska80-30
Plik pracy
Szczepanski_doktorat.pdf 1.15 MB
Recenzje
Recenzja pracy Piotra Szczepańskiego wykonana przez dr hab. inż. Piotra Faliszewskiego 368.41 KB
Recenzja pracy Piotra Szczepańskiego wykonana przez dr hab. inż. Mikołaja Morzego 130.58 KB
Inne pliki
abstract-Szczepański.pdf 68.35 KB
streszczenie-Szczepański.pdf 122.51 KB

Pobierz odnośnik do tego rekordu

Powrót