论文部分内容阅读
现代网络科学的研究和发展,提高了我们对复杂网络的认识。真实世界的复杂网络常常可以表示成图的形式,其最重要特征是社区结构,社区内部节点之间连接紧密,不同社区之间的节点连接相对稀疏。如何确定复杂系统中的社区结构,形成了数据挖掘领域的一个重要的研究课题——社区发现技术。基于复杂网络的特性,本文提出局部中心点的概念,研究局部中心点在真实网络和合成网络中的分布,分析局部中心点作为社区“核心”节点对社区发现的作用,基于局部中心点,提出两种社区发现算法。算法一首先找到网络中的局部中心点,以局部中心点为起始节点扩展进行社区,各个局部社区的扩展可以并行进行,快速找到各个以局部中心点为“核心”的社区。算法二也是首先找到网络中的局部中心点,通过建立基于模块度矩阵的特征向量矩阵,计算局部中心点和其他节点在特征向量矩阵中的关联性,从而形成以局部中心点为“核心”的社区。这两种算法对于网络中没有隶属任何社区的剩余节点集,采用迭代局部中心点,重新进行扩展和计算关联性,并形成社区,重复该过程直到社区个数不再增加为止。本文在31个复杂网络数据集上进行实验,使用调整Omega指标(AOI)和重叠模块度(Qov)分别评估发现社区的准确性及合理性,结果表明,在一些网络中,相对其他算法,这两种算法都提高了社区发现的合理性,发现社区的个数更接近实际网络中的社区个数并可发现有重叠的社区。算法一提高大规模网络的社区发现的效率,而且其准确性也不逊色于其他算法,算法二提升了社区准确性,其效率依赖于特征矩阵的计算。