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

作     者：金弟 刘大有 杨博 刘杰 何东晓 田野 JIN Di;LIU Da-you;YANG Bo;LIU Jie;HE Dong-xiao;TIAN Ye

作者机构：吉林大学计算机科学与技术学院吉林长春130012 吉林大学符号计算与知识工程教育部重点实验室吉林长春130012 

出 版 物：《电子学报》 (Acta Electronica Sinica)

年 卷 期：2011年第39卷第11期

页      面：2540-2546页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(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进行测试,实验表明,该算法的运行效率和聚类质量都要明显优于当前的一些优秀网络聚类算法.