基于非参数假设检验的拓扑推断算法

Topology Inference Algorithm Based on Nonparametric Hypothesis Test

针对基于门限比较的二叉树修剪拓扑推断算法稳健性差的问题,提出了一种基于非参数假设检验的网络拓扑推断算法。该算法首先应用经典的二叉树拓扑推断算法获得树状网络的二叉树结构,然后应用维尔科克森秩和检验算法逐个判断二叉树中的每条内部链路是否需要修剪,最后修剪二叉树,删除所有需要修剪的内部链路,得到真实的树状拓扑。由于该算法使用统计检测的方法,无需设置门限,相对门限比较法具有更好的稳健性。仿真实验表明,该算法相比基于门限的二叉树修剪算法具有更高的推断精度。

In order to improve the robustness of binary tree pruning based topology inference algorithm, a topology inference algorithm based on nonparametric hypothesis test is proposed. In this method, the binary tree is obtained by using classical binary tree inference algorithm; wilcoxon rank sum test method is applied to test which internal nodes should be removed; and finally all the internal nodes which should be removed are deleted to generate the real topology. Simulation results show that the algorithm can get higher topology inference accuracy than the method based on threshold comparison.