基于标签传播的实时社区发现算法研究

随着互联网的快速发展和Web2.0网站的兴起,对社区结构的挖掘成为了网络分析中的研究热点。社区发现对于深入了解网络的内部结构和深层特性有着重要意义,网络总是在变化的,对实时变化的网络进行实时性的社区发现对于揭示网络动态特性也有着重要的意义。在对单个静态的社会网络进行社区发现的静态社区发现研究已经产生了很多有效算法,但大部分都无法快速而准确的发现高质量社区,更加无法应用到实时社区发现中。 标签传播算法是一种快速简单但存在着准确性和随机性等缺点的社区发现算法,其在标签更新上的局部性可以很好的应用于实时社区发现。本文在其基础上提出了一种基于社区核心的标签传播算法,通过借助社区核心给网络图中的节点赋予一定的权重和改善标签的更新策略与传播策略对原始标签传播算法进行改进,从而在保持算法效率的基础上提高了算法的准确性和稳定性。而后将基于社区核心的标签传播算法应用于实时社区发现,在网络每次实时变化后动态改变节点的权重和社区核心集合,然后对发生改变的节点的标签进行局部更新,从而在满足实时性的要求的同时获得更加准确的实时社区发现结果。 实验结果表明,本文提出的算法在静态社区发现和实时社区发现中都能够快速并准确的得到高质量的社区划分,并且在时间效率和准确度两方面都能够达到一个理想的效果。