Cooperative game theory approaches for network partitioning

DOI10.1007/978-3-319-62389-4_49MaRDI QIDQ2412439zbMATH OpenOpenAlexFDO

Authors Alekseĭ Yu. Kondrat'ev, Vladimir V. Mazalov, Konstantin Avrachenkov

Publication date 23 October 2017

Full work available at URL https://arxiv.org/abs/1707.03587

zbMATH Keywords

community detectioncooperative gameshedonic gamesMyerson valuenetwork partitioning

Mathematics Subject Classification ID

Cooperative games (91A12) Games involving graphs (91A43) Applications of game theory (91A80) Social networks; opinion dynamics (91D30)

Abstract: The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting denser subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolution. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity based approach and its generalizations can be viewed as particular cases of the hedonic games.

Recommendations

• A game-theoretic approach to graph clustering
• Applying cooperative game theory with coalitional structure for data clustering
• A modified Myerson value for determining the centrality of graph vertices
• Modified Myerson value for determining the centrality of graph vertices
• A cooperative game framework for detecting overlapping communities in social networks

Cited in

(10)

• The Shapley value for cooperative games with restricted worths
• Data clustering via cooperative games: a novel approach and comparative study
• An empirical distribution of the number of subsets in the core partitions of hedonic games
• Applying cooperative games with coalition structure for data clustering
• Game theory in communication networks. Cooperative resolution of interactive networking scenarios.
• A game-theoretic approach to graph clustering
• Bi‐cooperative network games: A link‐based allocation rule
• Applying cooperative game theory with coalitional structure for data clustering
• Decentralized resource allocation for interdependent infrastructures resilience: a cooperative game approach
• The cohesiveness of subgroups in social networks: A view from game theory

This page was built for publication: Cooperative game theory approaches for network partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412439)