基于主干子图的幂律特征图聚类算法  

Power-law graph clustering algorithm based on skeleton subgraph

作　　者：张伟明[1] 张凯[1] 王清贤[1] 

机构地区：[1]解放军信息工程大学信息工程学院网络工程系,郑州450002

出　　处：《计算机应用研究》2008年第9期2610-2612,共3页Application Research of Computers

基　　金：国家"863"计划资助项目(20031AA146010)

摘　　要：从Internet拓扑的幂律特征(度分布律)出发,定义了主干子图的相关概念,证明了主干子图的若干性质,并在此基础上给出了基于主干子图的聚类算法。该算法可应用于有幂律特征的大型图的混合布局,也可为幂律特征网络的研究提供参考。幂律特征图可以被分解为一个主干子图和多个子树。主干子图是一些度相对较高节点的集合;而子树则正好相反,幂律特征有效地保证了节点度分布的非均一特性。基于主干子图理论的图聚类算法可以分成两个步骤,即主干子图生成算法和桩树生成算法。主干子图Gs(Vs,Es)与原始图G(V,E)之间的同态等价关系保证了Gs继承了G的众多特性,进而保证了该算法可以被很好地应用于大型幂律特征图的混合布局。Power-law graph can be segmented into a skeleton graph and several sub trees with recursively hung vertexes filetering. Skeleton sub-graph is a set of relatively important vertexes with high degree, sub trees are just in the opposite situation. Power-law characteristic guarantees the non-uniform distribution of nodes＇ degree. Based on this characteristic,this paper defined some related concepts of skeleton graph. The clustering algorithm based on skeleton sub-graph could be divided into two parts：skeleton sub-graph generation algorithm and stub tree growing algorithm. The homomorphically equivalence between skeleton sub-graph Gs （ Vs, Es ） and original graph G （ V, E） guaranteed Gs inheriented most characteristics from Gs which ensured this clustering algorithm could be applied to the hybrid layout of large graph with power-law characteristic. Meanwhile, it could also supply certain reference to the research of power-law network.

关 键 词：绘图 主干子图 聚类 幂律 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]