The Design And Analysis Of The Community Evolution Game For Overlapping Community Detection

Complex networks is one of the most important fundamental research areas in this century. The overlapping community structure is the key property of complex net-works. In this paper, we focused on one of the most centring areas in the research of complex networks, the overlapping community detection problem. With the commu-nity evolution game framework based on potential game, we proposed the concept of social distance and used this idea to construct a gain function to form a potential game, which guaranteed existence of equilibrium in the community evolution game. Then we gave a overlapping community detection algorithm SDMODGAME under this frame-work and analyzed the performances and results in different kinds of network datasets.Our main contributions were:· gave a systematic analysis of the framework for community evolution game and a restricted formalization of overlapping community detection problem;· proposed a concept called social distance combining the distance in networks and the community structure to reflect the read world;· designed a gain function based on the concept of social distance function which can guarantee the existence of the pure Nash equilibrium of our game. And we also could extend the social distance function to analyze more complex networks;· transferred the computation to localized version under reasonable assumption, and designed the SDMODGAME algorithm for detecting overlapping commu-nity structure.