Overlapping community detection in social networks using coalitional games

摘要

Community detection is a significant research problem in various fields such as computer science, sociology and biology. The singular characteristic of communities in social networks is the multimembership of a node resulting in overlapping communities. But dealing with the problem of overlapping community detection is computationally expensive. The evolution of communities in social networks happens due to the self-interest of the nodes. The nodes of the social network acts as self-interested players, who wish to maximize their benefit through interactions in due course of community formation. Game theory provides a systematic framework tox capture the interactions between these selfish players in the form of games. In this paper, we propose a Community Detection Game (CDG) that works under the cooperative game framework. We develop a greedy community detection algorithm that employs Shapley value mechanism and majority voting mechanism in order to disclose the underlying community structure of the given network. Extensive experimental evaluation on synthetic and real-world network datasets demonstrates the effectiveness of CDG algorithm over the state-of-the-art algorithms.