一种基于动态随机游走的多粒度路由网络表达方法与流程

1.本发明属于网络拓扑结构分析领域，具体涉及一种基于动态随机游走的多粒度路由网络表达方法。


背景技术：

2.随着卫星通信和互联网的发展，网络结构的规模呈指数增加，针对复杂的大规模网络分析成为当前的重要问题。传统用邻接矩阵表示网络的结构，它的维度为设备数n的平方，对于真实世界的大规模网络是不能接受的。而且大部分网络是稀疏的，用邻接矩阵表示会有很多的冗余信息。基于嵌入的网络表达方法旨在学习设备在低维空间中的连续稠密表示，从而减少噪声和冗余信息。
3.如果直接针对原网络进行训练复杂度会很高，通过分而治之的思想，将原网络进行粒度分层，然后采用并行计算的思想，加快模型训练速度。


技术实现要素：

4.为解决以上现有技术存在的问题，本发明提出了一种基于动态随机游走的多粒度路由网络表达方法，该方法包括：
5.s1：获取网络中各个节点的信息，根据节点信息计算各个节点的重要性；根据重要性将各个节点划分到多粒度图上；
6.s2：根据多粒度图中的每层节点的重要性和邻域结构计算每个图层节点对的边权，该边权为各个节点的相似性，将该相似性将会作为动态随机游走的初始概率；
7.s3：采用动态随机游走策略对每个节点进行处理，该游走策略中各个节点根据相似性选择后续节点，从而生成上下文节点序列；
8.s4：将生成的上下文节点序列输入到skip
‑
gram模型中进行训练，得到节点的低维向量φ。
9.优选的，计算各个节点的重要程度包括：根据度中心性和中介中心性计算节点的重要性；无向未加权网络为g＝(v,e)，计算无线未加权网路中的节点的度中心性和中介中心性；对计算出的度中心性和中介中心性进行归一化处理；将归一化后的度中心性和中介中心性进行加权融合处理，得到各个节点的重要程度，其中，v表示网络的节点数，e表示网络的边数。
10.进一步的，度中心性、中介中心性以及节点的重要程度计算公式为：
11.度中心性：
[0012][0013]
中介中心性：
[0014]
[0015]
节点的重要程度：
[0016]
imp(i)＝λ*dc(i) (1
‑
λ)*bc(i)
[0017]
优选的，根据重要性将各个节点划分到多粒度图上的过程包括：根据各个节点的重要程度的大小计算各个节点的相似性，根据相似性的大小将节点分为4类，每类对应一个粒层；节点划分的4个类别包括核心节点、重要节点、普通节点以及边缘节点。
[0018]
进一步的，计算每个粒层节点之间的相似的公式为：
[0019][0020]
优选的，计算每个加权图中的节点对之间的相似性的过程包括：根据每层节点之间的相似性构建相似性矩阵s和邻接矩阵a；根据相似性矩阵和邻接矩阵确定各层的权重矩阵w；根据权重矩阵构建各粒层之间的映射关系；根据映射关系以及权重矩阵对多粒度图进行重构，得到多粒度加权图。
[0021]
进一步的，各粒层之间的映射关系为：
[0022][0023]
w(k,k
‑
1)＝1
‑
w(k,k 1)
[0024]
优选的，采用动态随机游走策略对每个节点进行处理的过程包括：节点i和j为多粒度图的第k层中，将节点i选择节点j进行博弈，在博弈过程中，第k层的所有节点都参与博弈，使得边权发生动态变化；在进行随机游走前的边权的状态为s
l
，则在进行游走后，边权的状态变为s
l 1
，边权的变化表达式：
[0025][0026][0027]
优选的，将生成的上下文节点序列输入到skip
‑
gram模型中进行训练的过程包括：
[0028]
步骤1：将上下文节点序列中的节点分配给二叉树叶子；
[0029]
步骤2：采用二叉树分类器计算序列中每个节点分配到二叉树叶子的条件概率；
[0030]
步骤3：对于每个节点，采用softmax分类器在分类树中分配由一组树节点(t0，t1，t2，
…
，t
h
)组成的特定路径；
[0031]
步骤4：根据条件概率以及组成的特定路径计算模型的目标函数；
[0032]
步骤5：根据目标函数计算模型的损失函数；
[0033]
步骤6：当损失函数最小时，得到节点的低维向量表示。
[0034]
进一步的，损失函数的表达式为：
[0035]
[0036]
本发明的效果：
[0037]
1)本发明采用多粒度的思想，将初始网络根据性质进行划分，需要计算网络设备的两种种性质：度中心性(dc)、中介中心性(bc)，既考虑了结构性，也考虑了同质性；
[0038]
2)引入博弈的思想，构建收益矩阵让其在游走过程中进行动态变化，这更符合传播动力学；
[0039]
3)本发明采用并行随机游走策略对节点序列进行处理，大大提升效率；
[0040]
4)本发明采用skip
‑
gram无监督训练算法，不需要借助标签信息，利用游走序列本身的关系，得到设备的低维向量表示。
附图说明
[0041]
图1为本发明的基于动态随机游走的多粒度路由网络表达方法的实现流程图。
具体实施方式
[0042]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0043]
一种基于动态随机游走的多粒度路由网络表达方法，如图1所示，该方法包括：
[0044]
s1：获取网络中各个节点的信息，根据节点信息计算各个节点的重要性；根据重要性将各个节点划分到多粒度图上；
[0045]
s2：根据多粒度图中的每层节点的重要性和邻域结构计算每个图层节点对的边权，该边权为各个节点的相似性，将该相似性将会作为动态随机游走的初始概率；
[0046]
s3：采用动态随机游走策略对每个节点进行处理，该游走策略中各个节点根据相似性选择后续节点，从而生成上下文节点序列；
[0047]
s4：将生成的上下文节点序列输入到skip
‑
gram模型中进行训练，得到节点的低维向量φ。得到的节点的低维向量φ为多粒度路由网络表达结果。
[0048]
计算各个节点的重要程度包括：根据度中心性和中介中心性计算节点的重要性；无向未加权网络为g＝(v，e)，计算无线未加权网路中的节点的度中心性和中介中心性；对计算出的度中心性和中介中心性进行归一化处理；将归一化后的度中心性和中介中心性进行加权融合处理，得到各个节点的重要程度，其中，v表示网络的节点数，e表示网络的边数。各个公式的表达式为：
[0049][0050][0051]
imp(i)＝λ*dc(i) (1
‑
λ)*bc(i)
[0052]
其中，dc(i)是节点i的度中心性。如果节点i和j之间存在连边，则x
ij
＝1；否则x
ij
＝0。bc(i)是节点i的中介中心性，g
jk
代表节点j和k之间的最短路径的数量，g
jk
(i)表示依次连接节点j、i、k的最短路径数量，λ表示权重，且0＜λ＜1。
[0053]
为了解决网络结构问题，需要通过粒度粗化来简化复杂的结构，然后在不同的粒层上并行解决问题，以减少时间复杂度。根据重要性将各个节点划分到多粒度图上的过程包括：根据各个节点的重要程度的大小计算各个节点的相似性，根据相似性的大小将节点分为4类，每类对应一个粒层；节点划分的4个类别包括核心节点、重要节点、普通节点以及边缘节点。
[0054]
计算每个粒层节点之间的相似的公式为：
[0055][0056]
其中，k表示第k个粒层，s
k
(i，j)表示节点间的结构相似性，imp(i)表示节点i的重要程度，imp(j)表示节点j的重要程度，当节点i和j的重要性相等时，s
k
(i，j)＝1。
[0057]
由于重建的多粒度加权图没有考虑原始网络中节点之间的边关系。为了丰富模型中网络的边缘信息，每个粒层的邻接矩阵可以作为信息的补充。如果同一粒层中的两个节点是邻居，且具有相似的重要性，经过训练之后应该会有更紧密的表示。在第k层中，其邻接矩阵定义如下：
[0058][0059]
结合结构相似性矩阵s和邻接矩阵a，第k层的权重矩阵最终表示如下：
[0060]
w
k
(i,j)＝δ*s
k
(i,j) (1
‑
δ)*a
k
(i,j)
[0061]
其中，w既包含了节点的全局结构信息，也包含了节点的局部边缘信息，δ用于调整s和a所占的权重。
[0062]
由于每个粒层之间仍是相互独立的，则有在各粒层之间建立映射关系，具体定义如下：
[0063][0064]
w(k,k
‑
1)＝1
‑
w(k,k 1)
[0065]
其中，w(k，k 1)代表第k层与第(k 1)层之间的映射关系，w(k，k
‑
1)代表第k层与第(k
‑
1)层之间的映射关系，|v
k
|表示第k层中的节点数。
[0066]
中间粒层的每个节点都增加了两个连接，一个用于连接上一个粒层，另一个用于连接下一个粒层。值得注意的是，第一层仅添加了一个连接来与第二层连接，最后一层只增加了一个连接与倒数第二层相连。最后，重构的多粒度图定义为g'＝(v
mg
，e
mg
，w)，v
mg
表示重构的多粒度图节点的集合，e
mg
表示边的集合，w表示每个粒层的权重矩阵。
[0067]
采用动态随机游走策略对每个节点进行处理的过程包括：根据结构相似性和邻接矩阵确定节点间的权重；根据节点间的权重确定游走概率；为了使相似的节点在游走过程中更紧密，引入了博弈论的思想，在游走过程中动态调整节点间的权重。
[0068]
本发明采用的演化稳定策略是基于公共品博弈，将多粒度图中的节点视为博弈对象，将随机游走过程作为博弈过程，节点在博弈过程中将采取合作或背叛策略。对于每个粒层，每个节点都与其它节点一起进行博弈。整个博弈过程可以分为|v
k
|
‑
1次子博弈，则收益矩阵为：
[0069][0070]
其中，策略c表示节点选择合作策略，策略d表示节点选择背叛策略。
[0071]
若节点i和j都在第k层，则表示当节点选择合作策略c时边(i，j)的收益，节点j是随机游走过程中节点i的后继。y＝βw(i，j)表示当节点i和j选择合作时边(i，j)本身的支出。v
k
表示第k个粒层中的节点集合，α和β是控制收益和支出比例的超参数。多粒度图中的节点参与了博弈，导致节点之间的权重发生了变化。在参与博弈之前，边缘权重的状态为s
l
，在该次博弈结束后，状态变为s
l 1
，博弈前后权重的变化为：
[0072][0073][0074]
其中，α表示从其它节点获得的收益比例，β表示每次博弈自己的支付比例。
[0075]
每个粒层的节点通过博弈来选择随机游走的后续节点。当游走从第k层跳到第(k 1)层时，后续节点从第(k 1)层中重要性排名前5个节点中挑选。当游走从第(k 1)层跳到第k层时，后续节点从第k层中重要性排名倒数5个节点中挑选。
[0076]
skip
‑
gram模型为一种前沿的特征学习方法，可以通过句子的上下文生成有意义的词表示。kip
‑
gram的核心思想是最大化序列中上下文的可能性，其定义为：
[0077][0078]
其中，w是窗口的大小，为了将预测问题转化为计算最大化层次结构中特定路径的概率，将节点分配给二叉树的叶子，然后使用二叉树分类器来计算下面公式中的条件概率。对于每个节点j∈v，分层softmax在分类树中分配由一组树节点(t0,t1,t2,
…
，t
h
)组成的特定路径。在这种情况下，其条件概率可以定义如下：
[0079][0080]
其中节点i的向量表示为pr(t
u
|φ(i))可以由分配给t
u
的二分类器来计算，t
u
是节点j的父节点。
[0081]
pr(t
u
|φ(i))的定义为：
[0082][0083]
其中ψ(t
u
)是t
u
的向量表示。t
u
＝0表示选择左分支，t
u
＝1表示选择右分支。由于t
u
只能取0和1两个值，因此公式可以改为：
[0084][0085]
目标函数是根据其特征表示来最大化条件概率，可以表示为：
[0086][0087]
损失函数可以定义为最小化其对数函数的相反数，损失函数的表达式为：
[0088][0089]
通过最小化损失函数l来更新节点表示向量φ，最后得到优化的节点向量表示。
[0090]
随着卫星互联网的快速发展，针对目前越来越复杂的地面路由网络结构，传统网络分析方法已经无法满足当前任务需求的问题，提出用机器学习的方法对路由网络进行分析。该模型用于学习网络中节点的同构性和同质性。为了使相似的节点在随机游走中能更接近，模型重建了加权多粒度图，以让在全局结构和局部邻域关系相似的节点间有更大的权重，在该图上进行并行化随机游走可以大大降低模型的时间复杂度。同时节点间的边权并不是固定不变的，改方法引入博弈的思想，构建收益矩阵让其在游走过程中进行动态变化，这更符合传播动力学。综上所述，上述模型综合了多种优秀思想以让节点的低维表示更加精确。实验结果证明了其在节点重要性分类和可视化等任务中都有很好的表现。
[0091]
以上所举实施例，对本发明的目的、技术方案和优点进行了进一步的详细说明，所应理解的是，以上所举实施例仅为本发明的优选实施方式而已，并不用以限制本发明，凡在本发明的精神和原则之内对本发明所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。