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

Fast Complex Network Clustering Algorithm Using Local Detection

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

Recently,complex networks are always very huge and take on distributed nature.Therefore it is gradually becoming instant requirement to propose fast network clustering algorithms in the sight of local view.For the problem,this paper deduces a local objective function f aiming to each node in the network,which is based on the profound analysis on network modularity function Q,and proves that Q is monotone increasing with function f of any node,and then proposes a fast network clustering algorithm（FNCA） by using local optimization.In this algorithm,each node optimizes its own objective function f by only local information,and all the nodes collectively optimize function Q to detect network community structure.Both efficiency and effectiveness of algorithm FNCA are tested against computer-generated and real-world networks.Experimental result shows that this algorithm is better than some excellent network clustering algorithms in term of these two respects.