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

从Internet拓扑的幂律特征（度分布律）出发，定义了主干子图的相关概念，证明了主干子图的若干性质，并在此基础上给出了基于主干子图的聚类算法。该算法可应用于有幂律特征的大型图的混合布局，也可为幂律特征网络的研究提供参考。幂律特征图可以被分解为一个主干子图和多个子树。主干子图是一些度相对较高节点的集合；而子树则正好相反，幂律特征有效地保证了节点度分布的非均一特性。基于主干子图理论的图聚类算法可以分成两个步骤，即主干子图生成算法和桩树生成算法。主干子图Gs(Vs,Es)与原始图G(V,E)之间的同态等价关系

Power law graph clustering algorithm based on skeleton subgraph

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 G,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.