Abstract: In view of the problems of large amount of calculation and instability of present community structure detection algorithms, this paper puts forward a new community structure detection algorithm of local information based on the Newman fast algorithm and LPAm algorithm. The algorithm uses node degrees and shared neighbor numbers to define nodes similarity, and uses two preset parameters to improve the structure of society gradually. Algorithm performance analysis has showed that the algorithm not only has linear time complexity, but also is a stability algorithm. The experimental results have showed that the proposed algorithm performs well than the Newman fast algorithm and LPAm algorithm in terms of accuracy, and it’s feasible and effective.

Key words: community structure detection, node similarity, linear time complexity, stability

摘要： 针对目前社团结构检测算法计算量大以及不稳定的问题，在经典的Newman快速与LPAm的基础上提出了一种基于局部信息的社团发现新算法。算法利用节点度和共享邻居数定义节点相似度，并结合两个预设参数，逐步优化社团结构。性能分析证明，该算法不仅具有线性阶时间复杂度，而且是一种稳定的算法。实验结果表明，该算法在准确度上优于Newman快速和LPAm，且可行与有效。

关键词: 社团结构检测, 节点相似度, 线性阶时间复杂度, 稳定