Discovering overlapping communities in social networks: A novel game-theoretic approach

Article type: Research Article

Authors: Alvari, Hamidreza^; | Hashemi, Sattar | Hamzeh, Ali

Affiliations: Department of Electrical and Computer Engineering, Shiraz University, Shiraz, Iran. E-mails: alvari@cse.shirazu.ac.ir, s_hashemi@shirazu.ac.ir, ali@cse.shirazu.ac.ir

Note: [] Corresponding author. E-mail: alvari@cse.shirazu.ac.ir

Abstract: Identifying communities in social networks has been receiving the increasing attentions recently. However, the overlapping concept has received little attentions in the literature, although it is observed in almost all social networks. In this study, we propose a framework based on the game theory and the structural equivalence concept to address the detection of overlapping communities in social networks. Specifically, we consider the underlying graph as a hypothetical social networking website and regard each vertex of this graph as an agent performing in this multiagent environment. Since each agent may belong to several communities simultaneously, we are able to find overlapping community structure of social networks. The rigorous proof of the existence of Nash equilibrium in this game is provided which shows that the method always reaches to the final solution. Experimental results on the benchmark and real world graphs show superiority of our approach over the other state-of-the-art methods.

Keywords: Game theory, multiagent environment, overlapping communities, social networks, structural equivalence

DOI: 10.3233/AIC-130557

Journal: AI Communications, vol. 26, no. 2, pp. 161-177, 2013