Cooperative Game Theory Approaches for Network Partitioning

Cooperative Game Theory Approaches for Network Partitioning

27 Jul 2017 | Konstantin E. Avrachenkov, Aleksei Yu. Kondratev, Vladimir V. Mazalov
The paper explores cooperative game theory approaches for network partitioning, focusing on community detection. Traditional methods often rely on identifying denser subgraphs, while this paper proposes two novel methods: the Myerson value and hedonic games. The Myerson value emphasizes the impact of all coalitions and can be calculated efficiently using characteristic functions. The hedonic game approach explains the formation of coalitions and allows for varying resolution, making it particularly intuitive for tuning the level of detail in cluster detection. The paper also discusses how modularity-based approaches can be seen as special cases of hedonic games, providing a more interpretable framework. The methods are applied to various networks, including the Zachary karate club network, demonstrating their effectiveness and flexibility. The authors conclude by outlining future research directions, including testing their methods on more social networks and developing efficient computational algorithms.The paper explores cooperative game theory approaches for network partitioning, focusing on community detection. Traditional methods often rely on identifying denser subgraphs, while this paper proposes two novel methods: the Myerson value and hedonic games. The Myerson value emphasizes the impact of all coalitions and can be calculated efficiently using characteristic functions. The hedonic game approach explains the formation of coalitions and allows for varying resolution, making it particularly intuitive for tuning the level of detail in cluster detection. The paper also discusses how modularity-based approaches can be seen as special cases of hedonic games, providing a more interpretable framework. The methods are applied to various networks, including the Zachary karate club network, demonstrating their effectiveness and flexibility. The authors conclude by outlining future research directions, including testing their methods on more social networks and developing efficient computational algorithms.
Reach us at info@study.space