社区结构是复杂网络的一个重要拓扑结构特征,随着网络科学的迅猛发展,已经成为复杂网络的研究焦点。但当前的社区发现算法仍存在如下几个问题:时间复杂度大,社区个数需提前确定,社区结构稳定性差等。聚类是社区识别的重要方法,近邻传播(affinity propagation,AP)算法将所有数据点都考虑为潜在的中心点,通过多次迭代使中心点逐渐浮现,最终使用中心点进行聚类,无需给定聚类数,聚类稳定性较好。在社区发现过程中,数据集通常拥有复杂的结构,节点间的连接密度分布不均,传统AP算法的欧式距离度量表示的是个体在空间上的差异性,不能完全反映数据间的结构信息。同一社区内的节点通常倾向于更紧密的连接,拥有更大的相似性。因此,本文针对社区结构特征,在传统近邻传播算法的相似性度量上,分别引入局部随机游走和局部朴素贝叶斯模型两种方法对AP算法进行改进。主要研究包括:(1)有叠加效应的局部随机游走近邻传播算法(SRWAP)的研究。基于局部随机游走过程,引入六度分割理论确定随机游走步长,把状态概率转化为节点间的相似性矩阵,提出有叠加效应的局部随机游走近邻传播算法。该随机游走相似性指标综合考虑了游走范围内的直接相邻和间接相邻关系。实验证明该算法能缩短运行时间,提高聚类模块度。(2)局部朴素贝叶斯近邻传播算法(LNBCNAP)的研究。针对共同邻居节点的不同作用,引入局部朴素贝叶斯模型中的角色函数,并在邻接矩阵的基础上,考虑节点的自相似性和有共同邻居的无连接节点的相似性,提出局部朴素贝叶斯近邻传播算法。该方法综合了节点所在局部范围内的所有可能连接关系。实验证明改进后的算法在数据结构松散的情况下能取得更接近真实划分的聚类结果。(3)通过在人工基准数据集和真实网络数据集上进行实验,结果表明SRWAP算法和LNBCNAP算法能有效提高发现社区的模块度和归一化互信息,使社区发现结果更接近真实网络划分,提高社区发现的准确性,同时能减少算法运行时间。