On a Bypass Centrality Concept for Networks drawing on the Shapley Value

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.


Citation style:
Could not load citation form.

Access Statistic

Last 12 Month:


Use and reproduction:
All rights reserved