翟镇新 於跃成 谷 雨 景道月

（江苏科技大学计算机学院 镇江 212003）

1 引言

随着互联网技术的发展和社会网络规模的不断扩大，人与人之间的交流形式发生了巨大变化，人们获取的信息量也呈爆炸式增长。社会网络具有信息大、无标识、社区结构等特性，其中社区结构是社会网络的基本性质。所谓社区结构是指一个网络可以分为若干个社区，社区内节点相似度较高且连接相对紧密，社区间节点相似度较低且相对稀疏。社区发现可用于社交平台用户群组的发现，以实现相关商业广告的投放；通过社区发现并挖掘群组的最新讨论话题，可以向用户更好地推荐感兴趣的话题。

为了能够实现社区的有效划分，基于随机游走的方法［1］、基于模块度优化的方法［2～3］以及基于图分割的方法［4～5］被相继提出。这些方法主要依据网络结构进行划分，当应用于数据规模较大的社会网络时，便会面临迭代周期较长，算法复杂度较高等一系列问题。

2007 年，KUMARA 等学者［6］首次在面对非常繁琐的社会网络时，尝试将标签传播模型（Label Propagation Algorithm，LPA）运用其中做社区发现的研究。实验结果表明，使用LPA模型的社区发现时间效率等方面指标都有了巨大的突破。该算法模型不需要提前知道真实的社区个数有多少，仅依赖于社会网络的自身结构。LPA 算法复杂度较低，被广泛应用于大规模社会网络的社区发现。

然而，LPA 在每次的迭代过程中存在着随机性，致使每次社区发现的结果都不一致。造成LPA算法稳定性较差和随机性较高的主要原因在于该算法没有充分考虑节点自身的影响力，网络中所有节点均被平等看待。……