接下来将会以课程的形式进行详解核心思想是通过对拉普拉斯矩阵它第二小特征值向量进行求解然后对网络中的最大连通片进行谱划分从而来识别最优分割边界区域来进行拆解的一个主要思想第一课这篇论文解决什么问题先回顾之前学的内容之前我们学了BPD论文它解决的问题是删掉最少的节点让网络瘫痪 假设删每个节点的代价都一样 1这篇论文发现了一个大问题任小龙老师问了一个非常现实的问题现实中删掉每个节点的代价真的一样吗答案显然是不一样举个例子 想阻断一个犯罪网络 小混混度数低逮捕成本低 大boss度数高逮捕成本极高 有律师、有保镖、有钱 逮他花10倍的代价 之前所有算法都忽略了这个差别 直接去抓最重要的人度数最高的 → 代价极其昂贵 → 实际上非常不划算用一个生活例子彻底理解假设你要阻断一个传销网络预算有限传统算法BPD/CI的做法 找到网络里最核心的人连接最多 → 把他抓了 → 但他是总头目逮捕成本极高 任小龙的GND算法的做法 在花最少钱的前提下 找到一批性价比最高的人删掉 → 也许抓几个中层干部 → 花更少的钱同样让网络瘫痪一句话总结这篇论文在删除节点有不同代价的情况下如何用最少的总代价让网络瘫痪这叫做广义网络瓦解问题Generalized Network DismantlingGND这篇论文和BPD论文的关系BPD论文之前学的 删最少的节点 → 网络瘫痪 假设每个节点代价1 ↓ 任小龙发现这个假设不现实 GND论文这篇 花最少的总代价 → 网络瘫痪 每个节点代价可以不同 这是一个重要的推广和进步第二课代价是怎么定义的先理解代价这个概念在这篇论文里每个节点i都有一个代价值w_i 删掉节点i所需要付出的代价 可以代表 - 金钱成本收买或控制这个节点要花多少钱 - 保护等级这个节点有多难被攻击 - 能量消耗关闭这个节点需要多少能量 - 社会成本逮捕某人的政治/法律代价代价的两种情况情况一单位代价Unit Cost所有节点的代价相同 w₁ w₂ w₃ ... 1 这就是之前BPD、CI算法的假设 目标删掉最少数量的节点 这是GND问题的一个特殊情况情况二非单位代价Non-unit Cost——本文重点每个节点代价不同 w_A 1小混混好抓 w_B 5中层干部有点难 w_C 20大boss极难 目标让总代价 Σ wᵢ 最小 而不是让删除数量最少论文用什么来衡量代价论文在没有其他信息时用节点的度数作为代价的代理d_i 节点i的度数连接数量 为什么用度数 度数大的节点 → 连接多 → 更重要 → 更难被删除 → 代价更高 举例 节点A连着3个人 → w_A 3便宜 节点B连着50个人 → w_B 50昂贵总代价怎么计算论文用一个很直观的方式衡量总代价总瓦解代价 被删节点相邻的边数 ÷ 网络总边数 直觉理解 删掉一个度数为d的节点 → 同时删掉了d条边 → 度数越大删掉的边越多 → 代价越高为什么之前的算法会出问题这是本文最重要的发现之一传统算法BPD、Min-Sum等的逻辑 哪个节点最重要度数最大删它 问题 度数大的节点 代价最高的节点 结果 传统算法专门去删最贵的节点 → 总代价极其昂贵 → 有时候甚至比随机删除还差论文里的震撼结果图1对Petster-Hamster社交网络 相同代价 0.4 时 随机删除 网络缩小到75% GCC Min-Sum算法 网络缩小到85% GCC ← 比随机还差 GND算法 网络缩小到62% GCC ← 最好这说明什么 Min-Sum这样的聪明算法 在考虑代价之后 居然比随机乱删还要差 原因 Min-Sum专门去删Hub节点度数最大 Hub节点代价极高 → 花了很多钱效果却不好用犯罪网络理解这个直觉传统算法的思路 找最核心的犯罪头目把他抓了 → 但头目有钱有势逮捕代价极高 → 可能花光了所有预算只抓了一个人 GND算法的思路 在有限预算内找到性价比最高的组合 → 也许抓3个中层干部 → 花同样的钱但网络瘫痪程度更高小结代价的核心思想旧问题最少删几个节点数量最小化 ↓ 新问题总代价最小加权成本最小化 ↓ 关键洞察 高度节点Hub 高代价 传统算法偏爱删Hub → 代价爆炸 GND算法考虑代价 → 避开贵的Hub 选择性价比高的节点扩展GCC、Min-Sum算法第一部分GCC是什么基本定义GCC Giant Connected Component 巨型连通分量 网络中最大的那个连通块用图直观理解删节点之前A-B-C-D-E-F-G-H所有节点连在一起 GCC大小 8个节点 100%删掉几个节点之后A-B-C E-F H 块1 块2 块3 GCC 块1最大 3个小块 37.5%网络完全瘫痪时A B C D E F 每个节点都孤立 GCC ≈ 0%或低于阈值θ1%GCC为什么重要GCC大小 衡量网络是否还在正常运作的指标 GCC大50%网络基本完好信息/病毒还能传播 GCC小1% 网络已经瘫痪传播被阻断 所以 让GCC从大变小 成功瓦解网络论文里GCC的使用方式纵轴GCC Size网络最大连通块的相对大小 横轴Dismantling cost已花费的总代价 理想的曲线 GCC Size 1.0 |▓▓▓▓ 0.8 |░░▓▓ 0.6 |░░░▓ 0.4 |░░░░ 0.2 |░░░░ 0.0 |░░░░ 0 0.1 0.2 0.3 代价 花很少的代价 → GCC迅速下降 → 算法越好 注意只要代价稍稍大一点点 GCC就会有一个突然的下降第二部分Min-Sum算法起源和背景Min-Sum算法由Braunstein等人于2016年提出 发表在PNAS与本文同一期刊 它是在BPD之后提出的另一种 基于消息传递的网络瓦解算法核心思想Min-Sum的名字来自它的优化目标Min 最小化 Sum 被删节点数量之和 目标最小化 Σᵢ δ(节点i被删) 删掉最少数量的节点Min-Sum算法的工作原理它也是一种消息传递算法和BPD类似Step 1给每个节点分配一个删除倾向分数 Step 2节点之间互相传递消息 每个节点问邻居 如果我不在了你会怎样 Step 3根据收到的消息更新自己的分数 Step 4分数最高的节点被删掉 Step 5重复直到网络瘫痪Min-Sum和BPD的区别相同点 都是消息传递算法 都追求最小化被删节点数量 不同点 BPD基于自旋玻璃/FVS理论 专注于切断网络中的环 Min-Sum直接对瓦解问题建模 用求和最小化框架 在某些网络上比BPD更好Min-Sum的致命缺陷Min-Sum和BPD、CI一样的隐含假设 每个节点删除代价 1相同 当考虑非单位代价时 Min-Sum倾向于删掉度数大的节点 因为它们影响力最大 但度数大的节点代价也最高 结果 Min-Sum花费了极高的代价 效果却不如预期 论文中的数据 相同代价0.4的情况下 随机删除 → GCC缩小到75% Min-Sum → GCC缩小到85% ← 比随机还差为什么Min-Sum比随机还差用犯罪网络比喻 随机策略随机抓人 → 有时抓小混混便宜 → 有时抓中层中等 → 平均代价适中 Min-Sum策略专门抓最重要的人 → 每次都抓最核心的大boss → 大boss代价极高 → 花了大量预算只抓了几个人 → 网络其实还没怎么瘫痪 本质原因 Min-Sum优化的是删除数量 不是删除代价 两者在非单位代价下完全不同第三课GND的数学核心——拉普拉斯矩阵与特征向量第一步从一个简单问题开始假设你要把一个网络切成两半网络 A --- B --- C | | D --- E --- F 问题怎么切让切断的代价最小这个问题有很多种切法切法1切掉B把网络分成左右 切法2切掉A和C 切法3切掉B-C这条边…… 哪种最便宜这就是GND要解决的核心问题而它用拉普拉斯矩阵的特征向量来回答。第二步什么是邻接矩阵先从最基础的矩阵开始。用一个4节点网络举例网络 A --- B | | D --- C 正方形邻接矩阵AA B C D A [ 0 1 0 1 ] B [ 1 0 1 0 ] C [ 0 1 0 1 ] D [ 1 0 1 0 ] 规则 Aᵢⱼ 1i和j之间有链接 Aᵢⱼ 0i和j之间没有链接度矩阵D对角矩阵A B C D A [ 2 0 0 0 ] B [ 0 2 0 0 ] C [ 0 0 2 0 ] D [ 0 0 0 2 ] Dᵢᵢ 节点i的度数 正方形每个节点度2第三步什么是拉普拉斯矩阵LD−A普通拉普拉斯矩阵 A B C D A [ 2 -1 0 -1 ] B [-1 2 -1 0 ] C [ 0 -1 2 -1 ] D [-1 0 -1 2 ] 规律 对角线 节点的度数正数 非对角线 -1如果有链接或0没有链接 就算是普通的拉普拉斯矩阵也是一个完美的对称矩阵拉普拉斯矩阵的物理意义想象网络是一个弹簧系统 每条链接 一根弹簧 每个节点 一个质点 拉普拉斯矩阵描述了 如果我推动节点i 整个网络会怎么振动 特征向量 网络的自然振动模式 特征值 振动的频率第四步什么是特征向量先理解特征值和特征向量对于矩阵L如果存在向量v和数λ使得Lvλv那么v就是特征向量λ就是特征值。直觉理解普通矩阵乘以向量 → 向量的方向和大小都改变了 特征向量很特殊 → 矩阵乘以它之后方向不变 → 只是大小变了变为λ倍 就像 推一根弹簧特定频率 → 它按原来的形状振动 → 只是幅度变了拉普拉斯矩阵的特征值排列对于任何网络的拉普拉斯矩阵 λ₁ ≤ λ₂ ≤ λ₃ ≤ ... ≤ λₙ 重要性质 λ₁ 0第一个特征值永远是0 λ₂ 0第二个特征值 0 ↑ 这个叫做代数连通度 非常重要为什么第二小特征向量最重要第一特征向量 v⁽¹⁾ 对应λ₁ 0 v⁽¹⁾ (1,1,1,...,1)所有分量相等 含义网络的整体平均没有信息 第二特征向量 v⁽²⁾ 对应λ₂最小的非零特征值 含义网络最自然的分裂方式 → 正值节点自然聚在一边 → 负值节点自然聚在另一边 → 边界就是最优切割点这里有人可能会问 为什么要使用拉普拉斯矩阵 包括拉普拉斯矩阵的物理意义和性质是怎么得到的拉普拉斯矩阵——深度解析 第一部分为什么任小龙选择拉普拉斯矩阵先理解他面对的问题任小龙要解决的问题本质上是把网络切成两半 使得切断边界的总代价最小 数学上叫做最小图割问题Minimum Graph Cut其实这里也是表明最小图割问题可以用拉普拉斯矩阵来解决他有很多工具可以选择选项1暴力枚举所有切割方案 → 2^N种可能NP-hard完全不可行 选项2贪心算法每次删最划算的节点 → 局部最优容易陷入局部最小值 → 效果不好 选项3消息传递BPD/Min-Sum的方式 → 不考虑代价需要大改 → 难以自然融入非均匀代价 选项4拉普拉斯矩阵的谱方法 ✓ → 天然适合图分割问题 → 可以自然融入代价信息 → 有严格的数学保证 → 计算高效为什么谱方法天然适合图分割这要从一个深刻的数学定理说起Fiedler定理1973年 对于任何图的拉普拉斯矩阵L 第二小特征向量v⁽²⁾ 给出了图的最优二分割的近似解 这不是巧合而是有严格数学证明的注意是任何图且第二小特征向量给出了图的最优二分割的近似解这里是人家给出来解不用过多深纠任小龙的创新就是普通拉普拉斯Fiedler1973 → 最优分割但不考虑代价 任小龙的节点加权拉普拉斯2019 → 最优分割同时考虑代价 只需把代价信息编码进拉普拉斯矩阵 → 特征向量自动给出考虑代价的最优分割第二部分拉普拉斯矩阵的物理意义物理意义一热传导想象网络是一个导热系统每个节点 一个温度计 每条链接 一根导热棒 初始状态 节点A温度100度 其他节点温度0度 热量会怎么流动热传导方程L 拉普拉斯矩阵 T 每个节点的温度向量 含义 (LT)ᵢ dᵢTᵢ - Σⱼ AᵢⱼTⱼ 节点i的温度 × 度数 - 所有邻居温度之和 如果节点i比邻居热 (LT)ᵢ 0 → 热量从i流出 → 温度下降 如果节点i比邻居冷 (LT)ᵢ 0 → 热量流入i → 温度上升特征向量的物理含义特征向量v⁽ᵏ⁾ 系统的第k个自然冷却模式 λ₁ 0整体均匀温度永远不变 所有节点温度相同不流动 λ₂最小非零冷却最慢的模式 网络最难平衡的地方 自然的分割边界 λₙ最大冷却最快的模式 网络局部剧烈振荡用图来理解A---B---C---D一条链 最慢冷却模式v⁽²⁾ A和B偏热C和D偏冷 → 热量只能从B流向C → B-C之间是瓶颈 → 这就是最优切割点 热 → 冷 A() B() | C(--) D(---) ↑ 切这里物理意义二随机游走想象一只随机行走的蚂蚁在网络上规则 蚂蚁在节点i时 随机选择一条链接走到邻居节点 问题 这只蚂蚁长时间后 在各节点的概率分布是什么随机游走矩阵Pᵢⱼ Aᵢⱼ/dᵢ 从i走到j的概率 和拉普拉斯的关系 L D - A D(I - D⁻¹A) D(I - P)特征向量的物理含义第二小特征向量v⁽²⁾ 把节点染成正值红色和负值蓝色 蚂蚁从红色区域出发 → 很难走到蓝色区域 → 因为两区域之间链接很少 蚂蚁从蓝色区域出发 → 很难走到红色区域 → 这两个区域之间有瓶颈 → 瓶颈处 最优切割点物理意义三弹簧振动想象网络是一个弹簧质点系统每个节点 质量为1的质点 每条链接 弹簧常数为1的弹簧 质点可以上下振动 问题系统的自然振动频率是什么振动方程特征值λ 振动频率的平方 特征向量 振动模式 λ₁ 0整体平移不振动 λ₂最低频振动模式 网络最自然的摇摆方式 最低频振动 一半节点向上 另一半向下- 两半之间的弹簧被拉伸最多 → 两半之间的链接 最自然的切割点物理意义四电路网络想象网络是一个电阻网络每条链接 一个电阻阻值1 节点 导线连接点 在两个节点之间施加电压 → 电流会怎么流欧姆定律的矩阵形式L 拉普拉斯矩阵 V 每个节点的电压向量 I 注入电流向量 含义 (LV)ᵢ dᵢVᵢ - Σⱼ AᵢⱼVⱼ 从节点i流出的净电流 这正是基尔霍夫电流定律特征向量的物理含义第二小特征向量v⁽²⁾ 告诉我们网络的电阻瓶颈在哪里 λ₂越小 → 网络越难传导信号 → 两部分之间链接越少 → 切割越容易 λ₂越大 → 网络联通性很强 → 很难被分割 → 需要更多代价来瓦解四种物理意义的统一热传导 随机游走 弹簧振动 电路网络 ↓ ↓ ↓ ↓ └──────────┴───────────┴──────────┘ ↓ 拉普拉斯矩阵L ↓ 第二小特征向量v⁽²⁾ ↓ 揭示网络的自然分割边界 最小代价切割点第三部分什么时候用拉普拉斯矩阵判断标准适合用拉普拉斯矩阵的场景 1. 问题涉及分割或聚类 → 把网络切成几部分 → 找网络的社区结构 2. 问题涉及流动 → 信息/热量/电流在网络上传播 → 找传播瓶颈 3. 问题涉及连通性 → 网络有多稳健 → 最脆弱的地方在哪 4. 问题涉及代价最优化 → 用最小代价切断网络 → 用最小代价隔离某些节点不适合用拉普拉斯矩阵的场景不适合的场景 1. 需要找单个最重要节点 → 用度中心性/特征向量中心性更好 2. 需要找最短路径 → 用Dijkstra算法更好 3. 有向网络链接有方向 → 普通拉普拉斯不适用 → 需要用有向拉普拉斯 4. 代价在边上而不是节点上 → 需要边加权拉普拉斯任小龙为什么选对了任小龙的问题 用最小节点代价把网络切成小块 对应判断 ✓ 涉及分割切成小块 ✓ 涉及代价优化最小代价 ✓ 需要全局视角不是局部贪心 ✓ 网络是无向的普通拉普拉斯适用 → 拉普拉斯矩阵是完美选择 创新点 把节点代价wᵢ编码进矩阵 → 节点加权拉普拉斯 → 特征向量自动给出代价最优分割第四部分拉普拉斯矩阵的数学性质——怎么证明的性质一λ₁ 0第一特征值永远是0证明取向量 v (1,1,1,...,1)全1向量 计算 Lv (Lv)ᵢ Σⱼ Lᵢⱼ × 1 Lᵢᵢ Σⱼ≠ᵢ Lᵢⱼ dᵢ Σⱼ≠ᵢ (-Aᵢⱼ) dᵢ - dᵢ 0 所以 Lv 0 0×v → v(1,1,...,1) 是特征值为0的特征向量 → λ₁ 0 ✓ 物理含义 全1向量 所有节点状态相同 没有梯度/差异 不产生任何流动 系统不变化性质二所有特征值 λ ≥ 0半正定证明对任意向量x xᵀLx xᵀ(D-A)x xᵀDx - xᵀAx Σᵢ dᵢxᵢ² - Σᵢⱼ Aᵢⱼxᵢxⱼ Σᵢⱼ Aᵢⱼxᵢ² - Σᵢⱼ Aᵢⱼxᵢxⱼ 因为dᵢ Σⱼ Aᵢⱼ Σᵢⱼ Aᵢⱼ(xᵢ² - xᵢxⱼ) 由于对称性Aᵢⱼ Aⱼᵢ xᵀLx ½ Σᵢⱼ Aᵢⱼ(xᵢ² - 2xᵢxⱼ xⱼ²) ½ Σᵢⱼ Aᵢⱼ(xᵢ - xⱼ)² 由于Aᵢⱼ ≥ 0且(xᵢ-xⱼ)² ≥ 0 xᵀLx ≥ 0 对所有x成立 → L是半正定矩阵 → 所有特征值 λ ≥ 0 ✓这个公式的物理意义极其深刻xᵀLx ½ Σᵢⱼ Aᵢⱼ(xᵢ - xⱼ)² 含义 x 给每个节点赋予的值比如温度/电压 (xᵢ - xⱼ)² i和j之间的差异 Aᵢⱼ 两者是否相连 xᵀLx 所有相连节点对之间差异的总和 网络中总的不均匀程度 最小化xᵀLx → 让相连节点的值尽量相似 → 天然对应聚类/分割问题性质三λ₂ 0 当且仅当网络连通证明思路λ₂ 0 意味着什么 如果λ₂ 0存在另一个向量v使得Lv 0 且v ≠ (1,1,...,1) 由 xᵀLx ½Σᵢⱼ Aᵢⱼ(xᵢ-xⱼ)² 0 必须所有相连节点对满足xᵢ xⱼ 如果网络连通 从任意节点出发都能到达所有其他节点 → 所有节点的x值必须相同 → v只能是(1,1,...,1) → 矛盾所以λ₂ 0 如果网络不连通有两个分量 可以令分量1中节点x1 分量2中节点x-1 → 这个向量也满足Lv 0 → λ₂ 0 结论 λ₂ 0 ⟺ 网络连通 λ₂越大 ⟺ 网络越难被分割 ⟺ 越鲁棒性质四特征向量揭示最优分割Cheeger不等式最重要的定理定义图的等分比Cheeger常数h h 最小化 |切割边数| / min(|左边节点|,|右边节点|) Cheeger不等式告诉我们 λ₂/2 ≤ h ≤ √(2λ₂) 含义 h ≈ λ₂第二小特征值 → λ₂直接反映了图最难被分割的程度 → 第二小特征向量给出近似最优分割 这就是为什么 特征向量 → 节点正负值 → 分割方案 这个方案接近最优性质五节点加权拉普拉斯的性质任小龙的创新——节点加权拉普拉斯Lw保留了所有好性质性质验证 1. Lw也是半正定的 xᵀLwx ½ Σᵢⱼ Aᵢⱼ(wᵢwⱼ-1)(xᵢ-xⱼ)² 当所有wᵢ ≥ ½时这个值 ≥ 0 ✓ 2. Lw的第一特征值也是0 取v(1,1,...,1) Lwv的第i个元素 Σⱼ Bᵢⱼ - Σⱼ Bᵢⱼ × 1 0 ✓ 3. 第二小特征向量给出代价最优分割 这是任小龙最重要的理论贡献 通过Courant-Fisher定理证明 ✓ 额外性质任小龙证明的 λₙ ≤ 6d²_max所有特征值有上界 → 这保证了幂迭代算法的收敛速度总结四个问题的答案问题1为什么用拉普拉斯矩阵 → 它天然描述图分割问题 → 特征向量给出最优切割 → 可以自然融入代价信息加权版 → 有严格数学保证 问题2拉普拉斯矩阵的物理意义 → 热传导描述热量流动方向 → 随机游走描述蚂蚁行走的瓶颈 → 弹簧振动描述系统自然振动模式 → 电路网络描述电流流动规律 → 本质描述网络上任何流动现象 问题3什么时候用拉普拉斯 → 分割/聚类问题 ✓ → 流动/传播问题 ✓ → 连通性/鲁棒性问题 ✓ → 代价最优化问题 ✓ 问题4性质怎么得到的 → λ₁0全1向量是零特征向量直接计算 → 所有λ≥0xᵀLx½Σ(xᵢ-xⱼ)²≥0代数恒等式 → λ₂0⟺连通零空间维数连通分量数 → 最优分割Cheeger不等式拓扑学代数 → 加权版保留所有性质任小龙2019年证明第五步用具体数字手算一遍简单网络一条链A --- B --- C --- D邻接矩阵A B C D A [ 0 1 0 0 ] B [ 1 0 1 0 ] C [ 0 1 0 1 ] D [ 0 0 1 0 ]度矩阵A B C D A [ 1 0 0 0 ] B [ 0 2 0 0 ] C [ 0 0 2 0 ] D [ 0 0 0 1 ]拉普拉斯矩阵 L D - AA B C D A [ 1 -1 0 0 ] B [ -1 2 -1 0 ] C [ 0 -1 2 -1 ] D [ 0 0 -1 1 ]第二小特征向量近似值v⁽²⁾ ≈ (-0.60, -0.37, 0.37, 0.60) A: -0.60负 B: -0.37负 C: 0.37正 D: 0.60正如何解读负值节点A, B一组 正值节点C, D另一组 边界在哪B和C之间 → 删掉B或C就能切断网络 B和C的度数 B的度 2 C的度 2 两者代价相同随机选一个删掉即可 → 比如删C → 网络变成 A-B 和 D两个小块第六步加入代价——节点加权拉普拉斯这是GND最核心的创新假设节点代价不同同样是 A --- B --- C --- D 但现在 w_A 1便宜 w_B 5贵 w_C 1便宜 w_D 1便宜构建加权矩阵BBAWWA−A注意A→邻接矩阵W→代价矩阵是对角矩阵其中W是对角矩阵 A B C D W diag(1, 5, 1, 1) 计算B的元素 Bᵢⱼ Aᵢⱼ × (wᵢ wⱼ - 1) B_AB A_AB × (w_A w_B - 1) 1 × (15-1) 5 B_BC A_BC × (w_B w_C - 1) 1 × (51-1) 5 B_CD A_CD × (w_C w_D - 1) 1 × (11-1) 1含义B_AB 5切断A-B这条边代价5因为B很贵 B_BC 5切断B-C这条边代价5因为B很贵 B_CD 1切断C-D这条边代价1C和D都便宜 → 算法自然会选择切C-D → 代价只有1而不是5节点加权拉普拉斯矩阵LwD_B−BD_B是B的度矩阵对角元素为B的行和 计算D_B的对角元素 D_B(A,A) B_AB 5 D_B(B,B) B_AB B_BC 55 10 D_B(C,C) B_BC B_CD 51 6 D_B(D,D) B_CD 1 所以Lw A B C D A [ 5 -5 0 0 ] B [ -5 10 -5 0 ] C [ 0 -5 6 -1 ] D [ 0 0 -1 1 ]第二小特征向量近似v⁽²⁾ ≈ (-0.20, -0.15, 0.50, 0.85) 负值A(-0.20), B(-0.15) 正值C(0.50), D(0.85) 边界仍在B和C之间 但现在 B的代价5贵 → GND选择删C代价1而不是B 普通拉普拉斯可能选B度数角度最优 加权拉普拉斯选C代价角度最优✓第七步谱近似算法——怎么高效计算特征向量对于大型网络百万节点直接计算特征向量太慢。GND用了一个幂迭代的技巧核心思想构造矩阵 L̃ 6d²_max × I - Lw 其中 d_max 网络中最大的度数 I 单位矩阵 L̃和Lw有相同的特征向量 但特征值顺序翻转了 → Lw的第二小特征向量 L̃的第二大特征向量幂迭代步骤Step 1随机生成向量v 从单位球面上均匀采样 Step 2正交化 v v - (v₁ᵀv/v₁ᵀv₁) × v₁ 去掉第一特征向量的分量 Step 3反复乘以L̃ v L̃v / ||L̃v|| 重复k O(log N)次 Step 4收敛 v ≈ v⁽²⁾第二小特征向量为什么这样做有效把v展开在特征向量基底上 v Σᵢ ψᵢ v⁽ⁱ⁾ 每次乘以L̃ → 第二大特征值对应的分量增长最快 → 其他分量相对缩小 → 经过k次后 → v几乎完全是v⁽²⁾的方向 收敛速度指数级 只需要 k O(log N) 次迭代 总复杂度O(N log²N)第八步完整的GND流程图后续算法又提出了一个加权顶点覆盖的算法去找出具体哪些节点被移除它的成本代价是最小的那通过迭代的去计算这四个步骤之后我们会我们会得到这个图里面会移除这三个红色节点。输入网络G节点代价w ↓ 构建邻接矩阵A和代价矩阵W ↓ 计算加权矩阵B AW WA - A ↓ 构建节点加权拉普拉斯 Lw Dв - B ↓ 用幂迭代计算第二小特征向量 v⁽²⁾ ↓ 根据v⁽²⁾把节点分成两组 正值组M和负值组M̄ ↓ 精调用加权顶点覆盖 找边界上代价最小的节点删除 ↓ 删掉选中的节点 ↓ 检查每个子网络是否足够小 ↓是 ↓否 完成 对每个子网络 输出删除集合 递归重复上述步骤第九步用一句话理解每个数学工具邻接矩阵A → 记录网络谁和谁相连 度矩阵D → 记录每个节点有几个邻居 普通拉普拉斯L D-A → 描述网络结构的矩阵 → 特征向量揭示最自然的分割方式 代价矩阵W → 记录删掉每个节点要花多少钱 加权矩阵B AWWA-A → 把代价信息编码进网络结构 节点加权拉普拉斯Lw → 同时考虑网络结构和删除代价的矩阵 第二小特征向量v⁽²⁾ → 告诉我们怎么用最小代价把网络切成两半 幂迭代 → 快速近似计算特征向量的算法 → O(N log²N)复杂度可处理百万节点网络总结为什么谱方法这么强大传统算法BPD/CI/Min-Sum 逐个节点判断该不该删 → 局部视角 → 不考虑代价 GND谱方法 用矩阵一次性捕捉整个网络结构 → 全局视角 → 通过加权拉普拉斯自然融入代价信息 → 特征向量给出全局最优分割方案 本质 把网络瓦解问题转化为 线性代数中的特征值问题 借助数学的力量找到最优解扩展理解划分界限M1与M2M1中vi1,M2中vj-1←是通过加权拉普拉斯矩阵的第二最小特征向量得到的。利用公式2可以得出判断vi与vj是否在同一个M中同1不同-1。在不同M中可认为需要花费的代价为0→得到对移除节点成本代价的计算。可以利用节点VI和VJ的属性将所有的边总切割成本写成一个求和公式然后都变成了一个最小化切割成本的优化问题。对于4得到的G*又提出了一个加权顶点覆盖的算法去找出具体哪些节点被移除它的成本代价是最小的那通过迭代的去计算这四个步骤之后我们会我们会得到这个图里面会移除这三个红色节点。d_i残余度收益 这个节点手上握着多少条跨边。 例小明连接 3 条跨边删掉小明直接断掉 3 条跨边收益 3。 w_i权重成本 把这个节点删掉要付出多大代价。 例小明是大佬删他成本是 10小红是普通人删她成本是 2。 比值 w_i/d_i性价比删这个节点花的成本/能断掉多少条跨边【该节点的全部度/该节点的跨界边的度】。 代表断掉 1 条跨边平均要花多少钱。 这个数字越小性价比越高 它在 GND 大算法里面干什么 1、GND 先用谱聚类把网络最大连通块劈成两大块。 2、两块之间有一堆跨边拿这些跨边生成一个小的子图。 3、调用 WVC 加权节点覆盖算出删哪些点最小代价把两块之间全部联系切断。 是一种贪心算法 贪心只看当下局部最优看不到全局很容易出现 为了切断跨边删掉了一批其实根本不需要删的节点。 4、把这批点真正从原网络删掉。 5、剩下的网络重复整套流程一直拆到网络碎成足够小的碎片。移除了这三个红色节点之后我们再进行迭代的去计算网络中的GCC的大小。如果说达到拆解阈值的话会执行重插入算法。如果说没有达到拆解阈值的话我们会返回第一步然后再重新计算更新之后的网络然后进行一步一步的迭代直到我们的GCC的大小达到小于目标拆解小于这个阈值。非单位成本相关A移除成本一致时,M-S与GND的GCC大小CM-S的原理→高成本节点DGND的原理→中等程度成本的节点注意GND 是贪心近似算法会出现「过度删除」重插入就是修正这个贪心带来的副作用。注意由于知道GND是一种贪心算法 故需要重插入修正一下重插入reinsertionGNDR 就是 GND 重插入优化GND 算法一开始贪心删掉一批节点。重插入把部分之前删掉的节点试着重新放回网络里面看会不会坏事。如果放回之后最大连通分量 GCC 大小没有变大那就保留这个节点不再删除它。中间图例子橙色方块算法第一轮算出来准备要删掉的节点。红色菱形框这 4 个节点虽然算法一开始标记要删但是实验发现把它们放回去网络最大连通块不会重新长到很大。那我们就把这 4 个节点重插入放回原图不用删除了。为什么要干这件事WVC 加权顶点覆盖是贪心近似算法。 贪心有缺陷为了切断跨边会 “过度删除”—— 删掉了一些其实没必要删的节点。本来删 10 个点就够拆碎网络贪心算法一不小心删了 14 个多删了 4 个。 重插入就是做后处理优化把多删的捡回来。放回后最大连通分量 GCC 没有变大 → 这个节点是多余删掉的可以保留。放回后GCC 一下子变大网络又连起来了 → 这个节点真的必须删不能放回来。曲线图红色GND不带重插入黑色GNDRGND Re‑insertion 重插入横轴拆解成本花多大代价删节点越往右删除总代价越高 纵轴GCC size最大连通分量占比越往下代表网络拆得越碎效果越好。相同拆解成本同一个横坐标红色 GND 曲线在更下面GNDR 黑色在上方。 含义 同样花这么多删除成本GNDR 重插入之后不需要删那么多节点就能达到差不多拆解效果或者说想要拆到同样碎度GNDR 花费的总删除代价更小。GND 直接一股脑删掉很多节点GNDR 做完 GND再把 “删了也白删” 的节点捡回来降低整体删除成本算法性能得到提升。【虽然GND的效果比GNDR的效果好 但是没必要 GNDR同样可以和M-S以及EGP等达到同样近似的效果】完整 GNDR 流程运行原始 GND 算法得到一份待删除节点集合S。重插入后处理阶段遍历集合S里每一个被删掉的节点。尝试把这个节点放回网络计算放回之后最大连通分量 GCC 的大小。✅放回后 GCC 没有明显变大真正重插入这个节点不再删除把它从删除集合S剔除。❌放回后 GCC 暴涨网络重新连通不能恢复这个节点继续保持删除。全部节点尝试完毕输出精简后的删除集合这就是 GNDR。注意这里要尝试所有节点会花费对应的很多时间结果补充在不同策略下需要删除的节点不一样