基于节点伪近邻的电路板近邻网络排序算法

曾佩佩 穆东旭 贾春宇

摘  要：
在运用近邻网络排序集生成边界扫描测试向量方法中，多以网络局部或全局信息进行节点近邻关系排序，导致伪近邻点的识别排序能力较差。该文结合LeaderRank算法引入节点伪近邻作为局部重要性指标，首先利用LeaderRank求得网络节点的全局重要度，然后基于相关邻居关系提出节点伪近邻比计算方法，最后综合LeaderRank的全局重要度值与节点伪近邻性求得总体重要度，从而获得近邻网络重要度排序。采用所提方法和以往近邻排序算法对实际电路板网络模型进行近邻关系排序，对排序结果进行比较，并用SIR传染病模型进行仿真分析。实验结果表明，所提方法能够弥补以往排序算法的不足，从而获得更为精确的排序结果。

关键词：
近邻网络排序; 节点伪近邻; LeaderRank; 重要度排序; SIR模型; 仿真分析

中图分类号：
TN710?34; TP301.6                文献标识码：
A                       文章编号：
1004?373X（2020）02?0005?04

Circuit board neighboring network sorting algorithm based on node pseudo?adjacency

ZENG Peipei1， MU Dongxu2， JIA Chunyu2

Abstract：
In the method of generating the boundary scan testing vector with the neighboring network sorting sets， the node adjacent relationship is sorted mostly according to the local or global network information， which results in poor recognition and sorting abilities of the pseudo?adjacent nodes. The pseudo?adjacency node is introduced as the local importance index by means of the LeaderRank algorithm. The global importance of the network node is obtained with the LeaderRank， and then the calculation method of the node pseudo?adjacency ratio is proposed based on the related neighboring relationship. The overall importance of the network node is acquired by synthesizing the global importance value of LeaderRank and the pseudo?adjacency property of nodes， so as to obtain the importance sorting of the neighboring networks. The neighboring relationship of the real circuit board network models is sorted by means of the method proposed in this paper and the previous neighboring sorting algorithm. The sorting results are compared， and the SIR infectious disease model is used for the simulation analysis. The experimental results show this method can make up for the shortcomings of the previous sorting algorithms， so as to obtain the more accurate sorting results.

Keywords：
neighboring network sorting; node pseudo?adjacency; LeaderRank; importance sorting; SIR model; simulation analysis

0  引  言

随着电路板的不断集成化，电路网络结构的复杂化，扫描测试难度也不断加大。在应用边界扫描技术对电路板进行相关测试时，难点在于如何生成紧凑性更好，完备性更高的测试向量。目前，主流的测试向量生成算法设计思想来源于1989年C.W.YAU和Jarwala提出的近邻网络排序集最大独立性算法。但由于无法有效获得准确的近邻排序网络集，所以只能在理论上探讨。随后有关学者相继提出了多种近邻网络排序算法，如Jarwala后来提出的基于近邻独立性的测试生成优化方法，该方法前提是已获得近邻网络排序集，然后根据近邻独立性对测试向量生成进行相关优化，并获得了较好效果。近年来，学者在网络重要节点近邻排序上提出了很多指标和算法，如基于电路板结构信息的近似近邻网络排序算法，该算法运用有限制短路故障模型[1?2]，根据网络间短路可能性大小，利用最短路径法得到该电路板网络结构的一个近似近邻排序网络集。但该方法不仅概率阈值难以确定，而且只从局部重要度指标考虑，排序结果并不理想。LeaderRank算法是对PageRank算法进一步优化，通过在原网络中加入背景节点，相当于PageRank中的跳转概率S，从而使得算法的收敛速度和鲁棒性有了明显提升，相比其他同类型近邻节点重要性排序方法，该方法更有优势[3?4]。

虽然上述方法能够较好地解决近邻网络排序问题，但多数只片面从节点的全局重要度或局部重要度上进行考虑，忽略了电路网络节点间相互作用对整个网络的影响，从而导致在复杂网络伪近邻节点排序不明确，不能获得更精确的网络排序集。为解决上述问题，本文在LeaderRank的基础上引入节点伪近邻性作为局部重要性指标，提出了基于节点伪近邻性的PseudoRank电路板近邻网络排序方法。首先结合相关邻居关系从局部表征节点伪近邻;然后将其扩展到全局，提出一种综合方法来获得节点的伪近邻比;最后结合LeaderRank算法求得节点的总体重要度值。该方法综合利用节点全局和局部重要性指标对节点进行近邻重要度评价，最终和其他几种经典算法进行比较，从实验结果可以看出，本文方法能够克服以往的不足，从而获得更为准确的近邻网络排序，实现测试向量的进一步优化。

1  PseudoRank近邻网络排序算法

1.1 LeaderRank算法

LeaderRank算法是在原网络基础上增加一个节点[vg]与其余所有[n]个节点相连，组成一个节点数为[n+1]的强连接网络。

定义1  [LRi]定义为节点[vi]的全局重要度。[LRi（k）]为经过[t]次迭代系统达到稳态后节点[vi]的重要度初值。随后，背景节点[g]将其重要度值平均分配给网络其他[n]个节点，从而得到节点[vi]的全局重要度。因此节点[vi]的最终的全局重要度[LRi]值为：

[LRi（0）=1nLRi（t）=j=0naijdjLRj（t-1） ， t=1，2，…LRi=LRi（t）+LRg（t）·n-1]      （1）

式中：[n]为网络节点总数;若节点[vi]，[vj]直接相连，则[aij=1]，否则为0;[dj]为节点[vj]的度值;[LRg（t）]为系统稳定状态下背景节点[vg]的重要度。

1.2  节点伪近邻性

在实际电路网络中，随着电路板的不断集成化，器件管脚、焊点、网络间距愈发密集，近邻网络间通常具有一定伪近邻关系。如图1所示，假定相连节点物理间距近似相等，由有限制短路故障模型理论[5]可知，相邻网络间短路的可能性相同。又由于节点1，2的一阶近邻度相同，均为4，故依据以往排序方法无法对两节点有效排序。然而，节点1，2二阶近邻度不同，节点C与F相连，致使C的重要性增加，从而使得节点1，2的重要度略有差异，即节点间存在伪近邻关系。

目前计算节点伪近邻相似性算法大致分为两种：一是局部节点近邻相似性算法，如文献[6?7]基于相关邻居关系的节点伪近邻度;二是全局节点近邻相似性算法，如文献[8?10]将网络结构局部特征信息扩展到全局来求解节点的伪近邻度。

本文综合全局和局部重要度，利用相关邻居关系从局部拓扑上来衡量节点伪近邻度，然后将其扩展到全局来求解节点伪近邻度。相关邻居关系计算方法如下：

[P（vi，vj）=N（vi）?N（vj）+E[N（vi）?N（vj）]]     （2）

式中：[N（vi）?N（vj）]为节点[i]，[j]间的共同邻居节点数;[E（G[N（vi）?N（vj）]）]为节点[i]，[j]共同邻居间的边数。

结合相关邻居关系计算方法，本文定义局部节点伪近邻比为：

[Lpse（vi，vj）=N（vi）?N（vj）+E [N（vi）?N（vj）]1+N（vi）?N（vj）+E [N（vi）?N（vj）]]

（3）

式中：
[N（vi）?N（vj）]为节点[i]，[j]的一阶共同邻居节点数;[E[N（vi）?N（vj）]]为节点[i]，[j]所有共同一阶邻居节点间的边数;[N（v1）?N（v2）]表示节点[i]，[j]非共同一阶邻居节点数;[E[N（v1）?N（v2）]]表示节点[i]，[j]非共同一阶邻居节点间的边数。如图1所示，[N（v1）?N（v2）=2]，[E[N（v1）?N（v2）]=1]，[N（v1）?N（v2）=4]，[E[N（v1）?N（v2）]=3]，所以节点1和节点1之间的局部相似性为[（1+2+1）（1+4+3）]=0.5。

对式（3） 进行推广，定义全局节点伪近邻比：[Gpse（vi，vj）=0，                                    i，j不可達k=1nLpse（vqk，vq（k+1）），   i，j非邻居但可达]  （4）

式中：[vq1=vi];[vq（n+1）=vj];[qk（k=1，2，…n）]为节点[i]到[j]的最短路径上所有节点集合。

从而得到本文中节点间伪近邻比：

[pse（vi，vj）=Lpse（vi，vj），      i，j相邻Gpse（vi，vj），     其他] （5）

定义2  PseudoRank矩阵[PseR]，节点[i]的[PR]重要度值如下：

[PRi=LRij∈αipse（vi，vj）+1ki+1LRj] （6）

式中，[αi]为节点[vj]的邻居节点集合。从式（6）可以看出，节点重要度与其邻居节点个数、邻居节点重要度值以及节点对间的相互影响力有关。

2  算法仿真与分析

2.1 节点重要性排序

对所提算法进行仿真与分析验证前，首先根据Protel DXP提供的电路板结构信息、网表信息建立短路故障网络模型。本文以某机载雷达信号处理板为样例建立短路故障模型[2]，如图2所示。

[6] BILAL S， ABDELOUAHAB M. Node similarity and modularity for finding communities in networks [J]. Physica a statistical mechanics & its applications， 2018， 492：
1958?1966.

[7] YANG Y， PEI J， AL?BARAKATI A. Measuring in?network node similarity based on neighborhoods：
a unified parametric approach [J]. Knowledge & information systems， 2017， 53（1）：
43?70.

[8] JOCIC M， PAP E， SZAK?L A， et al. Managing big data using fuzzy sets by directed graph node similarity [J]. Acta polytechnica hungarica， 2017， 14（2）：
183?200.

[9] MOLLGAARD Anders， ZETTLER Ingo， DAMMEYER Jesper， et al. Measure of node similarity in multilayer networks [J]. Plos one， 2016， 11（6）：
0157436.

[10] 蒲国民，郁滨，朱璇.一种基于邻居关系的ZigBee抗节点复制攻击方法[J].系统仿真学报，2014，26（5）：1026?1031.

[11] 单治超.有限随机图上的随机游动和传染病模型[J].数学进展，2017，46（1）：1?12.

[12] T?NSING C， TIMMER J， KREUTZ C. Profile likelihood?based analyses of infectious disease models [J]. Statistical methods in medical research， 2018， 27（1）：
44?46.

[13] RUI X， MENG F， WANG Z， et al. SPIR：
the potential spreaders involved sir model for information diffusion in social networks [J]. Physica a statistical mechanics & its applications， 2018， 506：
101?110.

[14] KUNIYA T， WANG J. Global dynamics of an SIR epidemic model with nonlocal diffusion [J]. Nonlinear analysis real world applications， 2018， 43：
262?282.

[15] YUAN X， WANG F， XUE Y， et al. Global stability of an SIR model with differential infectivity on complex networks [J]. Physica a statistical mechanics & its applications， 2018， 499：
162?168.

作者简介：曾佩佩（1988—），男，助理工程师，主要研究方向为图像处理、飞行控制系统、机载电子系统故障诊断。

穆东旭（1992—），男，硕士研究生，主要研究方向为机载电子系统可测试性技术、故障诊断。

贾春宇（1993—），男，硕士研究生，主要研究方向为机载电子系统可测试性技术、故障诊断。