A Fast Approach for Detecting Overlapping Communities in Social Networks Based on Game Theory

Community detection, a fundamental task in social network analysis, aims to identify groups of nodes in a network such that nodes within a group are much more connected to each other than to the rest of the network. The cooperative theory and non-cooperative game theory have been used separately for detecting communities. In this paper, we develop a new approach that utilizes both cooperative and non-cooperative game theory to detect communities. The individuals in a social network are modelled as playing cooperative game for achieving and improving group's utilities, meanwhile individuals also play the non-cooperative game for improving individual's utilities. By combining the cooperative and non-cooperative game theories, utilities of groups and individuals can be taken into account simultaneously, thus the communities detected can be more rational and the computational cost will be decreased. The experimental results on synthetic and real networks show that our algorithm can fast detect overlapping communities.