COMP5313 考试 Cheatsheet — 六大模块速查

覆盖 Week 1-6，按六大知识模块组织，供考场快速回顾。 教材：Networks, Crowds, and Markets (Easley & Kleinberg) + Mining of Massive Datasets Ch5 + Barabási Network Science

---

一、图与网络基础（Graph Basics）

1.1 基础定义

• 图（Graph）：\(G = (V, E)\)，节点集 \(V\)、边集 \(E\)
• 邻居（Neighbors）：若 \((u,v) \in E\)，则 \(u, v\) 互为邻居
• 度（Degree）：节点连接的边数；有向图分出度 \(d^{out}\)、入度 \(d^{in}\)
• 无向图：边对称；有向图：边有方向（Web、Twitter 关注）
• 应用：社交（Facebook）、通信（Arpanet）、信息（Web）、生物（PPI）

1.2 路径与环

• 路径（Path）：节点序列，相邻节点间有边
• 简单路径（Simple Path）：不重复节点
• 环（Cycle）：首尾相同的路径，长度 ≥ 3
• 路径长度：边数
• 距离 \(d(u,v)\)：最短路径长度
• 直径（Diameter）：\(\max_{u,v} d(u,v)\)

1.3 连通性

• 连通（Connected）：无向图中任意两节点有路径
• 连通分量（Connected Component, CC）：极大连通子图
• 巨分量（Giant Component）：占节点相当比例的大分量；通常只有一个——两个巨分量只需 1 条边即合并
• 有向图：
  • 强连通（Strongly Connected）：任意两点互有有向路径
  • 强连通分量（SCC）：极大强连通子图

Week 6 Tutorial: PageRank 题解

课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 主题：PageRank 的定义与计算 依据教材 Networks, Crowds, and Markets（Easley & Kleinberg）第 14.3 节

---

一、预备知识回顾

1.1 基本 PageRank 更新规则（Basic PageRank Update Rule）

网络有 \(n\) 个节点，所有节点初始 PageRank 值为 \(1/n\)。

更新规则： > 每个页面将其当前 PageRank 均等地（equally）分给每条出链（out-going link），送给其指向的页面。若某页面没有出链，则把自己的 PageRank 全部传给自己（即保留不变）。

数学形式： \[v'_i = \sum_{j \to i} \frac{v_j}{d_j^{out}}\] 其中 \(d_j^{out}\) 为节点 \(j\) 的出度；若 \(d_j^{out}=0\) 则 \(v'_j = v_j\)（保留自身）。

矩阵形式：\(v' = M v\)，其中 \(M\) 是列随机的转移矩阵（column-stochastic transition matrix）。

1.2 均衡 PageRank 值（Equilibrium PageRank）

Week 5 Tutorial: Hub and Authority 题解

课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 主题：理解 Hub and Authority 更新规则如何影响网页排名 依据教材 Networks, Crowds, and Markets 第 14 章

---

一、预备知识回顾

1.1 HITS 算法核心思想

Hubs and Authorities 算法将网页的重要性分为两个互补维度：

• 权威（Authority）：内容上被认可为高质量信息来源的页面（如 Cornell 主页之于查询 "Cornell"）
• 中枢（Hub）：本身不一定是权威，但指向许多权威页面的"列表型"页面（如"十大最佳新闻网站"）

两者是相互递归定义（Mutually Recursive Definition） 的：

"好的中枢指向许多好的权威；好的权威被许多好的中枢指向。"

1.2 更新规则（Update Rules）