基于聚类粒化的社团发现算法

为了实现复杂网络社团发现算法的复杂度和精确度间的均衡，提出一种基于聚类粒化的社团发现算法(CGCDA)，将网络粒化获得的粒子视为一个社团，粒化结果即为对网络的社团划分。首先，将网络中的每个节点视为基本粒，通过初始粒化操作实现对网络的粒化；然后，针对获得的粒化集合中满足粒化系数的粒子进行聚类粒化操作，分层粒化直到不存在满足要求的粒子对；最后，将粒子对中的重叠节点视为孤立点，用邻居节点投票法把孤立节点归并到相应的粒子中，实现对复杂网络的社团划分。实验实现了Newman快速算法（NFA）、标号传播算法（LPA）和CGCDA。实验结果表明，CGCDA在四个基准数据集上可获得平均高于LPA 7.6%的模块度和低于NFA 96%的时间。CGCDA时间复杂度较低，获取的社团模块度较高，实现了社团发现时间和精确度的均衡，相比NFA、LPA总体性能更优。

Community detection algorithm based on clustering granulation

To keep the trade-off of time complexity and accuracy of community detection in complex networks, Community Detection Algorithm based on Clustering Granulation (CGCDA) was proposed in this paper. The granules were regarded as communities so that the granulation for a network was actually the community partition of a network. Firstly, each node in the network was regarded as an original granule, then the granule set was obtained by the initial granulation operation. Secondly, granules in this set which satisfied granulation coefficient were merged by clustering granulation operation. The process was finished until granulation coefficient was not satisfied in the granule set. Finally, overlapping nodes among some granules were regard as isolated points, and they were merged into corresponding granules based on neighbor nodes voting algorithm to realize the community partition of complex network. Newman Fast Algorithm (NFA), Label Propagation Algorithm (LPA), CGCDA were realized on four benchmark datasets. The experimental results show that CGCDA can achieve modularity 7.6% higher than LPA and time 96% less than NFA averagely. CGCDA has lower time complexity and higher modularity. The balance between time complexity and accuracy of community detection is achieved. Compared with NFA and LPA, the whole performance of CGCDA is better.