COMP5313 Large Scale Networks — Lecture 总结

Posted on Edited on In , Word count in article: 4.6k Reading time ≈ 17 mins.

COMP5313 Large Scale Networks — Lecture 总结

基于 Week 01-12 课程录音转录，涵盖老师讲的所有知识点、考点和重点提示。

Week 01: 课程介绍 & 图论基础

课程信息

  • 讲师：Adrian Chen
  • 考核：Assignment 1 (10%) + Midterm Quiz (10%, MCQ, 闭卷) + Group Project (20%) + Final Exam (60%, hurdle 40%)
  • 期末考试 hurdle：必须拿到 40% 以上才能通过
  • Midterm Quiz：纯选择题，闭卷但可带纸质材料，不能用电子设备
  • 可以使用 AI 工具辅助作业，但不能直接生成答案/报告/代码

课程主题概览

  • Week 2-4：社交网络（strong/weak ties, structural balance, community detection）
  • Week 5-6：信息网络（web graph, HITS, PageRank）
  • Week 7-8：图机器学习（GNN, label propagation）
  • Week 9-10：网络动力学（information cascade, power law, small world model）
  • Week 11：P2P 网络（Chord, CAN）

图论基础概念

  • 图 (Graph)：节点 (vertices/nodes) + 边 (edges/links)，G = (V, E)
  • 无向图 vs 有向图：无向图边是对称的；有向图边有方向
  • 路径 (Path)：节点序列，相邻节点间有边；有向图必须沿方向走
  • 简单路径：无重复节点
  • 环 (Cycle)：起点 = 终点的路径
  • 连通分量 (Connected Component)：最大连通子图
  • 巨型分量 (Giant Component)：远大于其他分量的连通分量；大多数网络只有一个
  • 距离 (Distance)：最短路径长度
  • 直径 (Diameter)：所有节点对中最大的距离
  • BFS (广度优先搜索)：计算从一个节点到所有其他节点的距离
    • BFS 树的性质：边只存在于相邻层之间或同层之间
    • 时间复杂度：O(n + m)

老师提到的例子

  • ARPANET（早期互联网）
  • 高中生恋爱关系网络（巨型分量与性病传播）
  • 澳大利亚殖民化导致两个巨型分量合并 → 天花传播

Week 02: 小世界现象、强弱连接、结构平衡

小世界现象 (Small World Phenomenon)

  • 六度分隔 (Six Degrees of Separation)
  • Milgram 实验 (1960s)：约 300 人转发信件给指定目标，64 封到达，中位步数 = 6
  • Microsoft Messenger 数据 (2008)：2.4 亿用户，平均距离 6.6，中位距离 7
  • BFS 计算所有节点对距离的时间复杂度：O(n × m)，对 2.4 亿节点需约 60 天

强连接与弱连接 (Strong & Weak Ties)

  • 桥 (Bridge)：删除后使两端点断开的边（实际网络中极少）
  • 局部桥 (Local Bridge)：两端点无公共邻居（即不在任何三角形中）
    • 删除后两端点距离严格 > 2
    • 跨度 (Span)：删除局部桥后两端点的距离
  • 强三角闭合性质 (Strong Triadic Closure, STC)：若 A 与 B、C 都是强连接，则 B 和 C 之间必有边
  • ⚠️ 考点定理：若节点 A 满足 STC 且至少有两个强连接，则 A 的任何局部桥必为弱连接
    • 老师明确说这个证明可能在期末考试中考到
    • 证明方法：反证法——假设局部桥是强连接，由 STC 推出三角形存在，与局部桥定义矛盾

邻域重叠 (Neighbourhood Overlap)

  • 公式：|N(A) ∩ N(B)| / |N(A) ∪ N(B) - {A, B}|
  • 局部桥的邻域重叠 = 0
  • 电话网络实验证实：连接强度与邻域重叠正相关

Facebook/Twitter 连接分析

  • 即使有 500 个好友，实际通信的只有 10-20 个（强连接）
  • 被动关注的约 50 个（中间地带，对信息传播重要）

结构洞 (Structural Holes)

  • 嵌入度 (Embeddedness)：一条边的两端点公共邻居数
  • 位于多个社区交界处的节点拥有信息控制优势（守门人角色）

符号图与结构平衡 (Signed Graphs & Structural Balance)

  • 边标记为 +（朋友）或 -（敌人）
  • 三角形的 4 种配置：
    • 3 个 +：平衡（互为朋友）
    • 1 个 + 2 个 -：平衡（共同敌人）
    • 2 个 + 1 个 -：不平衡（不稳定）
    • 3 个 -：不平衡（不稳定）
  • 平衡定理（完全图）：完全符号图平衡 ⟺ 所有边为 + 或节点可分为两组 X、Y，组内全 +，组间全 -
    • 老师说这个证明比较复杂，不会在期末考试中考

Week 03: 结构平衡检测算法、同质性、社会影响

非完全符号图的结构平衡

  • 两种等价定义：
    1. 能补全缺失边使之成为平衡的完全图
    2. 能将节点分为两组，组内全 +、组间全 -
  • 核心定理：符号图不平衡 ⟺ 包含负边数为奇数的环

⚠️ 检测平衡的算法（Assignment 1 有相关题目）

  • 两步法：
    1. 只看正边，找连通分量（超节点）；若超节点内有负边 → 不平衡
    2. 缩成超节点图（只剩负边），用 BFS 检查是否二部图
      • 二部图 → 平衡；有奇环 → 不平衡
  • 等价方法：直接用 BFS/DFS 在原图上标记 X/Y 集合

应用

  • 国际关系分析（1972 年美巴关系解释）
  • Slashdot、Epinions 等在线评价网络

同质性 (Homophily)

  • 定义：相似的人更容易成为朋友
  • 同质性检验：比较实际跨组边比例与随机图期望值 2pq
    • 实际 < 2pq → 有同质性证据
    • p = 一组占比，q = 另一组占比
    • 考试中不需要考虑统计显著性，直接比较即可

三种闭合过程 (Closure Processes)

  • 三角闭合 (Triadic Closure)：共同朋友 → 成为朋友 → 选择机制
  • 焦点闭合 (Focal Closure)：共同活动/组织 → 成为朋友 → 选择机制
  • 成员闭合 (Membership Closure)：朋友的活动 → 自己也加入 → 社会影响机制
  • 区分关键：是否已经是朋友？未成为朋友前 = 选择；已是朋友后 = 社会影响

聚集系数 (Clustering Coefficient)

  • 节点 A 的聚集系数 = A 的朋友中互为朋友的比例
  • 三角闭合会增加聚集系数

选择 vs 社会影响的实证（Wikipedia 编辑数据）

  • 首次通信前：相似度急升（选择机制）
  • 首次通信后：相似度继续升高（社会影响机制）

Schelling 模型（隔离模型）

  • 二维网格，两类人，阈值 T
  • 若同类邻居 < T，不满意 → 搬家
  • 结果：即使 T 很小也会产生大规模隔离区

Week 04: 社区检测

社区 (Community)

  • 非正式定义：内部连接密集、外部连接稀疏的节点组
  • 无正式定义，不同算法可能给出不同结果
  • 应用：蛋白质交互网络、空手道俱乐部数据集

两类方法

  • 分裂法 (Divisive)：逐步删除边，将网络分成小组
  • 凝聚法 (Agglomerative)：逐步合并节点/小组

树状图 (Dendrogram)

  • 记录分裂/合并的完整过程
  • 不同水平切割 → 不同数量的社区
  • 用模块度 (Modularity) 决定最佳切割点

⚠️ 模块度 (Modularity)

  • 公式：Q = Σ_s [m_s/m - (D_s/2m)²]
    • m_s = 社区 s 内的边数
    • D_s = 社区 s 内节点的度之和（包括跨社区边）
    • m = 总边数
  • 取值范围：[-1, 1]
  • 所有节点在同一社区 → Q = 0
  • 每个节点单独一社区 → Q < 0
  • 选择 Q 最大的分法

⚠️ Girvan-Newman 算法

  • 每步删除边介数最高的边
  • 删除后若产生新连通分量 → 记录为新层级
  • 每次删除后必须重新计算边介数（否则结果差）
  • 空手道俱乐部数据集只错分 1 个节点

⚠️ 边介数 (Edge Betweenness)

  • 定义：所有节点对之间的最短路径中经过该边的流量总和
  • 若有 K 条最短路径，每条分 1/K 的流量
  • 桥的介数 = |X| × |Y|（两侧节点数之积）
  • BFS 算法计算边介数（老师说理解即可，不要求实现）：
    1. 从某节点做 BFS，记录到每个节点的最短路径数
    2. 自底向上计算每条边的流量
    3. 对每个起始节点重复，求和后除以 2
    • 时间复杂度：O(nm) 计算所有边的介数
    • Girvan-Newman 总时间：O(nm²)

其他方法（简述）

  • 凝聚法 (Ravasz)：基于相似度矩阵的层次聚类
  • 重叠社区：K-Clique Percolation：共享 K-1 个节点的 K-团归入同一社区
  • Louvain 算法：直接优化模块度（启发式，NP-hard 问题）
  • Metis：图分区（用于分布式计算）

Week 05: 信息网络、Web 图结构、HITS 算法

信息网络 vs 社交网络

  • 信息网络：节点 = 信息片段（网页、论文）；通常有向
  • 社交网络：节点 = 人；通常无向
  • 社交网络的概念（社区检测等）也可应用于信息网络

有向图概念

  • 强连通分量 (SCC)：每对节点间都有有向路径
    • ⚠️ 去年期末考了 SCC 题目（给图求 SCC 数量），很多人答错
    • 单个节点也是一个 SCC
    • 不同 SCC 之间不相交

Web 图的 Bowtie 结构（Broder 1999）

  • Giant SCC：5600 万节点
  • IN 节点：能到达 Giant SCC 但不属于它（4400 万）
  • OUT 节点：能从 Giant SCC 到达（4400 万）
  • Tendrils：连接到 IN/OUT 但不连接 Giant SCC
  • 断开分量：与 Giant SCC 完全断开

⚠️ HITS 算法 (Hub and Authority)

  • 每个节点有两个分数：Hub 分数 h 和 Authority 分数 a
  • Authority 更新：a_p = Σ_{q→p} h_q（所有指向 p 的节点的 hub 分数之和）
  • Hub 更新：h_p = Σ_{p→q} a_q（p 指向的所有节点的 authority 分数之和）
  • 初始化 h = 全 1 向量
  • 迭代 K 步后归一化
  • 矩阵形式：
    • a = A^T × h
    • h = A × a
  • 收敛值：h → AA^T 的最大特征向量，a → A^TA 的最大特征向量
  • 不依赖初始值（只要全为正数）
  • 应用：美国最高法院判例引用分析

Week 06: PageRank 算法

⚠️ 基本 PageRank

  • 每个节点一个重要性分数 r_i
  • 定义：r_j = Σ_{i→j} r_i / d_i（从指向 j 的节点 i 获得 r_i/d_i 的投票）
  • 无出链节点加自环（保证 PageRank 总和 = 1）
  • 求解方法（小图）：列线性方程组 + 约束 Σr_i = 1
  • 迭代算法：初始 r_i = 1/n，重复应用更新规则
  • 矩阵形式：R^(k+1) = R^(k) × W，其中 W = D^(-1) × A（行随机矩阵）
  • 强连通图 → 唯一均衡值；非强连通图可能不收敛

Spider Trap 问题

  • 非强连通图中，PageRank 会累积在下游 SCC 中
  • Bowtie 结构中 PageRank 会全部流向 OUT 节点

⚠️ Scaled PageRank（实际使用的版本）

  • 公式：R^(k+1) = α × R^(k) × W + (1-α)/n × e
  • α 通常取 0.85
  • 等价于将图变为完全图 → 保证强连通 → 唯一均衡值
  • 随机游走解释：概率 α 沿随机出链走，概率 1-α 跳转到随机页面
  • 均衡值公式：R = (1-α)/n × e × (I - αW)^(-1)
  • 即使初始值全为 0 也能收敛（因为每步引入 1-α 的新 PageRank）
  • 无向连通非二部图：均衡 PageRank = degree/(2m)

⚠️ 个性化 PageRank (Personalized PageRank, PPR)

  • 与 Scaled PageRank 唯一区别：跳转时不是去随机页面，而是去预选页面集合 S
  • PPR 矩阵：第 i 行 = 相对于节点 i 的 PPR 值
  • Scaled PageRank = PPR 矩阵所有行的平均
  • 比最短路径更精细地衡量节点间相关性

考试相关

  • 老师说不会考推导过程，但要理解结论
  • 期末不考高级谱分析推导

Week 08: 图机器学习 — 标签传播与 GNN

主要内容

  • 标签传播 (Label Propagation)：利用图结构传播已知标签到未标记节点
    • 无特征时也可使用
    • 可作为后处理步骤提高 GNN 准确率
    • 可集成到 GNN 中
  • 特征传播 (Feature Propagation)：传播节点特征而非标签，用于预处理提高可扩展性
  • GNN 回顾：邻接矩阵 A、特征矩阵 X、节点分类任务
  • 核心思想：预测节点标签时，不仅用自身特征，还用邻居的特征

Week 09: 信息级联 (Information Cascade)

核心概念

  • 人们会受他人行为影响，即使自己的信息暗示不同选择
  • 从众 (Following the Crowd)：理性选择跟随他人行为
  • 羊群效应 (Herding)：信息级联的正式数学描述
  • 老师进行了数学证明，说明在某些条件下从众是理性的

主要内容

  • 旅行者选择餐厅的思想实验
  • 贝叶斯推理框架下的级联形成
  • 为什么级联会发生、何时会发生
  • 级联的脆弱性

Week 10: 幂律分布 & 小世界模型

幂律分布 (Power Law Distribution)

  • f(k) ≈ 1/k^c（c 通常略 > 2）
  • 与正态分布区别：下降速度慢得多，允许极高度数节点存在
  • 检验方法：log-log 坐标画图，若为直线则符合幂律
  • 优先连接模型 (Preferential Attachment)：新节点连接到已有节点的概率 ∝ 其当前度数
    • 产生"富者愈富" (Rich-get-richer) 效应
    • 生成幂律度分布

Watts-Strogatz 小世界模型

  • 两个原则：同质性（近邻连接 → 三角形）+ 弱连接（随机远程连接 → 短路径）
  • 原始模型问题：随机链接太随机，去中心化搜索不高效

⚠️ 广义 Watts-Strogatz 模型 (Kleinberg 模型)

  • 随机链接概率 ∝ d(u,v)^(-q)
  • q = 2 时去中心化搜索最高效（二维网格）
  • 核心直觉：距离 d 处节点数 ∝ d²，连接概率 ∝ d^(-2)，两者相乘 = 常数 → 各尺度均匀分布
  • 老师说不需要形式化证明，理解直觉即可

Rank-based Friendship

  • 连接概率 ∝ rank^(-p)，p = 1 对任意人口分布都有效
  • LiveJournal 实证验证

Week 11: P2P 系统 & 分布式哈希表

老师明确说 P2P 简介部分 optional，不会考

⚠️ Chord DHT

  • 环形结构，节点和文件 key 都用 m 位编码
  • 文件存储在 successor 节点上
  • Finger Table：节点 i 的第 j 项指向负责 key (i + 2^(j-1)) mod 2^m 的节点
  • 路由原则："尽可能远但不超过目标"
  • 时间复杂度：O(log n)，每步距离减半
  • 空间复杂度：O(log n)（finger table 大小）
  • Tutorial 会练习 finger table 计算

CAN DHT

  • d 维空间，节点负责一个区域
  • 路由：贪心选最近邻居
  • 时间复杂度：O(d × n^(1/d))
  • 空间复杂度：O(d)

Chord vs CAN 对比

Chord CAN
结构 一维环 d 维空间
时间 O(log n) O(d × n^(1/d))
空间 O(log n) O(d)

Week 12: 学生项目展示

  • 无新考试内容
  • 展示了图分析技术在各种实际问题中的应用

Week 13: 期末复习课 — ⚠️ 极其重要

期末考试格式

  • 14 题，共 60 分
  • 5 道 MCQ（共 10 分，每题 2 分）— 与 midterm quiz 类似，老师说是"easy marks"
  • 9 道简答题（共 50 分）— 部分有子问题
  • 时间：2 小时 + 10 分钟阅读时间
  • 考试范围：Week 1-11，排除所有标记为 optional 的内容
  • 无编程题
  • 必须展示解题过程，只写最终答案可能不给分
  • 今年比去年简单（减少了题目数量，去掉了填空题）

考试条件（限制性开卷）

  • ✅ 非编程计算器（需验证标签）— 强烈建议带
  • ✅ 1 张 A4 纸双面 cheat sheet（手写或打印均可，任何语言）
  • ✅ 标准双语词典
  • 提供草稿纸（答案写在考试册中，草稿纸不批改）

通过条件

  • 期末考试至少 40%（24/60 分）
  • 总分至少 50 分

Midterm Quiz 易错题回顾（老师在复习课详细讲解）

Q3 焦点闭合 (Focal Closure)：焦点（如网球）将两个人联系成朋友 vs 成员闭合（朋友介绍你加入活动） - 正确：Tennis introduces David to you（焦点闭合） - 错误：Bob introduces David to tennis（成员闭合）

Q4 跨度 (Span)：删除桥后两端点距离 = 正无穷（不是负无穷、不是 0）

Q7 Scaled PageRank 计算：无入链节点每步获得 (1-α)/n - 例：A→B，α=0.8，初始全 0，两步后 A 的 PageRank = (1-0.8)/2 = 0.1

Q8 聚集系数：6 个邻居中 6 条边 → 6/C(6,2) = 6/15 = 2/5

Q11 社区内度数之和：用原图的度（不是子图的度），包括跨社区边的贡献

Q12 嵌入度 = 包含该边的三角形数量：TRUE（每个公共邻居形成一个三角形）

Q13-14 基本 PageRank Spider Trap：A→B→C（无回路），两步后所有 PageRank 累积到 C=1

Q15 Scaled PageRank 收敛性：TRUE — 无论初始值如何（包括全 0），scaled PageRank 总是收敛到相同的非零均衡值 - 原因：每步引入 (1-α) 新 PageRank，初始值贡献按 α^k 衰减至 0

Q16 社会影响 vs 选择： - 选择 = 选择相似的人做朋友（形成新连接） - 社会影响 = 影响已有朋友改变行为

Q17-18 边介数计算： - 桥的介数 = |X| × |Y|（简单） - 非桥：必须枚举所有节点对，逐一计算最短路径分配

复习课上的示例考题

  1. 同质性检验：给图判断是否有同质性证据，计算 p、q、2pq，与实际跨组边比例比较

  2. 解释 Spider Trap 问题：基本 PageRank 的问题 + Scaled PageRank 如何解决

    • 基本 PageRank：非强连通图中 PageRank 累积在下游节点
    • Scaled PageRank：每步缩放 α 倍 + 重新分配 (1-α)，等价于完全图 → 强连通 → 唯一均衡值

  3. HITS 算法应用：给图计算 hub/authority 分数（来自 Tutorial Week 5）

  4. ⚠️ Chord Finger Table：m=6, 节点 8

    • 第 j 项：负责 key (8 + 2^(j-1)) mod 64 的节点
    • 结果：14, 14, 14, 21, 32, 42
    • 路由：节点 8 查 key 51 → 走到 42 → 42 的 finger table 中找到 51 → 到达
    • 老师说每年都考这类题

复习建议（老师原话）

  1. 看 Week 1-11 的 lecture slides
  2. 重点看 Tutorial Week 2, 5, 6, 11 的练习题（这四周有解题练习）
  3. Assignment 1 没拿满分的题目要重新做
  4. 复习 Midterm Quiz

⚠️ 考试要点终极汇总

一定会考的题型

  1. MCQ（5 题 10 分）：定义理解题，与 midterm 类似
  2. 同质性检验计算：p、q、2pq、与实际比较
  3. PageRank 计算（基本或 scaled，小图手算）
  4. 边介数计算（桥用 |X|×|Y|，非桥枚举节点对）
  5. Chord Finger Table + 路由查找（每年必考）
  6. HITS 计算（给图算 hub/authority 分数）
  7. 概念解释题（如 spider trap 问题）

老师明确说可能考的证明/推理

  • STC → 局部桥必为弱连接（反证法）
  • Scaled PageRank 为什么总收敛（直觉解释即可，不需要形式化证明）

老师说不考的内容

  • 结构平衡定理的完整证明
  • HITS/PageRank 的谱分析推导过程
  • P2P 系统简介部分
  • 所有标记为 "optional" 的内容
  • 编程题