Titelaufnahme

Titel
On a bypass centrality concept for networks drawing on the Shapley value / Helmut Meister
VerfasserMeister, Helmut
ErschienenHagen : FernUniversität in Hagen, 2018
Ausgabe
Elektronische Ressource
Umfang1 Online-Ressource (15 Seiten) : Diagramme
SerieLehrgebiet Stochastik. Forschungsbericht
SchlagwörterSpieltheorie / Shapley-Lösung
URNurn:nbn:de:hbz:6:2-128612 
Zugänglichkeit
 Das Dokument ist öffentlich im Netz zugänglich.
Dateien
On a bypass centrality concept for networks drawing on the Shapley value [0.55 mb]
Zusammenfassung

First, we analyse game-theoretic solution concepts for the assessment of members of a network drawing on the Shapley Value. Our approach starts with the concept of Betweenness Centrality as known from Social Network Analysis. We will also be interested in Centrality Concepts, which satisfy the conditions of Core Allocations of the value of the whole network and their relationship to Shapley Value based concepts. It turns out that a centrality concept derived from the membership of vertices in global shortest paths within the network provides a Core Allocation and is therefore in some sense agreeable by the members of the network. We will also consider relative shortest paths within coalitions of vertices. For this approach, which leads to a concept of Bypass Centrality, we get a different assessment method, which better reflects the local connectivity of the network and respects the capability of vertices to form bypasses for connections potentially blocked for some reason. For this type of allocations it seems to be an open problem, whether the Shapley Value satisfies the conditions of a Core Allocation in general. Apart from these game-theoretical questions, our focus concerns the computational complexity for the calculation of the Shapley Value, which is in general considered to be a NP-complete problem. For the computation of the Shapley Value based on global shortest paths an efficient algorithm has already be found. We can show that also for the concept based on relative shortest paths an algorithm exists, which solves the problem in pseudo-polynomial time, depending on a limitation of the number of connecting paths considered for each pair of vertices. This shows that in our situation the approach reduces the calculation to a weakly NP-complete problem.

Klassifikation
Links
Nachweis
Nutzungshinweis
 Das Medienwerk ist im Rahmen des deutschen Urheberrechts nutzbar.