论文研究 基于主干子图的幂律特征图聚类算法.pdf

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