J4 ›› 2012, Vol. 39 ›› Issue (2): 175-180.doi: 10.3969/j.issn.1001-2400.2012.02.029

• 研究论文 • 上一篇    下一篇

特征向量的核方法检测网络社团结构

付立东1,2;高琳2   

  1. (1. 西安电子科技大学 计算机学院,陕西 西安  710071;
    2. 西安科技大学 计算机学院,陕西 西安  710054)
  • 收稿日期:2010-12-27 出版日期:2012-04-20 发布日期:2012-05-21
  • 通讯作者: 付立东
  • 作者简介:付立东(1973-),男,副教授,西安电子科技大学博士研究生,E-mail: fulidong2005@163.com.
  • 基金资助:

    国家自然科学基金重点资助项目(60933009);国家自然科学基金资助项目(61100157,61072103);西安科技大学培育基金资助项目(2010029)

Kernel k-means clustering algorithm for detecting communities  in complex networks based on eigenvector

FU Lidong1,2;GAO Lin1   

  1. (1. School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China;
    2. The School of Computer, Xi'an Univ. of Sci. and Tech., Xi'an  710054, China)
  • Received:2010-12-27 Online:2012-04-20 Published:2012-05-21
  • Contact: FU Lidong

摘要:

为在权重的复杂网络中检测社团结构,推广模块密度函数到权重形式,并优化权重形式的权重密度函数到谱分聚类形式及权重的核聚类形式.证明了基于权重密度的两类聚类方法在数学上的等价性,利用这种等价性,提出了一种新的基于特征向量核聚类检测复杂网络社团方法.实验结果表明,这种方法比直接的谱分方法或直接的核方法检测社团更加准确.

关键词: 社团结构, 模块密度, 核k-means, 谱分方法, 特征向量的核方法

Abstract:

To detect the community structure in weighted complex networks, the modularity density function D is generalized to weighted variants(WD) and shows how optimizing the weighted function WD can be formulated as a spectral clustering problem, and a weighted kernel k-means clustering problem. We also prove the equivalence of both clustering approaches based on WD in mathematics. Using the equivalence, we propose a new eigenvector-based kernel clustering algorithm to detect communities in complex networks. Experimental results indicate that it has better performance compared with either the direct kernel k-means algorithm or direct spectral clustering algorithm in terms of quality.

Key words: community structures, modularity density, kernel k-means method, spectral approach, eigenvector-based kernel approach

中图分类号: 

  • A