通信学报

• 学术论文 • 上一篇    下一篇

基于Laplace矩阵Jordan型的复杂网络聚类算法

牛建伟,戴 彬,童 超,霍冠英,彭 井   

  1. 北京航空航天大学 虚拟现实技术与系统国家重点实验室,北京 100191
  • 出版日期:2014-03-25 发布日期:2014-03-15
  • 基金资助:
    国家重点基础研究发展计划(“973”计划)基金资助项目(2013CB035503);国家自然科学基金资助项目(61170296,61190125);国家高技术研究发展计划(“863”计划)基金资助项目(2012BAH07B01, 2013BAH35F01);北京市自然科学基金资助项目(4123101)

Complex network clustering algorithm based on Jordan-form of Laplace-matrix

  • Online:2014-03-25 Published:2014-03-15

摘要: 在目前复杂网络聚类算法中,基于Laplace特征值的谱聚类方法具有严密的数学理论和较高的精度,但受限于该方法对簇结构数量、规模等先验知识的依赖,难以实际应用。针对这一问题,基于Laplace矩阵的Jordan型变换,提出了一种先验知识的自动获取方法,实现了基于Jordan矩阵特征向量的初始划分。基于Jordan型特征值定义了簇结构的模块化密度函数,并使用该函数和初始划分结果完成了高精度聚类算法。该算法在多个数据集中的实验结果表明,与目前主流的Fast-Newman算法、Girvan-Newman算法相比,基于Laplace矩阵Jordan型聚类算法在不依赖先验知识的情况下,实现了更高的聚类精度,验证了先验知识获取方法的有效性和合理性。

Abstract: Among existing clustering algorithms, the graph-Laplacian-based spectrum clustering algorithm has rigorous theoretical basis and high accuracy. However, the application of this algorithm is limited by its dependence on the prior knowledge, such as the number and the size of clusters. Based on the Jordan form of graph Laplacian, an algorithm was proposed which can obtain the prior knowledge, and perform the primary clustering based on the eigenvalues of the Jordan form. The modularity density function of clusters was defined, and an improved spectrum clustering algorithm with the help of the function and the primary clustering was proposed. The experiments were conducted on diverse datasets showing that, compared with the classic algorithms such as Fast-Newman and Girvan-Newman, the algorithm can reach a high clustering accuracy and a fast convergence rate.

No Suggested Reading articles found!