基于局部探测的快速复杂网络聚类算法

目前复杂网络的规模越来越庞大,且呈现天然的分布式特性,因此从局部观点出发提出快速网络聚类算法就成为迫切需要.为解决这一问题,本文基于对网络模块性函数Q的分析,推导出一个针对于单个结点的局部目标函数f,并证明Q函数随网络中任一结点的f函数呈单调递增趋势,进而提出一个基于局部优化的近线性网络聚类算法FNCA.在该算法中,每个结点仅利用网络的局部簇结构信息来优化自身的目标函数f,所有结点通过相互协同来实现对整个网络的聚类.通过计算机生成网络和真实网络对算法FNCA进行测试,实验表明,该算法的运行效率和聚类质量都要明显优于当前的一些优秀网络聚类算法.