Department of Physics, Isfahan University of Technology, Isfahan, 84156-83111, Iran.
Sci Rep. 2022 Jun 30;12(1):11054. doi: 10.1038/s41598-022-15095-9.
Detecting communities in complex networks is of paramount importance, and its wide range of real-life applications in various areas has caused a lot of attention to be paid to it, and many efforts have been made to have efficient and accurate algorithms for this purpose. In this paper, we proposed a non-cooperative game theoretic-based algorithm that is able to detect overlapping communities. In this algorithm, nodes are regarded as players, and communities are assumed to be groups of players with similar strategies. Our two-phase algorithm detects communities and the overlapping nodes in separate phases that, while increasing the accuracy, especially in detecting overlapping nodes, brings about higher algorithm speed. Moreover, there is no need for setting parameters regarding the size or number of communities, and the absence of any stochastic process caused this algorithm to be stable. By appropriately adjusting stop criteria, our algorithm can be categorized among those with linear time complexity, making it highly scalable for large networks. Experiments on synthetic and real-world networks demonstrate our algorithm's good performance compared to similar algorithms in terms of detected overlapping nodes, detected communities size distribution, modularity, and normalized mutual information.
检测复杂网络中的社区至关重要，其在各个领域的广泛实际应用引起了广泛关注，并且已经做出了许多努力来为此目的开发高效准确的算法。在本文中，我们提出了一种基于非合作博弈理论的算法，能够检测重叠社区。在这个算法中，节点被视为参与者，社区被假设为具有相似策略的参与者群体。我们的两阶段算法在单独的阶段中检测社区和重叠节点，在提高准确性的同时，特别是在检测重叠节点方面，提高了算法速度。此外，不需要设置关于社区大小或数量的参数，并且没有任何随机过程使得该算法稳定。通过适当调整停止标准，我们的算法可以归类为具有线性时间复杂度的算法，使其能够适用于大型网络。在合成和真实网络上的实验表明，与类似算法相比，我们的算法在检测到的重叠节点、检测到的社区大小分布、模块度和归一化互信息方面表现良好。
