当前社区结构探测算法在寻求社区结构划分正确性的同时,算法效率较低.为此,提出一种在算法正确性和算法效率两个方面能取得较好均衡的社区结构探寻算法CoreScan.该算法寻找节点集合中一类称之为“次中心”的特殊节点,再将其作为聚类中心,然后通过D模块度来发现社区结构.理论分析表明,该算法能正确识别Fortunato提出的一类特殊社区结构,且算法效率可达O(n*kmax),其中n是节点数量,kmax是“次中心”最大数量.最后通过多项实验证明,CoreScan算法能够在效率和正确性上取得较好的均衡,适合于在大规模节点集合中进行快速社区结构探寻.%Some community structure identification algorithms in complex network research achieve high quality for identifying community correctly but low efficiency, but some algorithms were on the contrary. It is a challenge for community structure identifying algorithms to balance efficiency and correctness for category meanwhile. In this paper, a new algorithm named CoreScan was proposed. Different from existing algorithm, CoreScan found some special node named subcenter in network and using a preprocessing phase to divide nodes into several communities according to subcenter, then cluster nodes by evaluating the D modularity of community. The definition of subcenter was given and some certifications also were shown to guarantee the correction of CoreScan algorithm. At last, the algorithm was tested on two artificial networks and two real-world graphs. The experimental results show that the algorithm achieves the goal of linear efficiency, and the correction of identifying community is no less than existing algorithms. This algorithm is suitable to large-scale network structure investigation.
展开▼
