互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 张伟明 张 凯 王清贤

  摘 要:从Internet拓扑的幂律特征(度分布律)出发,定义了主干子图的相关概念,证明了主干子图的若干性质,并在此基础上给出了基于主干子图的聚类算法。该算法可应用于有幂律特征的大型图的混合布局,也可为幂律特征网络的研究提供参考。幂律特征图可以被分解为一个主干子图和多个子树。主干子图是一些度相对较高节点的集合;而子树则正好相反,幂律特征有效地保证了节点度分布的非均一特性。基于主干子图理论的图聚类算法可以分成两个步骤,即主干子图生成算法和桩树生成算法。主干子图与原始图G(V,E)之间的同态等价关系保证了继承了的众多特性,进而保证了该算法可以被很好地应用于大型幂律特征图的混合布局。
  关键词:绘图;主干子图;聚类;幂律
  中图分类号:TP393.08 文献标志码:A
   文章编号:1001-3695(2008)09-2610-03
  
  Powerlaw graph clustering algorithm based on skeleton subgraph
  ZHANG Weiming,ZHANG Kai,WANG Qingxian
  (Dept. of Network Engineering,Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002,China)
  Abstract: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 Gs(V,Etics 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. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017