背景用生活举例来理解想象一下电网全国的城市通过电线连接在一起。如果敌人想让全国大范围停电他们应该炸掉哪几个关键的变电站这就是这篇论文要解决的问题最少删掉哪些节点能让整个网络瘫痪核心概念什么是网络在这篇论文里网络不是指互联网而是一个数学概念节点Node 网络中的点比如城市、人、网页、蛋白质链接Link 节点之间的连线比如公路、好友关系、超链接举个具体例子微信好友网络每个人是一个节点两人互为好友就连一条线航空网络每个机场是节点有航班的两个机场之间连线论文的核心问题给你一个网络找出最少的节点删掉它们之后网络就碎成很多小块不再连通。这些被删掉的节点叫做**攻击目标**。一、为什么这个问题很难1、先用生活例子感受一下难在哪里假设一个小网络只有5个节点你要找出删掉哪些节点能让网络瘫痪。你可以一个一个试删节点1不行删节点2不行删节点12可以但是不是最少的……5个节点还好说但现实网络有几百万个节点比如论文里提到的一个互联网网络有170万个节点你根本没办法一个个试。2、NP-hard 是什么意思论文说这个问题是NP-hard这是计算机科学里的术语意思是目前世界上没有任何快速算法能保证找到最优解打个比方问题类型例子难度简单问题给1000个数排序电脑秒解NP-hard问题最优网络攻击即使超级计算机也可能需要宇宙年龄那么长时间所以科学家们退而求其次不追求最优解而是找近似最优解——也就是够好的答案。1、论文里的两个够好算法这篇论文主要比较两个算法CI算法集体影响算法 2015年 Morone和Makse提出 用局部信息判断哪个节点重要 BPD算法置信传播引导抽取算法 2013年 Zhou提出 用全局信息判断哪个节点重要 本文作者证明它更好2、一个关键比喻CI算法就像一个人站在某个路口只看周围几条街判断我这里重不重要。BPD算法就像一个人有整个城市的地图知道每条路和每个环路的全局结构判断更准确。二、网络里的环——理解BPD的关键1、什么是环用图来理解最直观树从任意一点出发只有一条路能到另一点有环的网络从一点出发可以绕圈回到原点2、为什么环这么重要想象一下网络是一座城市的道路没有环的情况树形结构北京 | 天津 | 济南如果你切断北京-天津这条路天津和济南就完全孤立了。切一刀就够有环的情况北京 / \ 天津 石家庄 \ / 济南就算你切断北京-天津还可以走北京→石家庄→济南→天津。必须多切几刀结论网络里的环让网络变得更韧更难被破坏3、论文的核心洞察作者发现要让网络瘫痪关键就是把所有的环都切断为什么在稀疏网络里链接不太多的网络小的连通块基本上都是树形结构没有环。而大的连通块巨型连通分量之所以大是因为它里面有大量的环把所有节点连在一起。所以切断所有环 → 大块碎成小树 → 网络瘫痪4、由此引出一个新问题FVS问题这就是论文里提到的 **反馈顶点集Feedback Vertex SetFVS**问题找出最少的节点删掉它们之后网络里一个环都不剩其中FVS节点就是去掉后总体可以变成 环 的节点这等价于把网络变成一片森林很多棵树删掉FVS节点前 删掉FVS节点后 有很多环的大网络 → 很多小树没有环5、BPD算法的思路就清晰了第一步找到FVS反馈顶点集 ↓ 第二步删掉这些节点切断所有环 ↓ 第三步网络碎成很多小树 ↓ 第四步如果某棵树还太大再删一两个节点 ↓ 网络彻底瘫痪小结三个关键词的关系环Loop ↓ 切断所有环 反馈顶点集 FVS ↓ 用来解决 网络最优攻击问题三.BPD算法是怎么工作的1.先理解算法的总体思路BPD算法的核心问题是网络里有那么多节点我怎么知道哪个节点对环的贡献最大应该优先删掉BPD的答案是给每个节点打一个应该被删掉的概率分数然后优先删分数最高的。2.用投票来理解置信传播置信传播Belief PropagationBP是BPD里最核心的机制。用一个投票的比喻来理解场景公司裁员公司要裁掉最可有可无的员工。但HR不了解每个人所以让每个员工互相评价员工A问员工B如果我不在了你觉得你自己还重要吗 员工B回答A同时也去问员工C同样的问题 员工C回答B……每个人根据邻居的回答来判断自己有多重要然后把这个判断再传给别的邻居。反复传递几轮之后每个人都能得到一个比较准确的重要性分数。这就是置信传播——在网络里传递信息直到信息稳定下来。3.BPD的具体步骤步骤一初始化【先赋予节点两种概率】网络里每个节点i先给它两个初始概率 - q⁰ᵢ 节点i适合被删掉的概率 - qⁱᵢ 节点i适合作为树根的概率这两个概率一开始是随机猜的不准确没关系后面会越来越准。步骤二传递消息BP方程【节点向邻居发送信息】每个节点i向它的每个邻居j发送两条消息消息1q⁰ᵢ→ⱼ 假设你j不存在我i被删掉的概率 消息2qⁱᵢ→ⱼ 假设你j不存在我i作为树根的概率这对应论文里的公式(3a)和(3b)但我们不用记公式只需要理解本质每个节点都在问邻居如果我消失了你会怎样然后根据邻居的回答更新自己的重要性。步骤三反复迭代直到稳定第1轮每个节点根据邻居信息更新自己的概率 第2轮再次更新…… 第3轮再次更新…… …… 直到所有概率不再变化 → 收敛就像投票一样经过几轮讨论后大家的意见趋于一致。步骤四删掉概率最高的节点收敛之后找出q⁰ᵢ 最大的节点【 节点i适合被删掉的概率】也就是最应该被删掉的节点把它删掉。删掉节点 → 网络结构变了 → 重新运行BP方程 → 找下一个删掉的节点反复循环直到所有环都被切断。5.用一个完整的比喻总结想象你要找出桥梁网络里最关键的桥炸掉最少的桥让城市交通瘫痪1. 每座桥问周围的桥如果我塌了你还重要吗 ↓ 2. 周围的桥根据自己的情况回答同时也去问它们的邻居 ↓ 3. 经过几轮传话每座桥都知道自己有多关键 ↓ 4. 最关键的桥被炸掉 ↓ 5. 重新评估剩余桥梁的重要性 ↓ 6. 再炸掉最关键的……直到交通瘫痪6.BPD里的神秘参数 x论文里BPD有一个参数x 12这是干什么的简单理解者通过实验发现 x 12 效果最好就固定用这个值了。7.BPD为什么比CI聪明CI算法BPD算法看的范围只看节点周围几步以内通过消息传递考虑整个网络关注什么节点的影响力节点对环的贡献信息量局部信息全局信息结果质量较差接近理论最优8.小结BPD算法 置信传播找关键节点 逐步删除decimation 核心思想 让网络里的节点互相传递消息 → 每个节点都能估计自己对环的重要性 → 优先删掉最重要的节点 → 重复直到所有环消失四.核心原理和公式 第一步从最简单的问题开始假设网络里只有3个节点连成一个三角形A / \ B - C这个三角形就是一个环现在问题是删掉哪个节点能用最少的代价切断这个环答案很简单删A、或删B、或删C随便删一个都行因为删掉任意一个节点三角形就断了。但是在复杂网络里有成千上万个环交织在一起就没这么简单了。第二步理解概率的意义BPD给每个节点打两个分数q⁰ᵢ 节点i应该被删掉的概率 qⁱᵢ 节点i应该留下来当树根的概率为什么要这两个概率因为每个节点只有两种命运命运1被删掉加入攻击目标集合S→ 用q⁰表示 命运2留下来成为某棵小树的一部分→ 用qⁱ表示第三步理解消息传递的本质这是最关键的部分先看一个极简例子只有两个节点A和B用一条线连着A ——— B现在A想知道我应不应该被删掉A的想法是我要不要被删取决于B。如果B很重要那我可以被删如果B不重要那我得留下来。所以A先问B假设我A不存在你B自己重要吗B回答A这个问题就是一条消息q⁰_B→A 假设A不存在B应该被删掉的概率 qⁱ_B→A 假设A不存在B应该留下当树根的概率A收到B的回答之后就能更好地判断自己该不该被删了。这些是需要告诉给A的信息第四步现在来看公式(3a)和(3b)论文里的BP方程不要被吓到我们逐个拆解公式(3a)节点i告诉j 我应该被删掉的概率这个公式说的是i告诉j假设你j不存在我i被删掉的概率为什么这么简单因为如果j不存在 → i和j之间的链接消失 → i只需要考虑其他邻居 → 被删掉的概率就是一个基础值 1/zz是归一化常数让概率加起来1公式(3b)节点i告诉j 我应该留下当树根的概率我们把这个公式拆成几个部分部分1∂i\j∂i 节点i的所有邻居 ∂i\j 节点i的所有邻居但去掉j 举例 如果i的邻居是 {A, B, C, j} 那么 ∂i\j {A, B, C}部分2这是邻居k发给i的两个概率之和 - q⁰_k→i k被删掉的概率 - qᵏ_k→i k留下当树根的概率 两个加起来 k处理好了自己的概率 要么被删要么当树根反正不会造成麻烦部分3部分4x是可调参数论文里取x12 e^x是一个放大系数 x越大留下来当树根的概率被放大得越多 → 算法越倾向于删节点而不是留节点整个公式(3b)的意思i告诉j假设你j不存在我i留下来当树根的概率 我所有其他邻居都安排好自己之后我还有余力当树根的概率第五步理解公式(2)——最终打分这个公式看起来最复杂但核心意思很简单收集所有邻居发来的消息综合计算节点i最终应该被删掉的概率我们只需要理解分母里的逻辑分母越大 → q⁰ᵢ 越小 → i不太应该被删 分母越小 → q⁰ᵢ 越大 → i很应该被删什么时候分母小i应该被删当 ∏[q⁰_j→i qʲ_j→i] 很小的时候 翻译当i的邻居们很难自己处理好自己的时候 → 说明i对这些邻居很重要 → i参与了很多环 → i应该被删掉第六步用一个完整小例子走一遍假设这个网络A /|\ B--C \|/ DA和B、C、D都相连B-C、C-D、D-B也相连有很多环。直觉上A在中间参与了最多的环应该优先删A。BPD是怎么得出这个结论的第1轮消息传递 - B问A假设C不存在你A重要吗 → A回答 - C问A假设B不存在你A重要吗 → A回答 - D问A假设B不存在你A重要吗 → A回答 - ……所有邻居互相问 第2轮根据收到的回答更新自己的判断再传出去 第3轮、第4轮……直到稳定 最终结果 - A的q⁰_A 最大比如0.85→ A最应该被删 - B的q⁰_B 较小比如0.4 - C的q⁰_C 较小比如0.4 - D的q⁰_D 较小比如0.4 → 删掉A → 重新计算剩余节点的概率 → 继续删……第七步整个BPD算法流程图开始 ↓ 对当前网络运行BP方程(3) 让消息在网络里传播直到收敛 ↓ 用公式(2)计算每个节点的 q⁰ᵢ ↓ 找出 q⁰ᵢ 最大的节点 实际上每次删一小批比如1%的节点 ↓ 删掉这些节点和它们的链接 ↓ 检查网络里还有环吗 ↓ ↓ 有环 没有环了 ↓ ↓ 回到第一步 检查剩余小树是否太大 ↓ ↓ 太大 都很小 ↓ ↓ 再删几个节点 完成输出攻击目标集合S最终总结用一句话记住BPDBPD 让网络里所有节点互相通风报信每个节点根据邻居的情报判断自己对环有多重要最重要的先删删完再重新通风报信直到所有环消失。五.实验结果——BPD到底比CI好多少先回顾一下评判标准论文用一个指标来衡量算法好坏ρrho 需要删掉的节点数 ÷ 网络总节点数 ρ越小 算法越好 用更少的节点就能让网络瘫痪目标是让最大连通块的相对大小≤ 0.01也就是最大剩余块不超过总网络的1%。实验一随机网络ER网络和RR网络什么是ER网络和RR网络ER网络Erdős-Rényi随机网络 → 每对节点之间随机连线 → 节点的连线数度参差不齐 → 用参数 c 表示平均每个节点有几条连线 RR网络随机正则网络 → 每个节点的连线数完全相同 → 更加均匀 → 用参数 K 表示每个节点有几条连线实验结果对应论文图4ER网络c10时CI算法需要删掉52% 的节点 BPD算法只需要48% 的节点 BPD少删了约 4% RR网络差距更大CI算法远超理论最小值 BPD算法几乎贴近理论最小值用图来理解理论最小值 ████████░░░░░░░░░░░░ 理想情况BPD结果 ████████▓░░░░░░░░░░░ 非常接近理想CI结果 ████████████░░░░░░░░ 差很多█ 必须删的节点▓ BPD多删的很少░ 不用删的节点实验二无标度网络Scale-Free网络什么是无标度网络现实世界很多网络都是无标度网络 - 互联网少数网站百度、谷歌有海量链接 - 社交网络少数人明星、网红有海量粉丝 - 航空网络少数机场北京、上海有海量航线 特点 少数节点Hub节点连线极多 大多数节点连线很少 用参数 γ 描述这种不均匀程度 γ越小 → Hub节点越突出实验结果对应论文图5γ3.0c10时CI算法需要删掉36.6% 的节点 BPD算法只需要33.8% 的节点 BPD又赢了为什么无标度网络相对容易攻击普通网络 无标度网络 ○-○-○-○-○ ○ ○-○-○-○-○ ○--Hub--○ ○-○-○-○-○ ○ 每个节点差不多 Hub连着所有人 攻击无标度网络优先删Hub节点 → 一个Hub倒下大片节点孤立 → 比普通网络容易瘫痪实验三真实世界网络最重要论文测试了12个真实网络包括基础设施网络 - RoadEU - 欧洲公路网1177个节点 - RoadTX - 德克萨斯公路网137万个节点 - Grid - 美国西部电网4941个节点 - IntNet2 - 互联网170万个节点 社交网络 - Friend - 在线友谊网络19万个节点 - Authors - 论文合著网络2.3万个节点 信息网络 - WebPage - 谷歌网页网络87万个节点 - Email - 欧洲邮件网络26万个节点 ……等等最震撼的结果对比互联网 IntNet2170万节点CI算法需要攻击 144,160 个节点 BPD算法只需要 73,229 个节点 BPD只用了CI一半的节点就完成任务电网 GridCI算法需要攻击 476 个节点 BPD算法只需要 320 个节点 节省了33%邮件网络 EmailCI算法需要攻击 21,465 个节点 BPD算法只需要 1,064 个节点 BPD只用了CI的 5%差距极其悬殊实验四最有趣的发现——突然崩溃现象这是论文里最令人惊讶的发现CI算法攻击过程图1中的虚线网络大小 100% |▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 80% |░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓ 60% |░░░░░░░░░░░░▓▓▓▓▓▓▓▓ 40% |░░░░░░░░░░░░░░░░▓▓▓▓ 20% |░░░░░░░░░░░░░░░░░░░░ 0% |____________________ 0% 5% 10% 15% 20% 删掉的节点比例 ▓ 剩余最大连通块 特点网络缓慢、平稳地缩小BPD算法攻击过程图1中的实线网络大小 100% |▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 80% |░░░░░░░░░░░▓▓▓▓ 60% |░░░░░░░░░░░░▓▓▓ 40% |░░░░░░░░░░░░░▓▓ 20% |░░░░░░░░░░░░░░▓ 0% |░░░░░░░░░░░░░░░▓← 突然瞬间归零 0% 5% 10% 13.7% 删掉的节点比例 特点网络长时间保持完整 然后在13.7%时突然崩溃为什么会突然崩溃这和BPD的工作原理有关BPD的目标是切断环不是缩小网络 所以攻击过程中 前期BPD专注切断环网络看起来还很完整 但其实网络内部的骨架在不断被破坏 某个临界点最后一个关键环被切断 → 网络失去支撑 → 轰然崩塌就像这个比喻CI攻击 慢慢拆砖头房子慢慢变小 BPD攻击 专门锯承重柱房子表面看起来没变 锯断最后一根承重柱 → 整栋楼瞬间倒塌这个突然崩溃有什么实际意义论文特别提到这一点有非常重要的现实警示意义对于防御方来说 CI攻击 网络慢慢变小 → 防御方能观察到异常 → 有时间反应和修复 BPD攻击 网络长时间看起来正常 → 防御方毫无察觉 → 突然整个网络崩溃 → 根本来不及反应作者在论文里警告如果恐怖分子或敌对势力掌握了BPD算法对电网、互联网、交通网络发动攻击防御方将极难察觉等发现时已经太晚了。实验五算法速度对比BPD不仅结果更好速度也很快BPD的运行时间 ∝ N × ln(N) 这叫做近似线性时间复杂度 含义 节点数翻倍 → 运行时间只增加一点点 实际表现 N 2亿个节点的网络 BPD只需要 23.5小时 就能找到攻击方案对比BPD结果好 速度快 ✓✓ CI 结果差 速度差 ✗✗本课总结实验结论 1. 随机网络上BPD比CI少删 4%-10% 的节点 2. 真实网络上BPD有时只需CI的 5% 的节点 3. BPD的结果非常接近理论最优值 4. BPD攻击会造成突然崩溃防御方难以察觉 5. BPD速度快可以处理超大网络亿级节点六.论文的核心结论论文最终说了三件事结论1BPD算法在所有类型网络上都远优于CI算法 结论2BPD造成的突然崩溃是一种危险的攻击模式 社会需要认真对待这种潜在威胁 结论3BPD算法可以推广到非均匀攻击成本的情况 现实中删掉不同节点的代价是不同的七.全部关键词详解我们把论文里所有重要词汇分成六个类别来解释【第一类】网络基础概念① Node节点定义网络中的基本单元用点表示 现实例子 - 社交网络中 → 每个人 - 互联网中 → 每台服务器 - 电网中 → 每个变电站 - 大脑神经网络→ 每个神经元② Link / Edge链接/边定义两个节点之间的连线表示它们有某种关系 现实例子 - 社交网络中 → 两人是好友 - 互联网中 → 两台服务器之间有数据传输 - 电网中 → 两个变电站之间有电线相连③ Degree度定义一个节点连接的链接数量也就是它有几个邻居 举例 A /|\ B C D A的度 3连着B、C、D B的度 1只连着A 度大的节点 Hub节点 枢纽节点④ Giant Connected Component巨型连通分量定义网络中最大的那个连通块 连通的意思 从这个块里任意一个节点出发 都能通过链接走到这个块里其他任何节点 举例 删节点前 删节点后 一个大块90%节点 → 很多小块每块1%节点 让巨型连通分量消失 网络瘫痪注意是其他任意节点沃⑤ Loop / Cycle环/回路定义从一个节点出发沿着链接走能回到原点的路径 有环A-B-C-A三角形 A-B-C-D-A正方形 无环树 A / \ B C / \ D E 环的重要性 环越多 → 网络越韧 → 越难被攻击破坏⑥ Sparse Network稀疏网络定义链接数量M 和 节点数量N 差不多大的网络 也就是每个节点平均只有几条链接 对比 稀疏网络M ≈ N 每人平均认识3-5人 稠密网络M ≈ N² 每人几乎认识所有人 现实中大多数大型网络都是稀疏网络 互联网、社交网络、电网等⑦ Clustering Coefficient聚类系数定义衡量网络中三角形有多少的指标 直觉理解 你的朋友们互相认识的程度 聚类系数高 → 朋友的朋友也是你朋友三角形多 聚类系数低 → 朋友圈互相不认识 真实网络的聚类系数通常比随机网络高得多【第二类】网络类型⑧ Erdős-Rényi NetworkER网络定义最简单的随机网络模型 生成方式 N个节点任意两个节点之间 以固定概率p随机连一条线 特点 - 大多数节点的度差不多比较均匀 - 度的分布接近正态分布钟形曲线 - 是理论研究的基准网络 参数 c 平均每个节点的度⑨ Regular Random NetworkRR网络随机正则网络定义每个节点的度完全相同的随机网络 举例 K3的RR网络每个节点恰好有3条链接 特点 - 比ER网络更均匀 - 数学上更容易分析 - 现实中较少见主要用于理论研究 参数 K 每个节点的度⑩ Scale-Free Network无标度网络定义度分布符合幂律分布的网络 幂律分布是什么 度为d的节点数量 ∝ d^(-γ) 直觉理解 极少数节点Hub有极多连接 大多数节点只有很少连接 就像财富分布 极少数富人拥有大部分财富 大多数人只有很少财富 现实例子 - 互联网少数网站有海量链接 - 社交网络少数明星有海量粉丝 - 论文引用网络少数论文被大量引用 参数 γ 幂律指数 γ越小 → Hub节点越突出 → 网络越不均匀⑪ Hub节点定义无标度网络中度极大的节点 举例 - 互联网中的百度、谷歌 - 社交网络中的明星账号 - 航空网络中的北京、上海机场 攻击意义 优先攻击Hub节点效果最好 删掉一个Hub → 大量节点失去连接【第三类】优化问题⑫ NP-hard非确定性多项式难定义计算机科学中最难的一类问题 通俗理解 目前没有任何已知算法能在合理时间内 保证找到最优解 时间复杂度对比 简单问题时间 ∝ N线性或 N²多项式 NP-hard时间 ∝ 2^N指数爆炸 举例 N10 2^10 1024 → 还行 N100 2^100 ≈ 10^30 → 超级计算机也算不完 N10002^1000 ≈ 10^300 → 比宇宙年龄还长 所以对NP-hard问题我们只能找够好的近似解⑬ Feedback Vertex SetFVS反馈顶点集定义删掉这些节点后网络中一个环都不剩 反馈的含义 环 信号能反馈回来的路径 切断所有反馈 删掉FVS 最小FVS 节点数量最少的FVS 用最少的代价切断所有环 与网络攻击的关系 在稀疏网络中 最小FVS ≈ 最优攻击目标集合 所以解决FVS问题 ≈ 解决网络攻击问题⑭ Heuristic Algorithm启发式算法定义不保证找到最优解但能快速找到够好解的算法 为什么用启发式算法 因为最优解问题是NP-hard太难了 退而求其次找近似最优解 本论文中的启发式算法 - CI算法较差的启发式 - BPD算法较好的启发式 衡量标准 找到的解 离 理论最优解 有多近 BPD非常近误差1% CI相差很远误差20%⑮ Targeted Attack SetTAS目标攻击集合定义需要被删掉的节点集合 衡量指标 ρ |TAS| ÷ N 被删节点数 ÷ 总节点数 ρ越小 → 攻击越高效 论文结果 BPD的ρ 远小于 CI的ρ 在某些网络上BPD的ρ只有CI的ρ的5%【第四类】算法相关⑯ Belief PropagationBP置信传播定义一种在网络上传递概率信息的算法 核心思想 每个节点把自己的信念概率估计 传递给邻居节点 邻居收到后更新自己的信念 再传递给下一个邻居 ……直到所有节点的信念稳定不变 类比 八卦在朋友圈里传播 每个人听到八卦后更新自己的判断 然后告诉其他朋友 最终大家的判断趋于一致 数学上 BP方程 论文里的公式(3a)(3b) 收敛后用公式(2)计算最终概率⑰ Decimation抽取/逐步删除定义每次删掉一小批节点然后重新计算的策略 为什么不一次性删掉所有高分节点 因为删掉一个节点后网络结构改变了 其他节点的重要性也随之改变 所以要 删一批比如1%的节点→ 重新计算 → 再删一批 → …… 参数 f 每次删掉的节点比例 论文中 f 0.01每次删1%⑱ Collective Information AlgorithmCI算法集体影响算法定义2015年Morone和Makse提出的网络攻击算法 核心思想 给每个节点计算一个影响力分数 分数 节点自身的传播能力 × 以节点为中心半径l范围内边界节点的传播能力 公式 CI_l(i) (度_i - 1) × Σ(度_j - 1) j在i周围距离l的位置 参数 l 考虑的半径范围论文中l4 缺点 只看局部信息半径l以内 忽略了全局的环结构 所以效果比BPD差很多⑲ Re-weighting Parameter x重加权参数定义BPD算法中控制激进程度的参数 作用 x大 → 算法更倾向于删节点 x小 → 算法更倾向于保留节点 论文中 ER网络用 x 12 RR网络用 x 7 x出现在公式里的位置 e^x × (其他项) x越大e^x越大删节点的倾向越强⑳ Time Complexity时间复杂度定义算法运行时间随网络规模增长的速度 BPD的时间复杂度 T ∝ N × ln(N) 这意味着 N 100万节点 → 算几分钟 N 1亿节点 → 算几小时 N 2亿节点 → 约23.5小时 CI的时间复杂度 和BPD差不多但结果质量差很多 为什么近线性很重要 现实网络动辄百万、千万节点 只有近线性算法才能处理这种规模【第五类】物理学概念㉑ Spin Glass自旋玻璃定义统计物理学中的一种无序磁性系统 物理含义 铁磁体中每个原子有一个自旋方向 自旋玻璃中这些方向是随机无序的 相互作用又复杂又矛盾 为什么和网络攻击有关 Zhou2013发现 FVS问题 可以 完美映射到 自旋玻璃模型 每个网络节点 → 一个自旋 节点的状态删/留 → 自旋的方向上/下 最小FVS → 自旋玻璃的基态最低能量状态 这个映射让我们可以用物理学工具解决网络问题㉒ Replica-Symmetric Mean Field Theory复本对称平均场理论定义统计物理中分析自旋玻璃的数学工具 作用 可以计算出最小FVS的理论下界 也就是理论上最少需要删掉多少节点 论文中的用途 作为衡量算法好坏的基准线 结果 BPD的结果 非常接近 理论下界误差1% CI的结果 远离 理论下界误差20%㉓ Non-backtracking Matrix / Hashimoto Matrix非回溯矩阵/桥本矩阵定义描述网络中信号传播不走回头路的数学矩阵 在论文里出现在哪 论文最后提到 可以用这个矩阵的最大特征值 来区分有意攻击和随机故障 直觉理解 BPD攻击 → 特征值变化有特殊规律 随机故障 → 特征值变化没有规律 → 或许可以用来预警 注这是论文提出的未来研究方向尚未实现【第六类】结果描述㉔ Abrupt Collapse突然崩溃定义网络在BPD攻击下表现出的现象 长时间保持完整然后瞬间崩溃 类比 - 水坝长时间承压突然决堤 - 骨牌推倒第一块其余瞬间全倒 - 桥梁表面完好锯断承重柱后瞬间倒塌 数学上类似于 相变Phase Transition 水突然从液态变成气态 网络突然从连通变成碎片 危险性 防御方毫无预警 → 极难防御㉕ Explosive Percolation爆炸性渗流定义网络科学中的一种相变现象 系统在临界点附近发生极其剧烈的突变 论文中说BPD的突然崩溃 类似于爆炸性渗流现象 渗流理论的直觉 往沙子里倒水 水慢慢渗透 突然在某一刻贯通整个沙层 网络中 随着节点被删除 网络突然在某一刻完全碎裂㉖ ρrho相对大小定义目标攻击集合的相对大小 公式ρ 被删节点数 ÷ 总节点数 例子 网络有100万个节点 BPD需要删7万个 ρ_BPD 7万 ÷ 100万 0.07 7% CI需要删14万个 ρ_CI 14万 ÷ 100万 0.14 14% ρ越小越好㉗ θtheta阈值定义判断网络是否瘫痪的标准 论文中 θ 0.01 含义 当最大连通块的相对大小 ≤ 1% → 认为网络已经瘫痪 为什么是1% 如果最大剩余块只有1%的节点 这个块已经非常小无法正常运作 实际上已经没有意义了三、所有关键词的关系图网络基础 节点链接度 ↓ 形成各种网络类型 ER网络 / RR网络 / 无标度网络 ↓ 网络中存在环和巨型连通分量 ↓ 目标最优网络攻击问题 找最小目标攻击集合TAS使ρ最小 ↓ 问题是NP-hard只能用启发式算法 ↓ 关键洞察攻击问题 ≈ 最小FVS问题 ↓ 两种算法 CI算法局部信息效果差 BPD算法全局信息效果好 ↓ BPD基于 自旋玻璃理论 → 置信传播(BP) → 逐步删除(Decimation) ↓ BPD的结果 - ρ更小接近理论最优 - 速度快近线性时间复杂度 - 造成突然崩溃类似爆炸性渗流 BPD算法详解
背景用生活举例来理解想象一下电网全国的城市通过电线连接在一起。如果敌人想让全国大范围停电他们应该炸掉哪几个关键的变电站这就是这篇论文要解决的问题最少删掉哪些节点能让整个网络瘫痪核心概念什么是网络在这篇论文里网络不是指互联网而是一个数学概念节点Node 网络中的点比如城市、人、网页、蛋白质链接Link 节点之间的连线比如公路、好友关系、超链接举个具体例子微信好友网络每个人是一个节点两人互为好友就连一条线航空网络每个机场是节点有航班的两个机场之间连线论文的核心问题给你一个网络找出最少的节点删掉它们之后网络就碎成很多小块不再连通。这些被删掉的节点叫做**攻击目标**。一、为什么这个问题很难1、先用生活例子感受一下难在哪里假设一个小网络只有5个节点你要找出删掉哪些节点能让网络瘫痪。你可以一个一个试删节点1不行删节点2不行删节点12可以但是不是最少的……5个节点还好说但现实网络有几百万个节点比如论文里提到的一个互联网网络有170万个节点你根本没办法一个个试。2、NP-hard 是什么意思论文说这个问题是NP-hard这是计算机科学里的术语意思是目前世界上没有任何快速算法能保证找到最优解打个比方问题类型例子难度简单问题给1000个数排序电脑秒解NP-hard问题最优网络攻击即使超级计算机也可能需要宇宙年龄那么长时间所以科学家们退而求其次不追求最优解而是找近似最优解——也就是够好的答案。1、论文里的两个够好算法这篇论文主要比较两个算法CI算法集体影响算法 2015年 Morone和Makse提出 用局部信息判断哪个节点重要 BPD算法置信传播引导抽取算法 2013年 Zhou提出 用全局信息判断哪个节点重要 本文作者证明它更好2、一个关键比喻CI算法就像一个人站在某个路口只看周围几条街判断我这里重不重要。BPD算法就像一个人有整个城市的地图知道每条路和每个环路的全局结构判断更准确。二、网络里的环——理解BPD的关键1、什么是环用图来理解最直观树从任意一点出发只有一条路能到另一点有环的网络从一点出发可以绕圈回到原点2、为什么环这么重要想象一下网络是一座城市的道路没有环的情况树形结构北京 | 天津 | 济南如果你切断北京-天津这条路天津和济南就完全孤立了。切一刀就够有环的情况北京 / \ 天津 石家庄 \ / 济南就算你切断北京-天津还可以走北京→石家庄→济南→天津。必须多切几刀结论网络里的环让网络变得更韧更难被破坏3、论文的核心洞察作者发现要让网络瘫痪关键就是把所有的环都切断为什么在稀疏网络里链接不太多的网络小的连通块基本上都是树形结构没有环。而大的连通块巨型连通分量之所以大是因为它里面有大量的环把所有节点连在一起。所以切断所有环 → 大块碎成小树 → 网络瘫痪4、由此引出一个新问题FVS问题这就是论文里提到的 **反馈顶点集Feedback Vertex SetFVS**问题找出最少的节点删掉它们之后网络里一个环都不剩其中FVS节点就是去掉后总体可以变成 环 的节点这等价于把网络变成一片森林很多棵树删掉FVS节点前 删掉FVS节点后 有很多环的大网络 → 很多小树没有环5、BPD算法的思路就清晰了第一步找到FVS反馈顶点集 ↓ 第二步删掉这些节点切断所有环 ↓ 第三步网络碎成很多小树 ↓ 第四步如果某棵树还太大再删一两个节点 ↓ 网络彻底瘫痪小结三个关键词的关系环Loop ↓ 切断所有环 反馈顶点集 FVS ↓ 用来解决 网络最优攻击问题三.BPD算法是怎么工作的1.先理解算法的总体思路BPD算法的核心问题是网络里有那么多节点我怎么知道哪个节点对环的贡献最大应该优先删掉BPD的答案是给每个节点打一个应该被删掉的概率分数然后优先删分数最高的。2.用投票来理解置信传播置信传播Belief PropagationBP是BPD里最核心的机制。用一个投票的比喻来理解场景公司裁员公司要裁掉最可有可无的员工。但HR不了解每个人所以让每个员工互相评价员工A问员工B如果我不在了你觉得你自己还重要吗 员工B回答A同时也去问员工C同样的问题 员工C回答B……每个人根据邻居的回答来判断自己有多重要然后把这个判断再传给别的邻居。反复传递几轮之后每个人都能得到一个比较准确的重要性分数。这就是置信传播——在网络里传递信息直到信息稳定下来。3.BPD的具体步骤步骤一初始化【先赋予节点两种概率】网络里每个节点i先给它两个初始概率 - q⁰ᵢ 节点i适合被删掉的概率 - qⁱᵢ 节点i适合作为树根的概率这两个概率一开始是随机猜的不准确没关系后面会越来越准。步骤二传递消息BP方程【节点向邻居发送信息】每个节点i向它的每个邻居j发送两条消息消息1q⁰ᵢ→ⱼ 假设你j不存在我i被删掉的概率 消息2qⁱᵢ→ⱼ 假设你j不存在我i作为树根的概率这对应论文里的公式(3a)和(3b)但我们不用记公式只需要理解本质每个节点都在问邻居如果我消失了你会怎样然后根据邻居的回答更新自己的重要性。步骤三反复迭代直到稳定第1轮每个节点根据邻居信息更新自己的概率 第2轮再次更新…… 第3轮再次更新…… …… 直到所有概率不再变化 → 收敛就像投票一样经过几轮讨论后大家的意见趋于一致。步骤四删掉概率最高的节点收敛之后找出q⁰ᵢ 最大的节点【 节点i适合被删掉的概率】也就是最应该被删掉的节点把它删掉。删掉节点 → 网络结构变了 → 重新运行BP方程 → 找下一个删掉的节点反复循环直到所有环都被切断。5.用一个完整的比喻总结想象你要找出桥梁网络里最关键的桥炸掉最少的桥让城市交通瘫痪1. 每座桥问周围的桥如果我塌了你还重要吗 ↓ 2. 周围的桥根据自己的情况回答同时也去问它们的邻居 ↓ 3. 经过几轮传话每座桥都知道自己有多关键 ↓ 4. 最关键的桥被炸掉 ↓ 5. 重新评估剩余桥梁的重要性 ↓ 6. 再炸掉最关键的……直到交通瘫痪6.BPD里的神秘参数 x论文里BPD有一个参数x 12这是干什么的简单理解者通过实验发现 x 12 效果最好就固定用这个值了。7.BPD为什么比CI聪明CI算法BPD算法看的范围只看节点周围几步以内通过消息传递考虑整个网络关注什么节点的影响力节点对环的贡献信息量局部信息全局信息结果质量较差接近理论最优8.小结BPD算法 置信传播找关键节点 逐步删除decimation 核心思想 让网络里的节点互相传递消息 → 每个节点都能估计自己对环的重要性 → 优先删掉最重要的节点 → 重复直到所有环消失四.核心原理和公式 第一步从最简单的问题开始假设网络里只有3个节点连成一个三角形A / \ B - C这个三角形就是一个环现在问题是删掉哪个节点能用最少的代价切断这个环答案很简单删A、或删B、或删C随便删一个都行因为删掉任意一个节点三角形就断了。但是在复杂网络里有成千上万个环交织在一起就没这么简单了。第二步理解概率的意义BPD给每个节点打两个分数q⁰ᵢ 节点i应该被删掉的概率 qⁱᵢ 节点i应该留下来当树根的概率为什么要这两个概率因为每个节点只有两种命运命运1被删掉加入攻击目标集合S→ 用q⁰表示 命运2留下来成为某棵小树的一部分→ 用qⁱ表示第三步理解消息传递的本质这是最关键的部分先看一个极简例子只有两个节点A和B用一条线连着A ——— B现在A想知道我应不应该被删掉A的想法是我要不要被删取决于B。如果B很重要那我可以被删如果B不重要那我得留下来。所以A先问B假设我A不存在你B自己重要吗B回答A这个问题就是一条消息q⁰_B→A 假设A不存在B应该被删掉的概率 qⁱ_B→A 假设A不存在B应该留下当树根的概率A收到B的回答之后就能更好地判断自己该不该被删了。这些是需要告诉给A的信息第四步现在来看公式(3a)和(3b)论文里的BP方程不要被吓到我们逐个拆解公式(3a)节点i告诉j 我应该被删掉的概率这个公式说的是i告诉j假设你j不存在我i被删掉的概率为什么这么简单因为如果j不存在 → i和j之间的链接消失 → i只需要考虑其他邻居 → 被删掉的概率就是一个基础值 1/zz是归一化常数让概率加起来1公式(3b)节点i告诉j 我应该留下当树根的概率我们把这个公式拆成几个部分部分1∂i\j∂i 节点i的所有邻居 ∂i\j 节点i的所有邻居但去掉j 举例 如果i的邻居是 {A, B, C, j} 那么 ∂i\j {A, B, C}部分2这是邻居k发给i的两个概率之和 - q⁰_k→i k被删掉的概率 - qᵏ_k→i k留下当树根的概率 两个加起来 k处理好了自己的概率 要么被删要么当树根反正不会造成麻烦部分3部分4x是可调参数论文里取x12 e^x是一个放大系数 x越大留下来当树根的概率被放大得越多 → 算法越倾向于删节点而不是留节点整个公式(3b)的意思i告诉j假设你j不存在我i留下来当树根的概率 我所有其他邻居都安排好自己之后我还有余力当树根的概率第五步理解公式(2)——最终打分这个公式看起来最复杂但核心意思很简单收集所有邻居发来的消息综合计算节点i最终应该被删掉的概率我们只需要理解分母里的逻辑分母越大 → q⁰ᵢ 越小 → i不太应该被删 分母越小 → q⁰ᵢ 越大 → i很应该被删什么时候分母小i应该被删当 ∏[q⁰_j→i qʲ_j→i] 很小的时候 翻译当i的邻居们很难自己处理好自己的时候 → 说明i对这些邻居很重要 → i参与了很多环 → i应该被删掉第六步用一个完整小例子走一遍假设这个网络A /|\ B--C \|/ DA和B、C、D都相连B-C、C-D、D-B也相连有很多环。直觉上A在中间参与了最多的环应该优先删A。BPD是怎么得出这个结论的第1轮消息传递 - B问A假设C不存在你A重要吗 → A回答 - C问A假设B不存在你A重要吗 → A回答 - D问A假设B不存在你A重要吗 → A回答 - ……所有邻居互相问 第2轮根据收到的回答更新自己的判断再传出去 第3轮、第4轮……直到稳定 最终结果 - A的q⁰_A 最大比如0.85→ A最应该被删 - B的q⁰_B 较小比如0.4 - C的q⁰_C 较小比如0.4 - D的q⁰_D 较小比如0.4 → 删掉A → 重新计算剩余节点的概率 → 继续删……第七步整个BPD算法流程图开始 ↓ 对当前网络运行BP方程(3) 让消息在网络里传播直到收敛 ↓ 用公式(2)计算每个节点的 q⁰ᵢ ↓ 找出 q⁰ᵢ 最大的节点 实际上每次删一小批比如1%的节点 ↓ 删掉这些节点和它们的链接 ↓ 检查网络里还有环吗 ↓ ↓ 有环 没有环了 ↓ ↓ 回到第一步 检查剩余小树是否太大 ↓ ↓ 太大 都很小 ↓ ↓ 再删几个节点 完成输出攻击目标集合S最终总结用一句话记住BPDBPD 让网络里所有节点互相通风报信每个节点根据邻居的情报判断自己对环有多重要最重要的先删删完再重新通风报信直到所有环消失。五.实验结果——BPD到底比CI好多少先回顾一下评判标准论文用一个指标来衡量算法好坏ρrho 需要删掉的节点数 ÷ 网络总节点数 ρ越小 算法越好 用更少的节点就能让网络瘫痪目标是让最大连通块的相对大小≤ 0.01也就是最大剩余块不超过总网络的1%。实验一随机网络ER网络和RR网络什么是ER网络和RR网络ER网络Erdős-Rényi随机网络 → 每对节点之间随机连线 → 节点的连线数度参差不齐 → 用参数 c 表示平均每个节点有几条连线 RR网络随机正则网络 → 每个节点的连线数完全相同 → 更加均匀 → 用参数 K 表示每个节点有几条连线实验结果对应论文图4ER网络c10时CI算法需要删掉52% 的节点 BPD算法只需要48% 的节点 BPD少删了约 4% RR网络差距更大CI算法远超理论最小值 BPD算法几乎贴近理论最小值用图来理解理论最小值 ████████░░░░░░░░░░░░ 理想情况BPD结果 ████████▓░░░░░░░░░░░ 非常接近理想CI结果 ████████████░░░░░░░░ 差很多█ 必须删的节点▓ BPD多删的很少░ 不用删的节点实验二无标度网络Scale-Free网络什么是无标度网络现实世界很多网络都是无标度网络 - 互联网少数网站百度、谷歌有海量链接 - 社交网络少数人明星、网红有海量粉丝 - 航空网络少数机场北京、上海有海量航线 特点 少数节点Hub节点连线极多 大多数节点连线很少 用参数 γ 描述这种不均匀程度 γ越小 → Hub节点越突出实验结果对应论文图5γ3.0c10时CI算法需要删掉36.6% 的节点 BPD算法只需要33.8% 的节点 BPD又赢了为什么无标度网络相对容易攻击普通网络 无标度网络 ○-○-○-○-○ ○ ○-○-○-○-○ ○--Hub--○ ○-○-○-○-○ ○ 每个节点差不多 Hub连着所有人 攻击无标度网络优先删Hub节点 → 一个Hub倒下大片节点孤立 → 比普通网络容易瘫痪实验三真实世界网络最重要论文测试了12个真实网络包括基础设施网络 - RoadEU - 欧洲公路网1177个节点 - RoadTX - 德克萨斯公路网137万个节点 - Grid - 美国西部电网4941个节点 - IntNet2 - 互联网170万个节点 社交网络 - Friend - 在线友谊网络19万个节点 - Authors - 论文合著网络2.3万个节点 信息网络 - WebPage - 谷歌网页网络87万个节点 - Email - 欧洲邮件网络26万个节点 ……等等最震撼的结果对比互联网 IntNet2170万节点CI算法需要攻击 144,160 个节点 BPD算法只需要 73,229 个节点 BPD只用了CI一半的节点就完成任务电网 GridCI算法需要攻击 476 个节点 BPD算法只需要 320 个节点 节省了33%邮件网络 EmailCI算法需要攻击 21,465 个节点 BPD算法只需要 1,064 个节点 BPD只用了CI的 5%差距极其悬殊实验四最有趣的发现——突然崩溃现象这是论文里最令人惊讶的发现CI算法攻击过程图1中的虚线网络大小 100% |▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 80% |░░░░░░░░▓▓▓▓▓▓▓▓▓▓▓▓ 60% |░░░░░░░░░░░░▓▓▓▓▓▓▓▓ 40% |░░░░░░░░░░░░░░░░▓▓▓▓ 20% |░░░░░░░░░░░░░░░░░░░░ 0% |____________________ 0% 5% 10% 15% 20% 删掉的节点比例 ▓ 剩余最大连通块 特点网络缓慢、平稳地缩小BPD算法攻击过程图1中的实线网络大小 100% |▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 80% |░░░░░░░░░░░▓▓▓▓ 60% |░░░░░░░░░░░░▓▓▓ 40% |░░░░░░░░░░░░░▓▓ 20% |░░░░░░░░░░░░░░▓ 0% |░░░░░░░░░░░░░░░▓← 突然瞬间归零 0% 5% 10% 13.7% 删掉的节点比例 特点网络长时间保持完整 然后在13.7%时突然崩溃为什么会突然崩溃这和BPD的工作原理有关BPD的目标是切断环不是缩小网络 所以攻击过程中 前期BPD专注切断环网络看起来还很完整 但其实网络内部的骨架在不断被破坏 某个临界点最后一个关键环被切断 → 网络失去支撑 → 轰然崩塌就像这个比喻CI攻击 慢慢拆砖头房子慢慢变小 BPD攻击 专门锯承重柱房子表面看起来没变 锯断最后一根承重柱 → 整栋楼瞬间倒塌这个突然崩溃有什么实际意义论文特别提到这一点有非常重要的现实警示意义对于防御方来说 CI攻击 网络慢慢变小 → 防御方能观察到异常 → 有时间反应和修复 BPD攻击 网络长时间看起来正常 → 防御方毫无察觉 → 突然整个网络崩溃 → 根本来不及反应作者在论文里警告如果恐怖分子或敌对势力掌握了BPD算法对电网、互联网、交通网络发动攻击防御方将极难察觉等发现时已经太晚了。实验五算法速度对比BPD不仅结果更好速度也很快BPD的运行时间 ∝ N × ln(N) 这叫做近似线性时间复杂度 含义 节点数翻倍 → 运行时间只增加一点点 实际表现 N 2亿个节点的网络 BPD只需要 23.5小时 就能找到攻击方案对比BPD结果好 速度快 ✓✓ CI 结果差 速度差 ✗✗本课总结实验结论 1. 随机网络上BPD比CI少删 4%-10% 的节点 2. 真实网络上BPD有时只需CI的 5% 的节点 3. BPD的结果非常接近理论最优值 4. BPD攻击会造成突然崩溃防御方难以察觉 5. BPD速度快可以处理超大网络亿级节点六.论文的核心结论论文最终说了三件事结论1BPD算法在所有类型网络上都远优于CI算法 结论2BPD造成的突然崩溃是一种危险的攻击模式 社会需要认真对待这种潜在威胁 结论3BPD算法可以推广到非均匀攻击成本的情况 现实中删掉不同节点的代价是不同的七.全部关键词详解我们把论文里所有重要词汇分成六个类别来解释【第一类】网络基础概念① Node节点定义网络中的基本单元用点表示 现实例子 - 社交网络中 → 每个人 - 互联网中 → 每台服务器 - 电网中 → 每个变电站 - 大脑神经网络→ 每个神经元② Link / Edge链接/边定义两个节点之间的连线表示它们有某种关系 现实例子 - 社交网络中 → 两人是好友 - 互联网中 → 两台服务器之间有数据传输 - 电网中 → 两个变电站之间有电线相连③ Degree度定义一个节点连接的链接数量也就是它有几个邻居 举例 A /|\ B C D A的度 3连着B、C、D B的度 1只连着A 度大的节点 Hub节点 枢纽节点④ Giant Connected Component巨型连通分量定义网络中最大的那个连通块 连通的意思 从这个块里任意一个节点出发 都能通过链接走到这个块里其他任何节点 举例 删节点前 删节点后 一个大块90%节点 → 很多小块每块1%节点 让巨型连通分量消失 网络瘫痪注意是其他任意节点沃⑤ Loop / Cycle环/回路定义从一个节点出发沿着链接走能回到原点的路径 有环A-B-C-A三角形 A-B-C-D-A正方形 无环树 A / \ B C / \ D E 环的重要性 环越多 → 网络越韧 → 越难被攻击破坏⑥ Sparse Network稀疏网络定义链接数量M 和 节点数量N 差不多大的网络 也就是每个节点平均只有几条链接 对比 稀疏网络M ≈ N 每人平均认识3-5人 稠密网络M ≈ N² 每人几乎认识所有人 现实中大多数大型网络都是稀疏网络 互联网、社交网络、电网等⑦ Clustering Coefficient聚类系数定义衡量网络中三角形有多少的指标 直觉理解 你的朋友们互相认识的程度 聚类系数高 → 朋友的朋友也是你朋友三角形多 聚类系数低 → 朋友圈互相不认识 真实网络的聚类系数通常比随机网络高得多【第二类】网络类型⑧ Erdős-Rényi NetworkER网络定义最简单的随机网络模型 生成方式 N个节点任意两个节点之间 以固定概率p随机连一条线 特点 - 大多数节点的度差不多比较均匀 - 度的分布接近正态分布钟形曲线 - 是理论研究的基准网络 参数 c 平均每个节点的度⑨ Regular Random NetworkRR网络随机正则网络定义每个节点的度完全相同的随机网络 举例 K3的RR网络每个节点恰好有3条链接 特点 - 比ER网络更均匀 - 数学上更容易分析 - 现实中较少见主要用于理论研究 参数 K 每个节点的度⑩ Scale-Free Network无标度网络定义度分布符合幂律分布的网络 幂律分布是什么 度为d的节点数量 ∝ d^(-γ) 直觉理解 极少数节点Hub有极多连接 大多数节点只有很少连接 就像财富分布 极少数富人拥有大部分财富 大多数人只有很少财富 现实例子 - 互联网少数网站有海量链接 - 社交网络少数明星有海量粉丝 - 论文引用网络少数论文被大量引用 参数 γ 幂律指数 γ越小 → Hub节点越突出 → 网络越不均匀⑪ Hub节点定义无标度网络中度极大的节点 举例 - 互联网中的百度、谷歌 - 社交网络中的明星账号 - 航空网络中的北京、上海机场 攻击意义 优先攻击Hub节点效果最好 删掉一个Hub → 大量节点失去连接【第三类】优化问题⑫ NP-hard非确定性多项式难定义计算机科学中最难的一类问题 通俗理解 目前没有任何已知算法能在合理时间内 保证找到最优解 时间复杂度对比 简单问题时间 ∝ N线性或 N²多项式 NP-hard时间 ∝ 2^N指数爆炸 举例 N10 2^10 1024 → 还行 N100 2^100 ≈ 10^30 → 超级计算机也算不完 N10002^1000 ≈ 10^300 → 比宇宙年龄还长 所以对NP-hard问题我们只能找够好的近似解⑬ Feedback Vertex SetFVS反馈顶点集定义删掉这些节点后网络中一个环都不剩 反馈的含义 环 信号能反馈回来的路径 切断所有反馈 删掉FVS 最小FVS 节点数量最少的FVS 用最少的代价切断所有环 与网络攻击的关系 在稀疏网络中 最小FVS ≈ 最优攻击目标集合 所以解决FVS问题 ≈ 解决网络攻击问题⑭ Heuristic Algorithm启发式算法定义不保证找到最优解但能快速找到够好解的算法 为什么用启发式算法 因为最优解问题是NP-hard太难了 退而求其次找近似最优解 本论文中的启发式算法 - CI算法较差的启发式 - BPD算法较好的启发式 衡量标准 找到的解 离 理论最优解 有多近 BPD非常近误差1% CI相差很远误差20%⑮ Targeted Attack SetTAS目标攻击集合定义需要被删掉的节点集合 衡量指标 ρ |TAS| ÷ N 被删节点数 ÷ 总节点数 ρ越小 → 攻击越高效 论文结果 BPD的ρ 远小于 CI的ρ 在某些网络上BPD的ρ只有CI的ρ的5%【第四类】算法相关⑯ Belief PropagationBP置信传播定义一种在网络上传递概率信息的算法 核心思想 每个节点把自己的信念概率估计 传递给邻居节点 邻居收到后更新自己的信念 再传递给下一个邻居 ……直到所有节点的信念稳定不变 类比 八卦在朋友圈里传播 每个人听到八卦后更新自己的判断 然后告诉其他朋友 最终大家的判断趋于一致 数学上 BP方程 论文里的公式(3a)(3b) 收敛后用公式(2)计算最终概率⑰ Decimation抽取/逐步删除定义每次删掉一小批节点然后重新计算的策略 为什么不一次性删掉所有高分节点 因为删掉一个节点后网络结构改变了 其他节点的重要性也随之改变 所以要 删一批比如1%的节点→ 重新计算 → 再删一批 → …… 参数 f 每次删掉的节点比例 论文中 f 0.01每次删1%⑱ Collective Information AlgorithmCI算法集体影响算法定义2015年Morone和Makse提出的网络攻击算法 核心思想 给每个节点计算一个影响力分数 分数 节点自身的传播能力 × 以节点为中心半径l范围内边界节点的传播能力 公式 CI_l(i) (度_i - 1) × Σ(度_j - 1) j在i周围距离l的位置 参数 l 考虑的半径范围论文中l4 缺点 只看局部信息半径l以内 忽略了全局的环结构 所以效果比BPD差很多⑲ Re-weighting Parameter x重加权参数定义BPD算法中控制激进程度的参数 作用 x大 → 算法更倾向于删节点 x小 → 算法更倾向于保留节点 论文中 ER网络用 x 12 RR网络用 x 7 x出现在公式里的位置 e^x × (其他项) x越大e^x越大删节点的倾向越强⑳ Time Complexity时间复杂度定义算法运行时间随网络规模增长的速度 BPD的时间复杂度 T ∝ N × ln(N) 这意味着 N 100万节点 → 算几分钟 N 1亿节点 → 算几小时 N 2亿节点 → 约23.5小时 CI的时间复杂度 和BPD差不多但结果质量差很多 为什么近线性很重要 现实网络动辄百万、千万节点 只有近线性算法才能处理这种规模【第五类】物理学概念㉑ Spin Glass自旋玻璃定义统计物理学中的一种无序磁性系统 物理含义 铁磁体中每个原子有一个自旋方向 自旋玻璃中这些方向是随机无序的 相互作用又复杂又矛盾 为什么和网络攻击有关 Zhou2013发现 FVS问题 可以 完美映射到 自旋玻璃模型 每个网络节点 → 一个自旋 节点的状态删/留 → 自旋的方向上/下 最小FVS → 自旋玻璃的基态最低能量状态 这个映射让我们可以用物理学工具解决网络问题㉒ Replica-Symmetric Mean Field Theory复本对称平均场理论定义统计物理中分析自旋玻璃的数学工具 作用 可以计算出最小FVS的理论下界 也就是理论上最少需要删掉多少节点 论文中的用途 作为衡量算法好坏的基准线 结果 BPD的结果 非常接近 理论下界误差1% CI的结果 远离 理论下界误差20%㉓ Non-backtracking Matrix / Hashimoto Matrix非回溯矩阵/桥本矩阵定义描述网络中信号传播不走回头路的数学矩阵 在论文里出现在哪 论文最后提到 可以用这个矩阵的最大特征值 来区分有意攻击和随机故障 直觉理解 BPD攻击 → 特征值变化有特殊规律 随机故障 → 特征值变化没有规律 → 或许可以用来预警 注这是论文提出的未来研究方向尚未实现【第六类】结果描述㉔ Abrupt Collapse突然崩溃定义网络在BPD攻击下表现出的现象 长时间保持完整然后瞬间崩溃 类比 - 水坝长时间承压突然决堤 - 骨牌推倒第一块其余瞬间全倒 - 桥梁表面完好锯断承重柱后瞬间倒塌 数学上类似于 相变Phase Transition 水突然从液态变成气态 网络突然从连通变成碎片 危险性 防御方毫无预警 → 极难防御㉕ Explosive Percolation爆炸性渗流定义网络科学中的一种相变现象 系统在临界点附近发生极其剧烈的突变 论文中说BPD的突然崩溃 类似于爆炸性渗流现象 渗流理论的直觉 往沙子里倒水 水慢慢渗透 突然在某一刻贯通整个沙层 网络中 随着节点被删除 网络突然在某一刻完全碎裂㉖ ρrho相对大小定义目标攻击集合的相对大小 公式ρ 被删节点数 ÷ 总节点数 例子 网络有100万个节点 BPD需要删7万个 ρ_BPD 7万 ÷ 100万 0.07 7% CI需要删14万个 ρ_CI 14万 ÷ 100万 0.14 14% ρ越小越好㉗ θtheta阈值定义判断网络是否瘫痪的标准 论文中 θ 0.01 含义 当最大连通块的相对大小 ≤ 1% → 认为网络已经瘫痪 为什么是1% 如果最大剩余块只有1%的节点 这个块已经非常小无法正常运作 实际上已经没有意义了三、所有关键词的关系图网络基础 节点链接度 ↓ 形成各种网络类型 ER网络 / RR网络 / 无标度网络 ↓ 网络中存在环和巨型连通分量 ↓ 目标最优网络攻击问题 找最小目标攻击集合TAS使ρ最小 ↓ 问题是NP-hard只能用启发式算法 ↓ 关键洞察攻击问题 ≈ 最小FVS问题 ↓ 两种算法 CI算法局部信息效果差 BPD算法全局信息效果好 ↓ BPD基于 自旋玻璃理论 → 置信传播(BP) → 逐步删除(Decimation) ↓ BPD的结果 - ρ更小接近理论最优 - 速度快近线性时间复杂度 - 造成突然崩溃类似爆炸性渗流