Position Matters: Play a Sequential Game to Detect Significant Communities

Detecting significant communities via an algorithmic game-theoretic model has recently shown great promise, which seeks to formulate community detection as a competitive game, enabling us to study the network's potential structure with a systematic tool. However, fully leveraging its potential to uncover the mechanism behind community formation remains a challenge. Here we propose SCG-a Sequential Community Game model to track and characterize the network's structural property. Unlike conventional formulations where individual nodes are treated as players, our model considers communities as players who strive to maximize their structural utility by strategically selecting member nodes. By prioritizing significant communities sequentially, SCG enables differentiation between uncovered communities. Importantly, we establish the existence of a strict Nash equilibrium in SCG, suggesting its ability to capture a stable community structure. We run extensive experiments on several synthetic and real-world networks to test SCG's performance. Results show that SCG can help us well track the network's structural properties and also give us reliable performance compared to related baselines.