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

• 作者: 张伟明 张凯 王清贤
• 来源期刊: 计算机应用研究
• 关键词: 绘图 主干子图 聚类 幂律
• 年，卷（期）: 2008,（9）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2610-2612
• 页数: 3页
• 分类号: TP393.08
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2008.09.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王清贤	解放军信息工程大学信息工程学院网络工程系	44	268	9.0	15.0
2	张凯	解放军信息工程大学信息工程学院网络工程系	2	7	1.0	2.0
3	张伟明	解放军信息工程大学信息工程学院网络工程系	3	69	2.0	3.0