计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (25): 149-153.

• 数据库、信号与信息处理 • 上一篇    下一篇

微分方程在复杂网络社团发现中的研究

肖自红   

  1. 湖南警察学院 信息技术系,长沙 410138
  • 出版日期:2012-09-01 发布日期:2012-08-30

Research on difference equation in community-finding of complex network

XIAO Zihong   

  1. Department of Information Technology, Hunan Police Academy, Changsha 410138, China
  • Online:2012-09-01 Published:2012-08-30

摘要: 理解复杂网络的关键在于迅速精确地发现网络中的社团结构。基于图理论的谱聚类算法是一种有效并全局收敛的优秀社团发现算法,其计算量集中于特征值和特征向量的计算。结合常系数线性常微分方程的解与系数矩阵特征值的关系,提出了基于微分方程的谱聚类社团发现算法(AMCF和LMCF);这两种算法避免了矩阵的特征值和特征向量的复杂计算过程,为社团发现算法提供了新的思路。理论分析和实验验证了算法的有效性。

关键词: 微分方程, 社团结构, 谱聚类

Abstract: Rapid and accurate community-finding of complex network is very important for people to understand the character of entire network. Spectral clustering algorithm is an effective and global convergent community-finding algorithm, the computation complexity lies in calculating eigenvalue and eigenvector. Combined with the advantage of solving the eigenvalues and eigenvector of linear homogeneous differential equations with constant coefficients, this paper proposes two community-finding algorithms based on spectral clustering and difference equation, which avoid the complex computation. The theoretical analysis and experimental verification show the effectiveness of these algorithms.

Key words: difference equation, community structure, spectral clustering