A game theoretic algorithm to detect overlapping community structure in networks |
| |
Authors: | Xu Zhou Xiaohui Zhao Yanheng Liu Geng Sun |
| |
Institution: | 1. Center for Computer Fundamental Education, Jilin University, Changchun, Jilin 130012, China;2. College of Communication Engineering, Jilin University, Changchun, Jilin 130012, China;3. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;4. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, Jilin 130012, China |
| |
Abstract: | Community detection can be used as an important technique for product and personalized service recommendation. A game theory based approach to detect overlapping community structure is introduced in this paper. The process of the community formation is converted into a game, when all agents (nodes) cannot improve their own utility, the game process will be terminated. The utility function is composed of a gain and a loss function and we present a new gain function in this paper. In addition, different from choosing action randomly among join, quit and switch for each agent to get new label, two new strategies for each agent to update its label are designed during the game, and the strategies are also evaluated and compared for each agent in order to find its best result. The overlapping community structure is naturally presented when the stop criterion is satisfied. The experimental results demonstrate that the proposed algorithm outperforms other similar algorithms for detecting overlapping communities in networks. |
| |
Keywords: | Game theory Utility function Community detection |
本文献已被 ScienceDirect 等数据库收录! |
|