Incremental Dynamic Community Detection Based on Local Rapid Update Under Non-Cooperative Game Theoretic Framework

Community detection algorithms based on game theory model the formation of communities as a game. When the game reaches equilibrium, the community structure is revealed. These algorithms provide good interpretability for the community formation process, thus attracting the attention of scholars. In particular, methods based on non-cooperative games emphasize independent decision-making by individuals, exhibiting good adaptability to dynamic network changes. These methods discover new community structures by updating node strategies. However, existing community detection algorithms based on non-cooperative games face challenges such as randomness in static networks and the need for repeated global games in dynamic networks. To address these issues, the paper investigates an Incremental Dynamic Community Detection Algorithm based on Local Rapid Update under Non-cooperative Game Theoretic Framework (IDCDG). On the one hand, we propose to play the game according to the importance of the nodes from small to large, to use the utility function based on local information, and to use a greedy strategy to choose the best community affiliation. On the other hand, we give the definitions of active nodes and non-active nodes, initialize the active nodes, and reinitialize the non-active nodes when the historical community is not connected. Finally, we propose a fast game queue and prove that when the queue is empty, the game reaches equilibrium. The experimental results on real networks and synthetic networks verify the effectiveness of our algorithm.