改进的CNM算法对加权网络社团结构的划分  

Improving CNM algorithm to detect community structures of weighted network

作　　者：韩华[1] 王娟[1] 王慧[1] 

机构地区：[1]武汉理工大学理学院,武汉430070

出　　处：《计算机工程与应用》2010年第35期86-89,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.70971103)~~

摘　　要：为了对可以反映网络结构局部重要性质的加权网络进行社团结构划分,延续广泛应用的社团结构分级聚类方法,改进Newman贪婪算法(CNM算法)。算法设计中引入点权和边权,并重新定义新的Q函数计算社团模块度,通过寻找Q函数峰值确定社团划分的最终结果。另外以股票价格波动相关性为加权边建立的加权网络为例进行算法检验,社团划分的结果验证了改进的CNM算法的有效性。与改进的GN算法、极值优化算法等划分效果进行比较分析后发现,改进算法在划分准确性及算法复杂度等方面都有明显的优势。For detecting community structures on weighted network that can reflect the important properties of the network structuret,his paper chooses the hierarchical clustering methods that have been widely used in community structure,and im-proves CNM algorithm.The new algorithm introduces the link weight and vertex weight,defines a new Q-function to calcu-late 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 weight,he community division results show that the improved CNM algorithm is effective.And a comparative analysis is maken with the improved GN algorithms,global optimi-zation algorithms on the same network of detecting community structures.The improved CNM algorithm demonstrates excel-lent detection resultst,he accuracy of classification and very fast process performance.

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

分 类 号：O24[理学—计算数学]