Analysis of Graph Centralities with the Help of Shapley Values

The topic of the present research paper refers to the analysis of the social networks’ characteristics. The paper touches upon key questions evaluating the power and the influence of network participants. The objective of this study is to describe and compare existing methodologies with the one that is explored in this paper. The techniques employed are based on the game theory approach and refer to the Shapley value calculation. The research is undertaken to develop a potentially powerful method of approximate calculation of the Shapley value in order to find a balance between computational complexity and the calculation accuracy. The objects under study are exponentially distributed random networks with different graph characteristics. Different applications of the approach based on simple paths between nodes are also proposed in the current work. Experimental results highlight advantages and disadvantages of different approximation methodologies. The comparison with other measures shows that the proposed methodology detects central nodes as expected. Keywords: Social Network Analysis, Shapley Values, Key Nodes, Approximation Methods, Simple Paths, Randomized algorithms.