27 Jul 2017 | Konstantin E. Avrachenkov, Aleksei Yu. Kondratev, Vladimir V. Mazalov
This paper presents two cooperative game theory approaches for network partitioning: the Myerson value and hedonic games. The traditional methods for detecting community structure in networks focus on identifying denser subgraphs. However, the proposed methods highlight not only link density but also the mechanisms of cluster formation. The first approach, based on the Myerson value, emphasizes value allocation in games with interactions constrained by a network. It uses an efficient method based on characteristic functions to calculate the Myerson value, which can be used to determine network centrality. The second approach, based on hedonic games, explains the formation of coalitions and allows for detecting clusters with varying resolution, avoiding the resolution limit problem. The hedonic game approach is particularly suitable for adjusting the resolution level, with the grand coalition and maximal clique decomposition as extreme cases. The modularity-based approach can be viewed as a particular case of hedonic games. The paper also discusses the application of these methods to real-world networks, including the Zachary karate club network, and shows how the resolution parameter can be used to tune the clustering resolution. The results demonstrate that the hedonic game approach provides a natural way to adjust the resolution and generalizes modularity-based methods. The paper concludes with future research directions, including testing the methods on more social networks and developing efficient computational methods.This paper presents two cooperative game theory approaches for network partitioning: the Myerson value and hedonic games. The traditional methods for detecting community structure in networks focus on identifying denser subgraphs. However, the proposed methods highlight not only link density but also the mechanisms of cluster formation. The first approach, based on the Myerson value, emphasizes value allocation in games with interactions constrained by a network. It uses an efficient method based on characteristic functions to calculate the Myerson value, which can be used to determine network centrality. The second approach, based on hedonic games, explains the formation of coalitions and allows for detecting clusters with varying resolution, avoiding the resolution limit problem. The hedonic game approach is particularly suitable for adjusting the resolution level, with the grand coalition and maximal clique decomposition as extreme cases. The modularity-based approach can be viewed as a particular case of hedonic games. The paper also discusses the application of these methods to real-world networks, including the Zachary karate club network, and shows how the resolution parameter can be used to tune the clustering resolution. The results demonstrate that the hedonic game approach provides a natural way to adjust the resolution and generalizes modularity-based methods. The paper concludes with future research directions, including testing the methods on more social networks and developing efficient computational methods.