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

Fast Complex Network Clustering Algorithm Using Local Detection

作　　者：金弟[1,2] 刘大有[1,2] 杨博[1,2] 刘杰[1,2] 何东晓[1,2] 田野[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012

出　　处：《电子学报》2011年第11期2540-2546,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60773099;60703022;60873149;60973088);国家863项目(No.2006AA10Z245);模式识别国家重点实验室开放课题(No.09-1-1);中央高校基本科研业务费专项资金(No.200903177);复旦大学智能信息处理上海市重点实验室开放课题(No.IIPL-09-007)

摘　　要：目前复杂网络的规模越来越庞大,且呈现天然的分布式特性,因此从局部观点出发提出快速网络聚类算法就成为迫切需要.为解决这一问题,本文基于对网络模块性函数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.

关 键 词：复杂网络 网络聚类 簇结构 局部探测 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP391[自动化与计算机技术—控制科学与工程]