Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (35): 86-89.DOI: 10.3778/j.issn.1002-8331.2010.35.025

• 网络、通信、安全 • Previous Articles     Next Articles

Improving CNM algorithm to detect community structures of weighted network

HAN Hua,WANG Juan,WANG Hui   

  1. Department of Science,Wuhan University of Technology,Wuhan 430070,China
  • Received:2010-05-20 Revised:2010-07-26 Online:2010-12-11 Published:2010-12-11
  • Contact: HAN Hua


韩 华,王 娟,王 慧   

  1. 武汉理工大学 理学院,武汉 430070
  • 通讯作者: 韩 华

Abstract: For detecting community structures on weighted network that can reflect the important properties of the network structure,this paper chooses the hierarchical clustering methods that have been widely used in community structure,and improves CNM algorithm.The new algorithm introduces the link weight and vertex weight,defines a new Q-function to calculate the community modularity.The type of communities are classified by finding the Q peak.When being tested on the weighted network with the stock price fluctuation of correlation for link weigh,the community division results show that the improved CNM algorithm is effective.And a comparative analysis is maken with the improved GN algorithms,global optimization algorithms on the same network of detecting community structures.The improved CNM algorithm demonstrates excellent detection results,the accuracy of classification and very fast process performance.

Key words: weighted network, community structure, community modularity, improved CNM algorithm

摘要: 为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法(CNM算法)。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。

关键词: 加权网络, 社团结构, 社团模块度, 改进的CNM算法

CLC Number: