COMP5313_Week1-6_Summary
Week 1: 课程介绍 & 图论基础
课程概述
- 课程名称: Large Scale Networks（大规模网络）
- 核心内容: 用图/网络模型分析现实系统（社交网络、Web、交通网络等）
- 教材: Networks, Crowds, and Markets — David Easley & Jon Kleinberg（电子版免费）
课程安排
| 周次 | 主题 |
|---|---|
| 2–4 | 社交网络（ties、structural balance、社区检测） |
| 5–6 | 信息网络（Hub/Authority、PageRank） |
| 7–8 | 图上的机器学习 |
| 9–11 | 网络动力学（信息级联、去中心化搜索） |
考核结构
- Assignment 1（10%）：解题
- Midterm Quiz（10%）：选择题，纸笔，可带纸质资料
- Assignment 2（20%）：小组项目 + 报告 + 录制展示
- Final Exam（60%）：hurdle，需 ≥ 40% 才能通过
图论基础概念
图的表示: G = (V, E)，V 为节点集，E 为边集
无向图 vs 有向图: - 无向图：边是对称关系（如 Facebook 友谊） - 有向图：边有方向（如 Twitter 关注、Web 超链接）
路径 (Path): 节点序列，每对相邻节点之间有边；路径长度 = 边数
连通分量 (Connected Component): 无向图中的最大连通子图
巨型连通分量 (Giant Component): 一个网络通常只有一个远大于其他分量的连通分量。两个大分量只需一条边即可合并。
距离与直径: 距离 = 最短路径长度；直径 = 所有节点对中最大的距离
BFS（广度优先搜索）: 从起点逐层扩展，可计算从起点到所有节点的距离。BFS 树中的边只连接同层或相邻层节点。
Week 2: 图的 Ties 与 Structural Balance
小世界现象 (Small World Phenomenon)
Milgram 实验 (1960s): 约 300 人尝试通过私人关系将信件转交到特定目标人物。64 封信到达，中位步数为 6 → "六度分隔"
Microsoft Messenger 验证 (2008): 2.4 亿用户网络，巨型连通分量包含几乎所有节点，平均距离 6.6，中位距离 7
强连接与弱连接 (Strong & Weak Ties)
核心发现: 找工作时，熟人（弱连接）比亲密朋友（强连接）更有用 → 弱连接跨越不同群体，带来新信息
桥 (Bridge): 删除后使两端点不连通的边（现实中极少）
局部桥 (Local Bridge): 两端点无公共邻居的边（删除后距离 > 2）；Span = 删除后两端点的新距离
Strong Triadic Closure 性质: 若节点 A 满足该性质且有 ≥ 2 条强连接，则 A 的所有局部桥必为弱连接
证明（反证法）: 假设 A-B 是强连接的局部桥，A 还有另一强连接 A-C，则 B、C 应相连（by STC），但这与局部桥定义矛盾。
实证验证 (手机通话数据): - Tie strength（通话总时长）与 Neighbourhood overlap（公共邻居比例）呈正相关 - 先移除弱连接 → 巨型分量迅速缩小；先移除强连接 → 巨型分量仍保持
Neighbourhood Overlap: |N(A) ∩ N(B)| / |N(A) ∪ N(B) {A,B}|，局部桥的 overlap = 0
结构洞 (Structural Holes)
Embeddedness: 一条边两端点的公共邻居数量
结构洞: 节点 B 位于多个不互动群体的交界处 → 充当"守门人"角色，控制信息流通，具有战略优势
Structural Balance (Signed Graph)
Signed Graph: 每条边标记为正（朋友）或负（敌人）
三角形平衡规则: - 平衡：3 正边 或 1 正 2 负 - 不平衡：2 正 1 负 或 3 负
完全图的 Balance Theorem: 一个有标签完全图是 balanced ⟺ 所有边为正 或 节点可分为两组（组内全正、组间全负）
证明思路: 选取有负边的节点 A，将其朋友归入 X、敌人归入 Y，利用 balanced 三角形条件推导出 X 内全正、Y 内全正、X-Y 间全负。
Week 3: Structural Balance（续）& 网络演化
不完全图的 Structural Balance
两种等价定义: 1. 能否补全缺失边使其成为 balanced 完全图 2. 能否将节点分为两组：组内全正、组间全负
关键定理: Signed graph 不平衡 ⟺ 存在含奇数条负边的环
检测算法（两步法）
Step 1: 只看正边，找连通分量（supernodes）。若某 supernode 内部有负边 → 直接判定不平衡（找到只含 1 条负边的环）
Step 2: 将 supernodes 缩点，得到只含负边的简化图。判断该图是否为二部图（用 BFS）： - 是二部图 → balanced - 存在奇数环 → unbalanced
也可直接用 BFS/DFS: 从任意节点开始，遇正边同组、负边异组，若产生矛盾则 unbalanced
应用
- 国际关系分析: 1972 年各国关系构成 signed graph，美国支持巴基斯坦可由 balance 分组解释
- 在线信任网络: Slashdot、Epinions 等数据集
Homophily（同质性）
定义: 人们倾向与相似的人建立关系
检测方法: 比较实际跨组边比例与随机图中的期望比例 2pq。若实际比例显著低于 2pq → 存在 homophily
两大驱动机制: - Selection（选择）: 人们选择与自己相似的人交友 - Social Influence（社会影响）: 朋友之间互相影响行为
Affiliation Network & 闭包过程
社会关联网络: 二部图（人 ↔︎ 活动/组织）+ 社交网络
三种闭包过程: 1. Triadic Closure（选择）: 共同朋友 → 成为朋友 2. Focal Closure（选择）: 共同活动 → 成为朋友 3. Membership Closure（社会影响）: 朋友参加的活动 → 自己也加入
实证（email 数据）: 共同朋友越多，未来成为朋友的概率越高（近似线性增长）
Clustering Coefficient: 节点 A 的朋友之间实际边数 / 最大可能边数。Triadic closure 会增大此值。
Schelling 模型（隔离模型）
- 两类 agent 在网格上，若同类邻居不足阈值 T 则搬家
- 即使 T 很小（如 3），也会产生大面积同质区域 → homophily 导致 segregation
Week 4: 社区检测 (Community Detection)
社区的定义
社区 = 内部连接密集、与外部连接稀疏的节点子集（无严格数学定义）
两种框架
- Divisive（自顶向下）: 逐步移除边，将图分裂为子图
- Agglomerative（自底向上）: 逐步合并相似的节点/社区
两种方法均生成 Dendrogram（树状图），水平切割确定最终社区数
Modularity（模块度）
\[Q = \sum_{s \in S} \left[ \frac{m_s}{m} - \left(\frac{D_s}{2m}\right)^2 \right]\]
- \(m_s\): 社区 s 内部边数
- \(D_s\): 社区 s 内节点度数之和
- \(m\): 图的总边数
- 取值范围 [-1, 1]，越大越好
- 所有节点归为一个社区 → Q = 0；每个节点自成社区 → Q < 0
Girvan-Newman 算法（Divisive）
Edge Betweenness: 所有节点对的最短路径中经过该边的流量总和
算法流程: 1. 计算所有边的 betweenness 2. 移除 betweenness 最高的边 3. 重新计算 betweenness（重要！） 4. 若产生新连通分量则记录 5. 重复，直到所有边被移除
Betweenness 高效计算（BFS 法）: 1. 从起点做 BFS，逐层记录最短路径数 2. 自底向上计算每条边的流量：每个节点的流量 = 1 + 下层传来的流量，按最短路径数比例分配给上层边 3. 对所有起点求和，最终除以 2
时间复杂度: 计算所有边 betweenness = O(nm)；完整 Girvan-Newman = O(nm²)
其他方法（简述）
- Agglomerative（Ravasz 算法）: 定义节点相似度 → 逐步合并最相似社区
- Clique Percolation: 以 k-clique 为基本单元，共享 k-1 个节点的 cliques 合并为社区 → 可发现重叠社区
- Louvain: 直接优化 modularity 的启发式算法（NP-hard 问题）
Week 5: 信息网络 & Hub-Authority 算法
信息网络
Web Graph: 节点 = 网页，有向边 = 超链接。去中心化系统。
Citation Network: 节点 = 论文，有向边 = 引用关系。具有时间特性（只能引用已发表的论文）。
有向图概念
路径: 必须沿边方向行进
强连通分量 (SCC): 有向图中，每个节点到其他所有节点都有路径的最大子图。每个节点恰属于一个 SCC。
Web 的蝴蝶结结构 (Bow-Tie Structure)
Broder et al. (1999) 用 AltaVista 爬取的数据发现： - Giant SCC (56M 节点): 核心，任意两点互达 - IN 节点 (44M): 可达 SCC 但 SCC 不可达它们 - OUT 节点 (44M): SCC 可达但不可回到 SCC - Tendrils: 与 SCC 通过 IN/OUT 间接相连的节点 - Disconnected: 与 SCC 完全无关
Hub-Authority 算法 (HITS)
提出者: Jon Kleinberg（教材作者之一）
核心思想: 每个网页有两个角色 - Authority（权威）: 被很多好 hub 指向的页面 - Hub（枢纽）: 指向很多好 authority 的页面
更新规则: - Authority 更新: \(a_p = \sum_{q \to p} h_q\)（所有指向 p 的页面的 hub 分数之和） - Hub 更新: \(h_p = \sum_{p \to q} a_q\)（p 指向的所有页面的 authority 分数之和）
算法: 1. 初始化所有 hub score = 1 2. 交替应用 authority 更新和 hub 更新，共 K 步 3. 归一化。K ≈ 20 通常足够
矩阵形式: - \(\mathbf{a} = A^T \mathbf{h}\)（authority 更新） - \(\mathbf{h} = A \mathbf{a}\)（hub 更新） - 经 K 步后: \(\mathbf{h}^{(K)} = (AA^T)^K \mathbf{h}^{(0)}\)
谱分析（可选/Advanced）
\(AA^T\) 是对称半正定矩阵 → 有 n 个正交单位特征向量 \(Z_1, ..., Z_n\)，对应非负特征值 \(C_1 \geq C_2 \geq ...\)
收敛定理: 只要初始 hub score 全为正数，归一化后的 hub vector 收敛到 \(AA^T\) 的最大特征值对应的特征向量 \(Z_1\)。Authority 类似，收敛到 \(A^T A\) 的最大特征向量。
Week 6: PageRank 算法
基本 PageRank
核心思想: 每个网页只有一个重要性分数。页面将 PageRank 均分给所有出链目标。
公式: \(R_j = \sum_{i \to j} \frac{R_i}{d_i}\)，其中 \(d_i\) 是节点 i 的出度
与 HITS 的区别: - 只有一个分数（不区分 hub/authority） - endorsement 直接在节点间传递
矩阵形式: \(\mathbf{r}^{(t+1)} = \mathbf{r}^{(t)} W\)，其中 \(W = D^{-1}A\)（行随机矩阵，每行和为 1）
求解: - 小图: 列线性方程组 + 约束 \(\sum R_i = 1\)，高斯消元 - 大图: 迭代算法，初始 \(R_i = 1/N\)
特殊处理: 无出链节点添加自环，避免 PageRank 泄漏
基本 PageRank 的问题
- Spider Trap: 非强连通图中，PageRank 积累在下游节点，其余归零
- 不收敛: 即使强连通图，迭代也可能不收敛（如 4 节点循环图的反例）
收敛条件: 无向图需连通且非二部图；有向图需强连通才有唯一均衡值
无向图均衡值: \(R_i = \frac{d_i}{2m}\)（度数正比）
Scaled PageRank（实际使用版本）
更新规则: \[R_j^{new} = \alpha \sum_{i \to j} \frac{R_i}{d_i} + \frac{1-\alpha}{N}\]
- \(\alpha\) 通常取 0.85
- 先用基本规则更新并乘以 α，再将 (1-α) 均匀分配给所有节点
直觉: 如同水循环中的蒸发-降雨，防止 PageRank 在下游积累
随机游走解释: 每步以概率 α 跟随随机出链，以概率 1-α 跳转到随机页面
矩阵形式: \(\tilde{W} = \alpha W + \frac{1-\alpha}{N} \mathbf{e}^T \mathbf{e}\)
关键性质: - 等价于完全图（\(\tilde{W}\) 无零元素）→ 必然强连通 → 必有唯一均衡值 - 即使初始值全为 0 也能收敛（每步注入 1-α 的新 PageRank） - 误差以 \(\alpha^K\) 衰减 - 均衡值: \(\mathbf{r} = \frac{1-\alpha}{N} \mathbf{e} (I - \alpha W)^{-1}\)
\((I - \alpha W)\) 可逆的证明: 该矩阵严格对角占优（对角线值 = 1 > 行内其余元素之和 = α < 1）
Personalized PageRank (PPR)
与 Scaled PageRank 唯一区别: 随机跳转时不跳到所有页面，而是跳到预选目标集 S
公式: 将均匀分布 \(\frac{1}{N}\mathbf{e}\) 替换为个性化向量 \(\mathbf{s}\)
PPR 矩阵: n×n 矩阵，第 i 行 = 以节点 i 为目标的 PPR 值；Scaled PageRank = 所有行的平均
优势: 比最短路径更精细——能区分同距离的节点
广义 PageRank（可选）
- 不同长度随机游走赋予不同权重
- Heat Kernel: 赋予长度 L 的随机游走权重 \(e^{-t} \cdot t^L / L!\)
- 也可用机器学习方法学习权重
关键考点提醒
- 证明题: Strong Triadic Closure → 局部桥为弱连接（反证法）；Balance Theorem
- 计算题: PageRank 均衡值（线性方程组）、Edge Betweenness（手算）、Modularity、Neighbourhood Overlap
- 概念辨析: Bridge vs Local Bridge、强连通分量、Homophily 检测、Scaled vs Basic PageRank
- 算法理解: BFS、Girvan-Newman、Hub-Authority 更新规则、Scaled PageRank 迭代
- 矩阵表示: 邻接矩阵、行随机矩阵 W、\(AA^T\) 与特征向量的关系