电子学报 ›› 2013, Vol. 41 ›› Issue (12): 2346-2352.DOI: 10.3969/j.issn.0372-2112.2013.12.005

• 学术论文 • 上一篇    下一篇

基于合并分层聚类的网络拓扑推断算法

张润生, 李艳斌, 李啸天   

  1. 中国电子科技集团公司第五十四研究所, 河北石家庄 050081
  • 收稿日期:2012-11-23 修回日期:2013-03-07 出版日期:2013-12-25 发布日期:2013-12-25
  • 作者简介:张润生 男,1984年生于河北保定,现为中国电子科技集团公司第54研究所博士研究生.主要研究方向为网络测量、网络拓扑推断. E-mail:zhang-runsheng@163.com李艳斌 男,1966年生于河北石家庄,现为中国电子科技集团公司首席专家,博士生导师.主要研究方向为电子对抗总体技术.李啸天 男,1986年生于河北石家庄,现为中国电子科技集团公司第54研究所博士研究生.主要研究方向为纠错码盲识别、网络测量.
  • 基金资助:

    国家科技支撑计划(No.2011BAH24B04);中国博士后科学基金(No.20110490989)

Agglomerative Hierarchical Clustering Based Algorithm for Network Topology Inference

ZHANG Run-sheng, LI Yan-bin, LI Xiao-tian   

  1. The 54th Research Institute of CETC, Shijiazhuang, Hebei 050081, China
  • Received:2012-11-23 Revised:2013-03-07 Online:2013-12-25 Published:2013-12-25

摘要: 针对HTE(Hierarchical Topology Estimation)算法计算复杂度较高的问题及其在节点相关性估计方差较大条件下性能下降的问题,提出基于合并分层聚类的网络拓扑推断算法.该算法采用自底向上的合并分层聚类,每次聚类仅使用与最大相关节点对有关的数据,相对HTE算法降低了运算复杂度;建立了改进的有限混合模型,增加了参数推断的有效数据,提高了算法的参数估计精度.仿真结果表明相对HTE算法,本文方法可以更快地推断出网络拓扑,且在节点相关性估计方差较大条件下,有更高的拓扑推断精度.

关键词: 拓扑推断, 分层聚类, 有限混合模型, 期望最大化

Abstract: Considering the high complexity of HTE(Hierarchical Topology Estimation)and its performance degradation under the condition of large correlation estimation variance,a method based on agglomerative hierarchical lustering is proposed.The method employs bottom-up agglomerative hierarchical clustering,which only uses the data related to the node pair with the largest correlation,so it has lower computation complexity than HTE.A modified finite mixture model is established,increasing the amount of effective data,which improves the accuracy of parameter estimation.The simulation demonstrates that the proposed method infers the topology more rapidly,with higher accuracy when the correlation estimation variance is large.

Key words: topology inference, hierarchical clustering, finite mixture model, expectation maximization

中图分类号: