The method of leader's overthrow in networks based on Shapley value. (December 2016) - Belik, Ivan; Jörnsten, Kurt
Abstract: Quantitative methods for leaders' detection and overthrow are useful tools for decision-making in many real-life social networks. In the given research, we present algorithms that detect and overthrow the most influential node to the weaker leadership positions following the greedy method in terms of structural modifications. We employ the concept of Shapley value from the area of cooperative game theory to measure a node's leadership and to develop the leader's overthrow algorithms. Specifically, we introduce a quantitative approach to analyze prospective structural modifications in social networks to make the initially identified network leader less influential. The resulting mechanism is based on the symbiosis of game-theoretic and algorithmic concepts. It presents a useful tool for the technical analysis of the primary structural data in the initial steps of multifaceted quantitative network analysis where the raw data (i.e., linkages) is frequently the only knowledge about interrelations in social networks. Highlights: The quantitative approach for the leader's overthrow in social networks is proposed. The developed algorithms rely on the symbiosis of game theoretic and algorithmic concepts. The advantages of the Shapley value compared to the traditional centrality metrics are analyzed. The practical importance of the developed algorithms is based on their applicability for the analysis of real-life networks.