关键词: 社区结构, 社区探测, Q模块度, D模块度

Abstract: 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.

Key words: community structure, community detection, Q modularity, D modularity