一、什么是空间网络瓦解问题定义传统拓扑网络概念映射到空间网络概念含义拓扑网络空间网络普通复杂网络只记录节点‑边连接关系空间网络每个节点带有真实地理空间坐标例如航空网、铁路网、城市交通网节点分布在地理平面上。节点移除区域毁伤传统模型攻击是删除单个 / 一批离散节点。空间场景攻击经常是地理区域打击一块地理范围内所有节点一起被摧毁不是零散挑选节点叫区域毁伤。关键节点关键区域传统找对网络影响最大的单个关键节点枢纽。空间网络不再只识别单点识别关键地理区域打击这片区域网络整体功能会遭受严重破坏。通俗理解拓扑网络只看谁和谁相连没有地理位置。比如社交网络只记录好友关系不关心人在哪。空间网络节点有真实地理位置USAir 航空网络、铁路网络都属于空间网络。机场、车站分布在地图上。传统攻防攻击是挑选若干编号节点做删除TAS/RAS挑枢纽节点或者随机挑节点。空间场景的新威胁区域毁伤。比如一个地理片区遭到打击这个片区内所有机场 / 站点全部失效是一块区域整体失效不是零散选几个节点。于是研究对象也跟着变 传统找关键节点空间网络要找关键区域—— 哪一块地理区域一旦被毁整个网络瓦解程度最大。二、一般模型左侧图原始空间网络节点带有真实地理坐标x 轴范围约 0.34~0.42y 轴范围约 0.51~0.60。这是一个典型的空间网络类似城市交通网、路网节点在地理平面上分布边代表节点间的连接。坐标数值不在 0~1 之间且 x、y 两个维度的取值范围不一样直接拿来做区域毁伤、距离计算会有问题。右侧公式按列最小 - 最大归一化C坐标矩阵每一行是一个节点每一列是一个坐标维度第 1 列 x第 2 列 y。\(C(:,j)\)第 j 列的所有值也就是所有节点在第 j 个维度上的坐标。\(\min(C(:,j))\)、\(\max(C(:,j))\)该维度上所有节点坐标的最小值、最大值。\(\hat{C}_{ij}\)归一化之后第 i 个节点第 j 维的坐标。计算效果对每一个维度独立做线性缩放该维度最小值 → 映射为 0该维度最大值 → 映射为 1中间值 → 按比例缩放到 0~1 之间注意是按列按维度分别归一化不是全局统一缩放。x 维度用 x 的 min/maxy 维度用 y 的 min/max。为什么要做这一步空间网络瓦解研究的必要性消除量纲和尺度差异真实地理坐标经纬度数值范围大x、y 维度范围不一致归一化后两个维度都在 [0,1]距离计算、区域划分才公平。方便定义区域毁伤归一化到单位正方形 [0,1]×[0,1] 之后可以方便地用网格划分、滑动窗口、圆形 / 方形区域来做区域毁伤模拟区域大小参数也统一到 0~1 尺度。不同网络可对比不同城市、不同数据集的地理坐标范围千差万别归一化到 0~1 之后实验结果可以跨网络横向比较。数值计算稳定避免坐标数值过大导致的浮点精度问题后续计算节点间距离、区域覆盖更稳定符号定义瓦解圆坐标 \(O(G)(O_{q1},O_{q2})\)瓦解圆的圆心坐标落在前面归一化后的 \([0,1]\times[0,1]\) 标准空间坐标系内。潜在瓦解圆集合 \(Y[y_1,y_2,...,y_m]\)将单位正方形做 \(w\times w\) 空间网格划分网格交点就是全部候选圆心位置 Y 是全部可选打击圆心的集合攻击者只能从这 m 个候选圆心里面选打击位置不能任意取点。左图\(w\times w\)网格划分把整个空间切分网格网格交点生成全部候选圆心控制候选打击点数量降低组合爆炸。瓦解圆半径 R圆形打击区域的半径半径固定代表打击的覆盖范围。毁伤规则核心瓦解圆内所有的节点和其连边被移除只要节点的地理坐标落在这个圆形内部该节点直接失效删除和该节点相连的全部边也一并删掉圆外面节点不受本次打击影响。右图示意图棕色圆形就是一次瓦解圆打击圆内部扎堆的网络节点全部被抹除。模型逻辑流程预处理网络节点坐标 min‑max 归一化到单位正方形 \([0,1]\times[0,1]\)对正方形做 \(w\times w\)网格划分网格交点生成候选圆心集合 Y攻击者策略从集合 Y 中选择若干个圆心搭配固定半径R生成打击瓦解圆凡是落入任意一个瓦解圆内部的节点全部移除连同相连边得到毁伤之后残缺空间网络之后可以方案 A拓扑评价计算最大连通分量等拓扑指标方案 B你的论文路线在被毁伤网络上跑 SIR/IC 蒙特卡洛仿真计算期望传播规模作为博弈收益。和传统节点移除模型对比表格传统拓扑网络攻击空间网络瓦解圆区域毁伤攻击者自由挑选任意编号节点删除攻击者选择地理圆心打击圆内地理连续成片的所有节点被攻击节点可以空间上分散、互不相邻被摧毁节点一定是地理上聚集在圆形区域内受地理约束策略空间所有节点子集组合爆炸策略空间网格候选圆心集合通过网格 w 控制候选数量约束攻击集合缓解爆炸瓦解效果测度指标解决问题做完瓦解圆区域打击之后怎么量化衡量这次打击把网络破坏到什么程度。公式X本次打击策略选的瓦解圆位置G原始完整网络\(\hat G\)遭受瓦解圆打击之后被删去圆内节点的残缺网络原始网络的网络性能指标\(\Gamma(\hat G)\)打击后残缺网络的性能指标\(\Phi(X)\)相对瓦解程度取值 0~1\(\Phi0\)打击几乎没造成破坏网络性能几乎不变\(\Phi1\)打击把网络性能完全摧毁物理含义网络性能相对下降的比例。图中标注\(\boldsymbol{\GammaLCC}\)最大连通片 Largest Connected Component这里文献基准版本\(\boldsymbol \Gamma\)取最大连通分量 LCC 的节点数目拓扑指标\(\Gamma(G)\)原始网络最大连通分量节点数\(\Gamma(\hat G)\)遭区域毁伤之后剩余网络最大连通分量节点数代入公式\(\Phi(X)\frac{\text{原始LCC大小}-\text{打击后LCC大小}}{\text{原始LCC大小}}\) 代表最大连通分量规模相对下降多少比例用来衡量网络拓扑被瓦解的严重程度。图上示意图左边两张子图上图瓦解圆打在右侧下图同一个网络瓦解圆打在偏左下位置问号就是同样半径的打击圆打在不同地理位置LCC 下降多少瓦解程度\(\Phi(X)\)多大右边示意图网络被打击之后分裂成多个连通子图LCC 就是其中节点数量最多那一块连通子图。左侧优化问题的数学形式化目标函数\(\)X攻击策略向量长度为 M候选瓦解圆的总数\(x_l\)第 l 个候选瓦解圆是否被选中\(x_l1\) 表示选\(x_l0\) 表示不选\(\Phi(X)\)选这一组瓦解圆之后网络的相对瓦解程度上一页讲的公式攻击者目标在有限打击次数下让网络瓦解程度最大约束条件第一个约束选中的瓦解圆总数恰好等于 k攻击者只能打 k 次资源有限第二个约束每个候选瓦解圆要么选要么不选是 0-1 整数决策这是一个带基数约束的 0-1 整数优化问题从 M 个候选打击点中选 k 个使瓦解效果最大。右侧NP-Hard 证明思路归约到集合覆盖问题 SCP证明一个问题是 NP-Hard标准做法是把一个已知的 NP-Hard 问题归约到它。这里用的是集合覆盖问题Set Cover Problem, SCP。对应关系表格集合覆盖问题 SCP空间网络瓦解问题全集 U网络全部节点的集合集合族 S若干个子集瓦解策略集合每个瓦解圆能覆盖 / 摧毁的节点构成一个子集子集 \(S_i\)单个瓦解圆打击策略该圆内被摧毁的节点集合目标用最少子集覆盖全集对应选若干瓦解圆使被摧毁节点集合最大瓦解程度最大归约逻辑集合覆盖问题是经典 NP-Hard 问题空间网络瓦解问题可以看作集合覆盖的变种每个瓦解圆对应一个 可摧毁节点子集攻击者要选 k 个子集使它们的并集被摧毁节点对网络性能的破坏最大既然集合覆盖是 NP-Hard空间网络瓦解问题至少和它一样难因此也是 NP-Hard。简单说想从 M 个候选打击点里暴力枚举所有 \(C_M^k\) 种组合找最优组合数随网络规模指数爆炸算不动。符号说明SDSpatial Degree空间度瓦解圆覆盖区域内所有节点的度数总和SESpatial Edge空间边数瓦解圆覆盖区域内包含的全部边的总数量 SD、SE 就是区域中心性指标用来衡量某一个瓦解圆的破坏潜力圆内节点度数越高、边越多这个打击位置价值越高。左侧示意图两个不同圆心的瓦解圆橙色、蓝色覆盖不同的一批网络节点不同圆 SD/SE 数值不一样。算法完整步骤贪心迭代选择瓦解圆Step1遍历全部候选瓦解圆计算每个瓦解圆对应的 SD区域总节点度或者 SE区域总边数。Step2SD/SE 降序排序选择当前得分最高的瓦解圆移除该圆内部全部节点与连边。Step3计算本次打击之后的瓦解效果指标\(\boldsymbol{\Phi(X)}\)。Step4网络已经被破坏节点、边发生变化更新剩余网络每个节点的度、连接关系。Step5回到 Step1 循环迭代不断选下一个最优瓦解圆终止条件已经选够预设k个瓦解圆 / 攻击成本耗尽。算法本质贪心策略每一步只选当下看起来收益最大的瓦解圆每打击一次就更新网络状态再做下一轮选择。 属于迭代贪心算法用来求解 NP‑Hard 的空间瓦解问题得到近似最优攻击策略。优缺点✅优点计算速度远小于暴力枚举全部组合可输出多轮打击的攻击序列物理含义清晰优先打击节点、边高度聚集的地理区域。❌缺点 贪心是局部最优不一定等于全局最优会出现 “短视”当前单圆收益最大但多个圆组合之后整体瓦解效果不是全局最好。潜在瓦解圆候选打击圆心集合 Y识别 / 生成完整逻辑结合前面 PPT归一化 → \(w\times w\)网格划分 → 生成全部候选圆心得到潜在瓦解圆集合\(Y\{y_1,y_2…y_m\}\)1、前置预处理原始网络节点带有真实空间坐标\((lat,lon)\)或者平面\((x_{raw},y_{raw})\)min‑max 归一化把所有节点坐标映射到单位正方形 \([0,1]\times[0,1]\)所有节点全部被框在 0‑1 的正方形内后续网格、瓦解圆计算都在这个归一化坐标系完成。2、网格采样生成候选圆心PPT 标准做法把单位正方形均匀切分为 \(\boldsymbol{w\times w}\) 的空间网格w网格划分粒度人为设置超参数例如\(w20\)代表横向 20 格、纵向 20 格网格线交点就是全部潜在瓦解圆的圆心位置每一个交点\(y_i(o_{q1},o_{q2})\)搭配固定打击半径R就构成一个潜在瓦解圆全部交点收集起来构成候选集合 \(Y[y_1,y_2,…,y_m]\) 总候选数量 \(m(w1)^2\)。举例\(w20\)网格交点\((201)^2441\)个潜在圆心也就是一共有 441 个潜在瓦解圆可供攻击者选择。关键点不是网络节点位置瓦解圆圆心可以落在没有网络节点的空白地理位置打击圆只看哪些节点落在这个圆形范围内圆心本身不需要是网络节点。为什么不用网络节点当圆心如果只用节点位置做圆心打击中心只能固定在节点上现实打击可以打击节点之间的地理区域网格采样可以覆盖整片空间更贴合区域毁伤。w参数的权衡w越大网格越密候选圆心越多更接近连续空间但是m爆炸后面贪心、仿真计算量暴涨w越小候选点少计算快但是采样稀疏有可能漏掉优秀打击位置。3、一个潜在瓦解圆如何判定哪些节点会被摧毁给定候选圆心\(y_i(o_{q1},o_{q2})\)固定半径R 遍历网络每一个节点v节点归一化坐标\((x_v,y_v)\) 计算欧氏距离\(d\sqrt{(x_v-o_{q1})^2(y_v-o_{q2})^2}\)如果 \(d\le R\)该节点落在瓦解圆内打击发生后该节点以及全部相连边被移除如果 \(dR\)节点不受该瓦解圆影响。每一个潜在瓦解圆\(y_i\)预先就可以算出它能够摧毁哪一批节点子集。潜在瓦解圆不是网络自带的是我们人为采样生成的。三、虚拟节点四、成本约束