一种用于识别通信网络中模糊冗余节点身份的方法

摘要

本发明属于复杂网络的结构研究领域，具体涉及一种用于识别通信网络中模糊冗余节点身份的方法。该方法包括步骤如下，获取通信网络数据，将通信网络数据先区分出已知确定部分和模糊不确定部分，对于获取到的通信信息中出现过的发送方、接收方以及可能因为信息丢失而空缺或者不明确的发送方、接收方都分别用一个占位符表示，构建一个初步连接关系图，然后依据这些占位符的属性和在连接关系图中的拓扑特征，采用谱聚类算法对这些占位符进行聚类，确定哪些占位符实际上表示同一个节点，将聚类到同一组中的占位符合并成一个通信节点，从而达到识别并去除模糊、冗余节点的目标，实现通信网络的重构。

说明书

技术领域

本发明属于复杂网络的结构研究领域，具体涉及一种用于识别通信网 络中模糊冗余节点身份的方法，适用于通信网络中网络拓扑结构的还原、 去噪问题。

背景技术

对于通信网络拓扑结构的重构是通过对获取到的不完整甚至含有噪声 的通信数据进行分析，从而还原出尽可能接近真实的网络结构。通信网络 重构问题包含三个方面：缺失链路的还原；缺失、隐藏的通信节点的还原； 以及身份模糊、冗余节点的辨别和去除。本文针对第三个方面，即通信网 络中模糊节点的识别问题进行研究。

在信息爆炸的时代，特别是复杂电磁环境下，因为干扰、伪装等手段 的运用，我们获取到的通信信息中难免存在信息的缺失、遗漏、甚至错误， 还会有大量的冗余噪声，例如我们获取到的通信信息格式通常为：[通信时 间，发送方，接收方，数据包大小]，但是因为干扰、噪声等因素，可能会 造成数据包丢包、串线、发送方接收方不明确或者错误等情况。部分通信 数据可能丢失或损坏，使得接收方获取的通信数据的数据源可能存在错误， 原本从同一点发出的多条通信可能被误认为从两个甚至多个不同节点发 出。这使得接收点无法准确判断期望通信源的状态等。如果一个通信网络 中有多个节点存在此问题，则会在网络中产生大量的模糊点，整个网络的 通信会因此受到影响。若不能分辨清这些模糊节点的源节点(模糊节点本 应代表的节点)，网络的通信效率和准确率都会受到影响。为了维持通信 网络的稳定性，必须对模糊节点进行辨别，将通信网络中节点间的关联情 况尽可能恢复到理想状态。

目前国内外关于复杂网络拓扑结构的重构问题已经进行了一些研究， 主要集中在缺失链路预测方面，关于网络中节点信息的相关的研究才刚刚 起步。现有的少量关于通信网络中节点信息的研究只涉及到缺失节点的预 测，主要有两种思路：

第一种是从网络重构的角度同时预测缺失节点和连边。如Leskovec等 [1]结合期望最大框架和Kronecker图模型，提出KronEM算法，首先用观 察到的网络来估计模型参数，然后用模型预测缺失部分，再用预测的网络 结构估计模型参数，如此迭代，直到参数收敛。

第二种是直接预测缺失节点，Wen-XuWang等人[2]利用压缩感知在基 于博弈论的网络中进行网络重构，认为重构出现异常的点与某隐含的点相 连，从而预测缺失点在网络中的位置。作者首先在网络中定义一种博弈机 制，个体有两种选择，合作或者背叛(S＝{cooperation,Defense})，采用 Fermi规则模拟个体的策略更新。压缩感知最初是用在信号恢复中，通过 获取到的稀疏信号的部分数据还原出完整信号。对于基于博弈论的演化网 络，经过多轮博弈，因为链接概率矩阵是一个稀疏矩阵，符合压缩感知定 义，根据个体每轮的策略和获取到的收益以及链接矩阵的关系，就化成类 似Y＝Φ·X的形式，Y表示测量值，Φ表示测量矩阵，X表示真实信号。最后 得到的链接概率矩阵中，如果概率接近1就认为有边相连，接近0就认为 没有边相连。作者设定的阈值是0.1。对于多轮博弈，理论上每次用压缩 感知重构出的链接概率矩阵应该是一样的，因为文中的博弈机制不改变网 络链接情况，但是如果某几个节点的连接情况在每一轮并不一样并且与网 络本身拓扑特征不相符，就可判定这几个异常点与缺失点相连，从而确定 缺失点在网络中的位置。

J.P.Bagrow等人[3]从网络上的动力学行为出发，对于固定的网络结 构，模拟仿真网络上的信息流通情况，然后用预测算法预测经过每个节点 的信息流通速度判定信息流通速度，判定出现异常的点为缺失点的邻居， 从而确定缺失点在网络中的位置。

现有技术虽然能够对通信网络中缺失节点进行初步的判定，但是 Leskovec的算法计算复杂度特别高，在现实网络中并不适用，压缩感知的 方法只适用于演化机制已知的网络，J.P.Bagrow等人的算法较理想化， 只能在仿真数据集上进行实验。上述三个算法都只是初步分析网络中可能 的缺失隐含节点，而没有对网络中可能的冗余节点、模糊节点进行分析和 识别。

文中参考文献：

[1]M.Kim,J.Leskovec.TheNetworkCompletionProblem:InferringMissingNodesand EdgesinNetworks.SIAMInternationalConferenceonDataMining(SDM)2011.

[2]Wen-XuWang,Ying-ChengLai,CelsoGrebogi,andJiepingYe.Network ReconstructionBasedonEvolutionary-GameDataviaCompressiveSensing. PHYSICALREVIEWX1,021021(2011).

[3]J.P.Bagrow,S.Desu,M.R.Frank,N.Manukyan,L.Mitchell,A.Reagan,E.E. Bloedorn,L.B.Booker,L.K.Branting,M.J.Smith,B.F.Tivnan,C.M.Danforth,P.S. Dodds,andJ.C.Bongard,Shadownetworks:Discoveringhiddennodeswithmodelsof informationflow.InProceedingsofCoRR.2013.

发明内容

针对通信网络中因为干扰、噪声等因素可能出现的数据包丢包、串线、 发送方接收方不明确或者错误等情况造成的模糊节点、冗余节点进行识别， 本发明使得重构出的通信网络拓扑接近其真实结构。具体技术方案如下：

一种用于识别通信网络中模糊冗余节点身份的方法，包括以下步骤：

(1)获取通信网络数据，将通信网络数据先区分出已知确定部分 G_k＝<V_k,E_k>和模糊不确定部分，将每个不确定节点用一个占位符表示；构建 一个初步连接关系图G_a＝<V_a,E_a>，其中，<V_a,E_a>、<V_k,E_k>分别对应连接关 系图G_a、G_k中所包含的节点集合和连边集合，计算占位符数目|V_p|＝|V_a|-|V_k|； V_k表示已知确定节点，V_p表示占位符，即不确定的模糊节点，V_a表示全部节 点；

(2)采用高斯距离计算方法，计算初步连接关系图G_a中的所有节点之 间的关联矩阵其中|V_a|为节点集合V_a中的元素数目；表示实数 域，表示实数域上|V_a|行、|V_a|列矩阵的集合。

(3)定义为对角矩阵，其中，对角元素D_ii为关联矩阵C的第 i行元素之和，i＝1,..,|V_a|，由建立相应的矩阵其中表示对角矩阵D的每个元素取平方根的倒数；

(4)假定模糊节点本应该代表的源节点数目是已知的，记为h，找到 h个L的最大特征向量，组成矩阵其中L的h个特征向量分别为Q的 列；

(5)标准化矩阵Q使每行为单位长度，记为矩阵Q′；

(6)去掉矩阵Q′中对应已知确定节点的行，保留矩阵中对应占位符的 行，得到矩阵此时，矩阵Q″中每一行对应一个占位符；

(7)把Q″中的行采用k-mediods方法聚类成h个类；

(8)将同一个类中的占位符合并成一个节点，合并成的节点与该类中 的占位符原来的邻居相连。

进一步地，所述步骤(2)中采用高斯距离计算方法关联矩阵的过程如下：

定义d_i为初步连接关系图G_a中节点i到其他所有节点的最短路径长度 的向量，则

$C_{ij}=e^{\frac{-\left|\right|d_i-d_j|{|}^2}{2{\sigma }^2}}$

参数σ是高斯距离公式的标准差，||·||表示求向量的模运算，e表示 数学常数，即自然对数的底数，C_ij表示矩阵C中对应的第i行第j列位置的 元素。因为σ越大灵敏度越低(网络增减一条边对节点间高斯距离影响越 小)，σ越小灵敏度越高，取值在3-5之间时区分度较好(实施例中σ一般 取值为4)。

采用本发明获得的有益效果：本发明用于通信网络中数据缺失造成的 网络拓扑结构重构不完整不准确的问题，对通信网络中的模糊节点进行辨 别和合并，以尽可能使得重构出的通信网络拓扑接近其真实结构，目前国 内外还没有对于识别通信网络中模糊冗余节点问题相关的研究，通过实验 测试本发明对于模糊冗余节点的身份识别能够达到较高的准确率(75％以 上)。通过本发明对于模糊冗余节点的识别和合并，能够提高通信网络拓扑 结构重构的准确度，为进一步在通信网络上进行网络层次分析、通信流程 分析、业务流程分析等提供可靠数据支撑。

附图说明

图1为正确的通信网络图与含有模糊冗余节点通信网络图对比示意图；

图2为聚类效果示意图；

图3为本发明方法流程图；

图4为仿真网络原始图；

图5为仿真数据集拆分后网络图；

图6为公开网络数据集Football原始网络图。

具体实施方式

下面，结合附图和具体实施例对本发明作进一步说明。

本发明对于通信网络中模糊冗余节点识别问题的基本思路是，除去一 部分确定的节点外，对于获取到的通信信息中出现过的发送方、接收方以 及可能因为信息丢失而空缺或者不明确的发送方、接收方都分别用一个占 位符表示，构建一个初步连接关系图，然后依据这些占位符的属性和在连 接关系图中的拓扑特征，采用谱聚类算法对这些占位符进行聚类，确定哪 些占位符实际上表示同一个节点，将聚类到同一组中的占位符合并成一个 通信节点，从而达到识别并去除模糊、冗余节点的目标，实现通信网络的 重构。

在通过获取到的通信数据对通信网络本来的结构进行还原的过程中， 因为噪声、干扰等因素，造成通信数据的不完整甚至错误，构建出的网络 中难免存在一些不确定节点，可能被误认成多个冗余节点，如图1所示， 图(a)表示正确的通信网络图，图(b)表示网络中含有模糊冗余节点示 意图，图中的6号、7号节点为模糊冗余节点，通过本发明中的算法对这 些冗余不确定节点进行聚类，识别出其真实的身份，如图2所示，从而还 原出尽可能接近真实的通信网络拓扑结构。

下面首先对数据的采集过程进行说明。采用仿真数据集和真实社交网 络数据集共同验证算法有效性。验证的思路是从仿真数据和公开数据集中 随机选择一部分节点将其拆分成多个节点(即：冗余节点)，如果算法能 够将拆分后的节点识别出其原来对应的节点，则证明算法有效。对于获取 的子图，从全部节点中随机选取ξ个节点作为实验点集合V_m，V_m是模糊节 点本应该代表的源节点，然后将这ξ个点分别拆分成若干个，构成模糊节 点集，用占位符v′∈V_p代替，V_p表示占位符集，这就构成了初步连接关系图 G_a。这样拆分出来的节点若干个其实表示一个源节点，拆分出来的都用占 位符表示，整个数据集处理过程就是数据集构造过程，构造出一个用于实 施例的训练集。算法的目的是把拆分出来的占位符(即模糊冗余节点)给 聚类回去，找出哪几个模糊节点实际上是表示同一个源节点。

用Matlab仿真生成BA无标度网络，生成规则为BA(m0,m,N,pp)，其 中m0为增长前的网络节点个数，m为每次引入新节点时新生成的边数，N 为增长后的网络规模，pp为初始网络情况，pp的取值有1,2,3三种，其中1 表示都是孤立；2表示构成完全图；3表示随机连接一些边。分别设置不同 参数生成两个无标度网络，如图4所示，图(a)为网络1对应参数BA (4,3,100,2)；图(b)为网络2对应参数BA(10,6,100,3)。

实验中分别在两个网络中随机选取三个点作为实验点，网络1中选取的 为9、19、57号三个节点，网络2中为69、87、93号三个节点。假设在该网 络上进行的通信信息传递具有噪声，这几个节点进行的通信存在信息丢失， 从而造成这几个节点在网络结构中没有出现，在进行数据收集时被标记为 多个不同的身份，本发明提出的算法就是将网络中不确定的节点进行识别， 还原出真实的网络节点。

在这两个网络中分别找到三个实验节点的最近邻居,然后将实验节点 分别进行拆分，对应关系下表所示。

表1仿真数据中实验节点对应关系

拆分后的网络图如图5所示，拆分后的节点分别与原实验节点的邻居 相连，每个新点保留原实验节点一半数目的连边，初步连接关系图G_a。

公开数据集为Football网络，该数据集记录了1998年参加世界杯的22 个足球队成员在35个国家之间的签约情况，网络中的连边表示某个成员从 一个国家输出到另一个国家。将该数据集看作是无权无向网络，包含35个 节点，118条边。初始网络连接图如图6所示。从中任意选取3号、14号、 16号三个节点作为实验节点，分别将这三个节点进行拆分，每个节点拆分 成四份，拆分后节点与原节点对应关系如表2所示。

表2Football数据集实验节点对应关系

如图3所示，为本发明流程图；具体实施例一，以Football网络数据 集为例(实验中σ取4)：

(1)对于构造好的实验数据集，首先区分出已知确定部分G_k＝<V_k,E_k>和 模糊不确定部分，其中原网络中35个节点中除了3、14、16号节点(这3个 节点组成集合V_m)以外的32个节点组成已知确定部分V_k，拆分出的36至47 号一共12个节点为模糊冗余节点V_p，每个模糊冗余节点作为1个占位符，构 建初步连接关系图G_a＝<V_a,E_a>，<V_a,E_a>分别为连接关系图G_a所包含的节点 集合和连边集合，V_a是已知确定节点V_k和模糊冗余节点V_p的并集，E_a表示V_a中节点之间的连接关系；

(2)采用高斯距离计算方法，计算初步连接关系图G_a中的所有节点之 间的关联矩阵其中44为集合V_a中的元素个数，也就是G_a中包含 的节点数；

(3)对角元素D_ii(i＝1,..,44)为关联矩阵C的第i行元素之和，由 建立相应的矩阵

(4)模糊节点本应该代表的源节点数目h＝3，找到3个L的最大特征向 量(对重复特征值找垂直的特征向量)，组成矩阵其中L的3个特 征向量分别为Q的列；

(5)标准化Q矩阵使每行为单位长度，记为Q′；

(6)去掉Q′矩阵中对应已知确定节点的行(算法是按照节点编号将每 个节点对应矩阵的一行，比如节点i对应第i行，本实施例中是对应前32行； 保留矩阵中对应占位符的行，本实施例中是矩阵的最后12行)，得到矩阵 此时，Q″矩阵中每一行对应一个占位符；

(7)把Q″中的12个行采用k-mediods方法(一种现有的样本聚类方法) 聚类成3个类，也就是对36号至47号这12个占位符进行聚类，聚类结果为：

表3占位符聚类结果

36 38 39 43 47 37 40 41 42 44 45 46

(8)将同一个类中的占位符合并成一个节点，与该类中的占位符原来 的邻居相连。聚类得到的结果，也就是聚类得到的源节点与模糊冗余节点 的对应关系如下表：

表4实验节点对应关系

节点编号 36 38 39 43 47 37 40 41 42 44 45 46 得到对应源节点编号 3 14 16

聚类的正确率为9/12＝0.75，从结果可以看出说明该算法能够有效识别 出网络中冗余不确定节点的真实身份。

具体实施例二，按照本发明的步骤用仿真数据进行实验。采用本发明 中的算法对仿真得到的两个网络中的不确定节点进行分析，聚类结果如下 表：

表5仿真数据预测结果

节点编号 101 102 103 104 105 106 107 108 109 110 正确率 网络1 9 57 19 9 57 57 57 57 19 19 0.8 网络2 69 69 69 69 93 93 87 87 87 87 1

表中第二列、第三列分别为聚类后模糊冗余节点对应的分组，也就是 对应原网络中的实验节点，可以看出，对于网络1，算法预测正确率达到 0.8，网络2的预测正确率达到1.0，说明该算法能够有效识别出网络中冗 余不确定节点的真实身份。

以上是对本发明进行了示例性描述，显然本发明的实现并不受上述方 式的限制，只要采用了本发明技术方案进行的各种改进，或未经改进将本 发明的构思和技术方案直接应用其它场合的，均在本发明的保护范围内。