随着社交网络的不断发展,社区发现已经成为复杂网络领域的一个重要的研究热点。若干个社区组成了一个完整的网络,在社区的内部,节点之间的连接相对紧密,而社区与社区之间节点间的连接则相对松散。标签传播算法LPA(Label Propagation Algorithm)是社区发现算法中比较优秀的算法。它的线性的时间复杂度是它的一大优势。虽然LPA有很多的优点,但是缺点也是非常明显的。由于标签的随机选择,LPA不能保证每次结果的一致性;此外,在多次迭代之后,可能会出现大的社区将小社区吞并的现象。结合以上内容,本文在LPA的基础上改进扩展出了两个算法,具体的研究成果如下所示:(1)LPA的优化改进LPA算法不包含任何参数,主要对标签传播及更新进行优化。在基于概率和相似度的标签传播算法 PSLPA(Probability and Similarity based Label Propagation Algorithm)中,结合节点间的概率以及相似度,并在标签传播的过程中使用了自适应标签选择的方式对节点标签进行更新。在基于节点权重和随机游走的标签传播算法WRWILPA(Weightand Random Walk based Label Propagation Algorithm)中,结合节点权重和随机游走提出了一种新的相似度计算方式,在标签传播过程中利用权重和相似度进行标签的更新。这两个算法在准确性以及稳定性上都有着很优秀的表现。(2)并行化对于上述的两个算法均实现了并行化。采用的是Spark平台下的GraphX模块。将算法流程转化为对网络图的迭代计算过程,通过现有的API接口对网络图进行转换操作。对于标签传播过程,实现了自定义的函数,来完成算法的并行化。并行化后的算法在不同规模的数据集上均表现出了高准确性以及高稳定性。