Lanzhou University, School of Information Science and Engineering, Lanzhou, 730000, China.
Gansu Resources and Environmental Science Data Engineering Technology Research Center, Lanzhou, 730000, China.
Sci Rep. 2018 May 23;8(1):8064. doi: 10.1038/s41598-018-26415-3.
Community detection has been paid much attention in many fields in recent years, and a great deal of community-detection methods have been proposed. But the time consumption of some of them is heavy, limiting them from being applied to large-scale networks. On the contrary, there exist some lower-time-complexity methods. But most of them are non-deterministic, meaning that running the same method many times may yield different results from the same network, which reduces their practical utility greatly in real-world applications. To solve these problems, we propose a community-detection method in this paper, which takes both the quality of the results and the efficiency of the detecting procedure into account. Moreover, it is a deterministic method which can extract definite community structures from networks. The proposed method is inspired by the voting behaviours in election activities in the social society, in which we first simulate the voting procedure on the network. Every vertex votes for the nominated candidates following the proposed voting principles, densely connected groups of vertices can quickly reach a consensus on their candidates. At the end of this procedure, candidates and their own voters form a group of clusters. Then, we take the clusters as initial communities, and agglomerate some of them into larger ones with high efficiency to obtain the resulting community structures. We conducted extensive experiments on some artificial networks and real-world networks, the experimental results show that our proposed method can efficiently extract high-quality community structures from networks, and outperform the comparison algorithms significantly.
近年来，社区检测在许多领域受到了广泛关注，提出了大量的社区检测方法。但是，其中一些方法的时间消耗很大，限制了它们在大规模网络中的应用。相反，存在一些时间复杂度较低的方法。但是，大多数都是非确定性的，这意味着在同一个网络上运行相同的方法多次可能会得到不同的结果，这大大降低了它们在实际应用中的实用性。为了解决这些问题，我们在本文中提出了一种社区检测方法，该方法既考虑了结果的质量，也考虑了检测过程的效率。此外，它是一种确定性方法，可以从网络中提取确定的社区结构。该方法受到社会选举活动中投票行为的启发，我们首先在网络上模拟投票过程。每个顶点根据提议的投票原则为提名的候选人投票，密集连接的顶点组可以快速就其候选人达成共识。在这个过程结束时，候选人和他们自己的选民形成一组集群。然后，我们将集群作为初始社区，并以高效的方式将其中一些社区合并成更大的社区，以获得最终的社区结构。我们在一些人工网络和真实网络上进行了广泛的实验，实验结果表明，我们提出的方法可以有效地从网络中提取高质量的社区结构，并显著优于比较算法。
