Position Matters: Play a Sequential Game to Detect Significant Communities
Yuyao Wang, Jie Cao, Youquan Wang, Jia Wu, Yangyang Liu
Abstract
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SCG</i> —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, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SCG</i> enables differentiation between uncovered communities. Importantly, we establish the existence of a strict Nash equilibrium in <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SCG</i> , suggesting its ability to capture a stable community structure. We run extensive experiments on several synthetic and real-world networks to test <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SCG</i> 's performance. Results show that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SCG</i> can help us well track the network's structural properties and also give us reliable performance compared to related baselines.