基于主动图分割的分布式牛顿法的制作方法

1.本发明涉及图信号处理技术领域，具体是基于主动图分割的分布式牛顿法。


背景技术：

2.在图信号处理框架中，分布式方法是处理大规模图信号的一种重要的方法。然而，在现有的分布式方法中，所有节点都以等同的角色地执行局部运算，这种方式产生大量的计算和通信开销。此外，许多现实中的大规模图在进行分布式图信号处理时一般会出现功能异常节点，如：运算或通信延迟较大的节点，电池供电的能量受限节点。在这样的图中，个别节点的功能异常将使现有的分布式方法无法正常工作。因此，需要为这样的大规模图设计一种只需要部分节点执行子图核心运算，同时具备快速收敛、较低计算和通信代价的分布式算法。


技术实现要素：

3.本发明的目的是针对现有分布式方法的不足，提供了一种新的分布式牛顿法。这种方法采用主动图分割的分布式牛顿法只需要部分节点执行子图核心运算，该方法具备收敛快速、计算和通信代价低的特点。
4.实现本发明目的的技术方案是：
5.基于主动图分割的分布式牛顿法，与现有技术不同处在于，包括如下步骤：
6.1)主动图分割方法设计：主动图分割方法的目的是确定子图中心节点，主动图分割方法基本原则：给定正整数ρ0，选择包含ρ0跳邻居节点最多的节点作为子图中心节点，以该原则为基础，主动图分割的过程为：采用多次迭代确定所有的子图中心节点，在每一次迭代中，以节点与节点的ρ0跳邻居节点之间的指示消息的收发为基础，确定包含ρ0跳邻居节点最多的节点作为子图中心节点，即在初始化中，网络中所有节点的状态设置为未被包含状态s
u
，即具有s
u
状态的节点不是任何一个子图中心节点的ρ0跳邻居节点，相对应的，在迭代过程中，如果某节点成为某个子图中心节点的ρ0跳邻居节点，则该节点状态更新为被包含状态s
c
，指示消息仅在具有s
u
状态的节点之间进行收发，在每次迭代中，节点i向节点i的ρ0跳邻居节点发送一条仅包含序列编号i的指示消息，同时接收来自节点i的ρ0跳邻居节点的指示消息，节点i根据接收到的指示消息确定节点i的ρ0跳邻居节点总数，记为m
i
，ρ0跳邻居节点最多的节点确定为子图中心节点，子图中心节点及子图中心节点的ρ0跳邻居节点的状态更新为s
c
，由此可知，随着迭代次数的增加，所有具有s
u
状态的节点收到的指示消息数量的最大值τ是递减的，而当τ＝0时，表示所有节点都是s
c
状态，即图分割方法终止，因此，τ可以作为图分割方法的迭代终止条件，τ的初始值即为图中各节点的ρ0跳邻居节点数量的上限其中，已知参数和d分别是图的beurling维度和beurling密度；
7.2)主动图分割的迭代过程：主动图分割的迭代过程运行于节点i如下所示：输入：ρ0，η
u
，初始化：节点i的状态设置为s
u
，令τ＝η
u
，则：
[0008]1‑
2)如果节点i的状态为s
u
，则向节点i的ρ0跳邻居节点发送指示消息，否则跳转至步骤4
‑
2)；
[0009]2‑
2)节点i通过接收到的指示消息获取m
i
；
[0010]3‑
2)如果m
i
≠τ跳转至步骤4
‑
2)；否则节点i被确定为子图中心节点，同时，节点i及节点i的ρ0跳邻居节点的状态更新为s
c
；
[0011]4‑
2)令τ＝τ
‑
1，如果τ＝0，则迭代终止；否则，返回步骤1
‑
2)继续进行迭代，
[0012]
输出：如果节点i为子图中心节点，则输出i，迭代过程在每一个节点上独立运行，η
u
次迭代后，各节点执行的迭代过程同时结束；
[0013]
3)部分节点进行子图核心运算的分布式牛顿法设计：在图上，以b(i,r)表示节点i及节点i的r跳邻居节点组成的集合，v
c
是图的节点集合v的子集，子图中心节点集合v
c
由步骤2)所述迭代过程确定，其中的每一个节点都对应一个以该节点为中心，以r0的为半径的子图，图上的最小二乘问题为公式(1)所示：
[0014][0015]
其中，h＝[h(i,j)]
i,j∈v
为具有测地宽度σ的图信号算子，x＝(x(i))
i∈v
为图各节点的信号值组成的图信号，x
*
为问题(1)的最优解，z0＝(z0(i))
i∈v
为观测信号，公式(1)被分解为子图上的最小二乘问题为公式(2)所示：
[0016][0017]
其中，为以节点i为中心节点的子图的最优解，矩阵的元素定义为公式(3)所示：
[0018][0019]
每一个子图中心节点i利用牛顿法迭代求解公式(2)，迭代公式为公式(4)所示：
[0020][0021]
其中，t≥0为迭代次数，为局部海森逆矩阵的近似矩阵，为局部图信号算子，
[0022]
4)部分节点进行子图核心运算的分布式牛顿法的迭代过程：部分节点进行子图核心运算的分布式牛顿法的迭代过程运行于节点i∈v
c
过程如下：
[0023]
输入：终止条件ε、观测信号z0、子图半径r0跳、σ、最高迭代次数c，
[0024]
初始化：令t＝0，则：
[0025]1‑
4)获取和分别组成g
i
和h
i
；
[0026]2‑
4)计算
[0027]3‑
4)更新
[0028]4‑
4)向b(i,2(r0 σ))\{i}中的节点发送的相应的信号值；
[0029]5‑
4)接收来自b(i,2(r0 σ))\{i}中的节点相应的信号值组成
[0030]6‑
4)如果或者迭代次数t超过指定次数c，则停止迭代并输出节点i及其r0/2跳邻居节点对应的信号值，否则，更新t＝t 1并回到步骤1)继续进行迭代；
[0031]7‑
4)令并向b(i,r0/2)\{i}中的节点发送的相应的信号值，输出：v
c
中的所有子图中心节点执行本步骤的迭代过程，进而问题(1)的近似解为公式(5)所示：
[0032][0033]
步骤3)中所述的子图半径r0＝2ρ0跳。
[0034]
步骤3)中所述的矩阵g的表达式如公式(6)所示：
[0035][0036]
本技术方案与现有技术相比，本技术方案采用主动图分割，将大规模图分割为以部分节点为中心节点的子图，并以这些子图为基础将大规模图上的最小二乘问题分解为子图上的最小二乘问题，进而在子图中心节点采用牛顿法对子图的最小二乘问题进行迭代求解。这种方法采用主动图分割的分布式牛顿法只需要部分节点执行子图核心运算，该方法具备收敛快速、计算和通信代价低的特点。
附图说明
[0037]
图1为实施例中随机几何图rgg
4096
的结构示意图；
[0038]
图2为实施例中随机几何图rgg
4096
的子图中心节点分布示意图；
[0039]
图3为实施例中rmse误差收敛曲线示意图。
具体实施方式
[0040]
下面结合附图和实施例对本发明的内容作进一步的阐述，但不是对本发明的限定。
[0041]
实施例：
[0042]
基于主动图分割的分布式牛顿法，与现有技术不同处在于，包括如下步骤：
[0043]
1)主动图分割方法设计：主动图分割方法的目的是确定子图中心节点，主动图分割方法基本原则：给定正整数ρ0，选择包含ρ0跳邻居节点最多的节点作为子图中心节点，以该原则为基础，主动图分割的过程为：采用多次迭代确定所有的子图中心节点，在每一次迭代中，以节点与该节点的ρ0跳邻居节点之间的指示消息的收发为基础，确定包含ρ0跳邻居节点最多的节点作为子图中心节点，即在初始化中，网络中所有节点的状态设置为未被包含状态s
u
，即具有s
u
状态的节点不是任何一个子图中心节点的ρ0跳邻居节点，相对应的，在迭
代过程中，如果某节点成为某个子图中心节点的ρ0跳邻居节点，则该节点的状态更新为被包含状态s
c
，指示消息仅在具有s
u
状态的节点之间进行收发，在每次迭代中，节点i向节点i的ρ0跳邻居节点发送一条仅包含序列编号i的指示消息，同时接收来自节点i的ρ0跳邻居节点的指示消息，节点i根据接收到的指示消息确定节点i的ρ0跳邻居节点总数，记为m
i
，ρ0跳邻居节点最多的节点确定为子图中心节点，子图中心节点及子图中心节点的ρ0跳邻居节点的状态更新为s
c
，由此可知，随着迭代次数的增加，所有具有s
u
状态的节点收到的指示消息数量的最大值τ是递减的，而当τ＝0时，表示所有节点都是s
c
状态，即图分割方法终止，因此，τ可以作为图分割方法的迭代终止条件，τ的初始值即为图中各节点的ρ0跳邻居节点数量的上限其中，已知参数和d分别是图的beurling维度和beurling密度；
[0044]
2)主动图分割的迭代过程：主动图分割的迭代过程运行于节点i如下所示：
[0045]
输入：ρ0，η
u
，初始化：节点i的状态设置为s
u
，令τ＝η
u
，则：
[0046]1‑
2)如果节点i的状态为s
u
，则向节点i的ρ0跳邻居节点发送指示消息，否则跳转至步骤4
‑
2)；
[0047]2‑
2)节点i通过接收到的指示消息获取m
i
；
[0048]3‑
2)如果m
i
≠τ跳转至步骤4
‑
2)；否则节点i被确定为子图中心节点，同时，节点i及节点iρ0跳邻居节点的状态更新为s
c
；
[0049]4‑
2)令τ＝τ
‑
1，如果τ＝0，则迭代终止；否则，返回步骤1
‑
2)继续进行迭代，
[0050]
输出：如果节点i为子图中心节点，则输出i，迭代过程在每一个节点上独立运行，η
u
次迭代后，各节点执行的迭代过程同时结束；
[0051]
3)部分节点进行子图核心运算的分布式牛顿法设计：在图上，以b(i,r)表示节点i及节点i的r跳邻居节点组成的集合，v
c
是图的节点集合v的子集，子图中心节点集合v
c
由步骤2)所述迭代过程确定，其中的每一个节点都对应一个以该节点为中心，以r0跳为半径的子图，图上的最小二乘问题为公式(1)所示：
[0052][0053]
其中，h＝[h(i,j)]
i,j∈v
为具有测地宽度σ的图信号算子，x＝(x(i))
i∈v
为图各节点的信号值组成的图信号，x
*
为问题(1)的最优解，z0＝(z0(i))
i∈v
为观测信号，
[0054]
公式(1)被分解为子图上的最小二乘问题为公式(2)所示：
[0055][0056]
其中，为以节点i为中心节点的子图的最优解，矩阵的元素定义为公式(3)所示：
[0057][0058]
每一个子图中心节点i利用牛顿法迭代求解公式(2)，迭代公式为公式(4)所示：
[0059][0060]
其中，t≥0为迭代次数，为局部海森逆矩阵的近似矩阵，为局部图信号算子，
[0061]
4)部分节点进行子图核心运算的分布式牛顿法的迭代过程：部分节点进行子图核心运算的分布式牛顿法的迭代过程运行于节点i∈v
c
过程如下：
[0062]
输入：终止条件ε、观测信号z0、子图半径r0跳、σ、最高迭代次数c，
[0063]
初始化：令t＝0，则：
[0064]1‑
4)获取和分别组成g
i
和h
i
；
[0065]2‑
4)计算
[0066]3‑
4)更新
[0067]4‑
4)向b(i,2(r0 σ))\{i}中的节点发送的相应的信号值；
[0068]5‑
4)接收来自b(i,2(r0 σ))\{i}中的节点相应的信号值组成
[0069]6‑
4)如果或者迭代次数t超过指定次数c，则停止迭代并输出节点i及其r0/2跳邻居节点对应的信号值，否则，更新t＝t 1并回到步骤1)继续进行迭代；
[0070]7‑
4)令并向b(i,r0/2)\{i}中的节点发送的相应的信号值，输出：v
c
中的所有子图中心节点执行本步骤的迭代过程，进而问题(1)的近似解为公式(5)所示：
[0071][0072]
本例步骤3)中的子图半径r0＝2ρ0跳。
[0073]
步骤3)中所述的矩阵g的表达式如公式(6)所示：
[0074][0075]
仿真实验1：本次仿真采用主动图分割方法对随机几何图rgg
4096
进行子图划分，如图1所示，随机几何图rgg
4096
以空心圆圈表示的4096个节点随机分布在边长为1的正方形区域内，并且距离不大于的两个节点之间通过一条无向边连接，随机几何图rgg
4096
的beurling维度和beurling密度分别为2和3.0775，以ρ0＝2跳确定子图中心节点集合v
c
，其中的子图中心节点数为741，子图中心节点分布如图2所示，其中，黑色圆点表示子图中心节点，可以看出，子图中心节点只占所有节点的一部分并且整体分布均匀；
[0076]
仿真实验2：本次仿真采用基于主动图分割的分布式牛顿法求解rgg
4096
上的最小二乘问题：给定rgg
4096
上的原始信号，如公式(7)所示：
[0077]
x
orig
＝100u2 n
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)，
[0078]
其中，u2为rgg
4096
的归一化拉普拉斯矩阵的第二个特征向量，n为元素值均匀分布于[
‑
0.01，0.01]的随机向量，随机选取x
orig
中的1229个元素置为0其他2867个元素不变作为观测信号z0，通过z0估计原始信号，如公式(8)所示：
[0079][0080]
其中，i为4096阶单位矩阵，式中a为rgg
4096
的邻接矩阵，λ
max
(a)为a的最大特征根，采用本例方法得到的估计信号与原始信号x
orig
之间的误差以rmse如公式(9)所示：
[0081][0082]
rmse误差收敛曲线如图3所示，可以看出，采用本例方法在解决最小二乘问题时具有接近牛顿法的快速收敛性。