COMP5313 考试 Cheatsheet（六大模块复习）

Posted on 2026-04-16 In Course , COMP5313 Word count in article: 4.2k Reading time ≈ 15 mins.

COMP5313 考试 Cheatsheet — 知识点 / 公式 / 做题思路

按六大模块组织，每个模块提供：知识点 → 公式 → 思路 → 做题步骤。教材：Networks, Crowds, and Markets (Easley & Kleinberg)

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

1.1 基本概念

知识点：

图 \(G=(V,E)\)：节点 \(V\)、边 \(E\)
无向图 / 有向图
度（Degree）：节点的边数；有向图分 \(d^{out}\)、\(d^{in}\)
邻居（Neighbors）：相邻节点

路径相关：

路径（Path）：节点序列 \(v_0, v_1, \dots, v_k\)，每对相邻有边
简单路径：不重复节点
环（Cycle）：首尾相同的路径
距离 \(d(u,v)\)：最短路径长度
直径：\(\max_{u,v} d(u,v)\)

1.2 连通性

知识点：

连通分量（CC）：无向图中极大连通子图
巨分量（Giant Component）：占节点相当比例；通常只有一个——两个巨分量只需 1 条边即合并
有向图：
- 强连通分量（SCC）：沿方向可互达的极大子图
- 蝴蝶结构 (Bow-Tie Structure)：
  - 强连通分量 (SCC, Strongly Connected Component)：约占网页 27%，形成网络的核心
  - 入分量 (In-Component)：能到达 SCC 但不能从 SCC 返回的网页（约 21%）
  - 出分量 (Out-Component)：能从 SCC 到达但不能被 SCC 到达的网页（约 21%）
  - 须条 (Tendrils)：连接到 In 和 Out 的网页
  - 管道 (Tubes)：直接连接 In 到 Out 的网页
  - 孤立分量 (Disconnected Components)：与其他部分无连接

1.3 BFS 广度优先搜索

思路：逐层展开，每层到起点距离相同。

核心性质：

层 \(d\) 的节点到起点距离为 \(d\)
无向图中，边只连同层或相邻层
复杂度 \(O(|V|+|E|)\)

二、社交网络局部结构（Local Structure）

2.1 三元闭包与聚类系数

知识点：若 \(A\)-\(B\)、\(A\)-\(C\) 是朋友，则 \(B\)-\(C\) 更可能成为朋友。

公式（聚类系数）：

\[C(v) = \frac{v \text{ 的朋友之间实际的边数}}{\binom{d_v}{2}} = \frac{2 \cdot |\{(u,w): u,w \in N(v), (u,w) \in E\}|}{d_v(d_v-1)}\]

范围：\([0, 1]\)。三元闭包活跃 → \(C(v)\) 高。

设节点 A 有 \(k\) 个邻居（朋友）
A 的邻居之间最多可以形成 \(\binom{k}{2} = \frac{k(k-1)}{2}\) 条边
设实际形成的边数为 \(e_A\)
则聚类系数 \(C_A = \frac{2e_A}{k(k-1)}\)

情景 (a)：节点 A 有 4 个邻居 B、C、D、E - 这 4 个邻居之间所有可能的边数：\(\binom{4}{2} = 6\) - 可能的边对：(B-C), (B-D), (B-E), (C-D), (C-E), (D-E) - 在该图中，实际只有 (C-D) 这一条边存在 - 聚类系数：\(C_A = \frac{1}{6} ≈ 0.167\)

2.2 强联系 / 弱联系 / 桥

知识点：

概念	定义
强联系（Strong Tie）	亲密、频繁、投入
弱联系（Weak Tie）	熟人、偶然接触
桥（Bridge）	删除后两端不连通——现实中极少
局部桥（Local Bridge）	两端无共同邻居的边
跨度（Span）	删除局部桥后两端的新距离

判定局部桥：\(A\)-\(B\) 是局部桥 \(\Leftrightarrow\) \(N(A) \cap N(B) = \emptyset\)（不算 \(A, B\) 本身）。

2.3 强三元闭包性质（STC）【必考】

定义：节点 \(A\) 满足 STC，若 \(A\) 有两个强联系 \(B, C\)，则 \(B\)-\(C\) 之间必有边（强或弱皆可）。

关键定理：若 \(A\) 满足 STC 且 \(\geq 2\) 个强联系，则 \(A\) 的所有局部桥必为弱联系。

反证法证明思路（必会）：

假设 \(A\)-\(B\) 是强的局部桥
\(A\) 还有另一强联系 \(A\)-\(C\)（因为 \(A\) 有 ≥ 2 个强联系）
由 STC，\(B\)-\(C\) 必有边
但这说明 \(B, C\) 有共同邻居 \(A\)... 更关键：\(C\) 本身就是 \(A, B\) 的共同邻居
与"\(A\)-\(B\) 是局部桥（\(N(A) \cap N(B) = \emptyset\)）"矛盾 ∎

典型题型：给一个带 S/W 标记的图，问某节点是否满足 STC，或某条无标签边应该是 S 还是 W。

做题步骤： 1. 找出所有强联系对 \((A, B)\) 和 \((A, C)\) 共享同一节点 \(A\) 2. 检查 \(B\)-\(C\) 之间是否有边 → 无则 \(A\) 违反 STC 3. 反推未标签边：若画出的局部桥两端都是 S，则违反 STC

2.4 邻域重叠与嵌入度（Neighborhood Overlap）

定义：对于任意边 (A, B)，其邻域重叠（Neighborhood Overlap） 定义为：

\[O(A,B) = \frac{|N(A) \cap N(B)|}{|N(A) \cup N(B)|}\]

其中： - \(N(A)\) 是节点 A 的邻居集合（不包括 B） - \(N(B)\) 是节点 B 的邻居集合（不包括 A） - 分子：A 和 B 的共同邻居数量 - 分母：A 和 B 的所有邻居总数（不重复计算）

特殊情况： - 如果 \(O(A,B) = 0\)，则 A 和 B 没有共同邻居，这条边就是一条局部桥 - 如果 \(O(A,B) = 1\)，则 A 的所有邻居都是 B 的邻居，反之亦然（高度重叠）

邻域重叠的解释： - 邻域重叠反映了一条边在多大程度上被嵌入在一个紧密的三角形网络中 - 高重叠意味着该边被许多三角形所包围（高度嵌入） - 低重叠意味着该边相对孤立（像一条局部桥）

嵌入度（Embeddedness）：一条边的共同邻居数（即分子部分）。\(Embeddedness(A,B) = |N(A) \cap N(B)|\)

2.5 结构洞与社会资本

知识点：

结构洞（Structural Hole）：节点位于多个不互动群体之间 → 掌控信息流
高嵌入度 → 信任、规范（bonding capital）
跨结构洞 → 信息、机会（bridging capital）

三、社区发现与图划分（Community Detection）

3.1 基本思路

目标：把网络分成紧密区域，区域间连接稀疏。

两大策略：

分裂式（Divisive）：移除跨区边 → 网络碎裂（Girvan-Newman）
聚合式（Agglomerative）：合并相似节点 → 自底向上（Ravasz、Louvain）

树状图（Dendrogram）：合并/分裂顺序形成的树，水平切割得到分区。

3.2 中介性（Betweenness）

公式（边中介性）：

\[b(e) = \sum_{s \neq t} \frac{\sigma_{st}(e)}{\sigma_{st}}\]

\(\sigma_{st}\)：\(s\) 到 \(t\) 的最短路径数量
\(\sigma_{st}(e)\)：上述路径中经过边 \(e\) 的数量

流量直觉：每对 \((s, t)\) 发送 1 单位流量，沿所有最短路径等分；\(b(e)\) 是流过 \(e\) 的总流量。

3.3 Edge Betweenness 手算三步法【必会】

步骤 1：从起点 \(A\) 做 BFS 分层

层 \(d\) = 距离 \(A\) 为 \(d\) 的节点

步骤 2：自顶向下数最短路径数 \(\sigma_A(X)\)

起点：\(\sigma_A(A) = 1\)
其他：\(\sigma_A(X) = \sum_{Y \in X \text{的上层邻居}} \sigma_A(Y)\)

步骤 3：自底向上分配流量

叶节点：自带 1 单位（它自己是终点）
节点 \(X\)：总流量 = \(1 + \sum\)（下层邻居传上来的流量）
把 \(X\) 的总流量按 \(\sigma_A(Y)/\sigma_A(X)\) 比例 分给上方每个邻居 \(Y\)

最后：对每个起点重复 → 所有流量求和 → 除以 2（每对被数两次）

3.4 Girvan-Newman 算法

算法流程：

算所有边的 betweenness
删最高 betweenness 的边（并列全删）
重算所有 betweenness（关键！因为结构变了）
若图分裂 → 记录此时的分区
重复直到所有边被删

复杂度：单次 betweenness 计算 \(O(nm)\)；完整算法 \(O(nm^2)\)。

典型题型：小图（10-15 节点）手算前几步移除哪条边，画出 dendrogram。

3.5 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\)：图的总边数

解释：

第一项 \(m_s/m\)：实际社区内边占比
第二项 \((D_s/2m)^2\)：随机图中期望占比
差值表示"超出随机"的社区强度

取值：\(Q \in [-1, 1]\)；\(Q > 0\) 表示有社区结构。

做题： 1. 对每个社区求 \(m_s\)（社区内的边数） 2. 求 \(D_s\)（社区内所有节点度数之和——注意跨社区的边也要算度数） 3. 代入公式累加

局限：

分辨率极限：小于 \(\sqrt{2L}\) 的小社区会被合并
模块度高原：最大值常不唯一

3.6 Louvain 算法（贪心最大化 Q）

思路：两阶段迭代

局部优化：每个节点尝试加入邻居社区中使 \(\Delta Q\) 最大的社区
粗化：社区缩为超级节点，回到步骤 1

复杂度：\(O(N \log^2 N)\)

四、网络形成与同质性（Homophily & Formation）

4.1 同质性（Homophily）

知识点：人们倾向与相似的人建立关系。

公式（2pq 测试）：

节点二分类：比例 \(p\) 为类 1、\(q\) 为类 2（\(p + q = 1\)）
随机图中跨组边的期望比例 \(= 2pq\)
实际跨组比例 < \(2pq\) → 存在同质性

做题步骤： 1. 数跨组边数 \(E_{\text{cross}}\) 和总边数 \(E_{\text{total}}\) 2. 算实际跨组比例 \(f = E_{\text{cross}} / E_{\text{total}}\) 3. 与 \(2pq\) 比较：\(f < 2pq\) → homophily 存在

两大驱动机制：

选择（Selection）：相似 → 结识（同质性的成因）
社会影响（Social Influence）：结识 → 变相似（反过来）

4.2 从属网络（Affiliation Network）

从属网络（Affiliation networks）表示个体参与哪些团体或活动的关系。这种网络的基本结构是二部图（Bipartite graph）：

一组节点代表个人（People）
另一组节点代表焦点/团体（Foci/Groups）
边仅在这两组之间存在；同组内部没有边

知识点：

二部图：人 ↔︎ 活动/组织
融合网络 = 社交网络 + 二部图
Focal Point：共同活动/焦点

4.3 三种闭包机制【概念辨析必考】

机制	描述	类型
三元闭包（Triadic）	共同朋友 → 成为朋友	选择
焦点闭包（Focal）	共同活动 → 成为朋友	选择
成员闭包（Membership）	朋友参加的活动 → 自己加入	社会影响

实证（email 数据）：共同朋友数 ↑ → 未来结交概率近线性上升。

4.4 Schelling 隔离模型

知识点：

网格上两类 agent（红/蓝）
阈值 \(T\)：同类邻居 ≥ \(T\) 才满意
不满意 → 迁移
惊人发现：即使 \(T=3\)（8 邻居中 3 个即可）也会出现大片同质区
结论：微弱个人偏好 → 宏观隔离

五、正负关系与结构平衡（Signed Networks）

5.1 知识点

符号图：每条边标 \(+\)（朋友）或 \(-\)（敌人）
三角形是否"平衡"取决于正负边的组合
整图平衡 → 节点可划分成两个友好派系、派系间敌对

一个 signed graph 是 balanced，当且仅当它的节点可以分成两个阵营，使得：

阵营内部全是正边；

阵营之间全是负边。

two-step approach 做题时怎么落地

lecture 里的正式版本会先看 positive edges、再压成 supernodes；但手算时更直观的等价写法是：

任选一个点放进阵营 X；
遇到正边，就把另一端放进同一阵营；
遇到负边，就把另一端放进另一阵营；
一直沿着图往外推；
如果某个节点被同时要求属于两个不同阵营，就说明图不 balanced。

你可以把它记成三句话：

正边：同组
负边：异组
推出矛盾：not balanced

5.2 三角形四种配置

平衡 \(\Leftrightarrow\) 正边数为奇数（1 或 3）
平衡 \(\Leftrightarrow\) 三边符号乘积 = +
平衡 \(\Leftrightarrow\) 负边数为偶数（0 或 2）

5.3 完全图的 Harary 平衡定理【必考必证】

定理：完全符号图平衡 \(\Leftrightarrow\) 节点可划分为两组 \(X, Y\)（允许 \(Y = \emptyset\)），满足：

组内所有边为 +
组间所有边为 −

证明思路（\(\Leftarrow\) 方向，简单）：

任取三角形 \((A, B, C)\)，三节点在 \(X, Y\) 中只有两种分布：

三个都在同组 → 3 条内部边全为 + → 平衡（3 正）✓
两个同组 + 1 个异组 → 2 条组间边为 −、1 条组内边为 + → 平衡（1 正 2 负）✓

证明思路（\(\Rightarrow\) 方向，构造性 BFS 法）：

核心思想：选任一节点 \(A\)，按"朋友/敌人"二分全图。

步骤：

选起点 \(A\)
定义 \(X = \{A\} \cup \{A \text{ 的朋友}\}\)，\(Y = \{A \text{ 的敌人}\}\)（完全图下每个节点与 \(A\) 有边）
证 \(X\) 内全正：取 \(B_1, B_2 \in X\)，三角形 \((A, B_1, B_2)\) 两条 \(A\)-边为 + → 需奇数正 → \(B_1\)-\(B_2\) 也为 + ✓
证 \(Y\) 内全正：取 \(C_1, C_2 \in Y\)，三角形 \((A, C_1, C_2)\) 两条 \(A\)-边为 − → 需奇数正 → \(C_1\)-\(C_2\) 为 + ✓
证 \(X\)-\(Y\) 间全负：取 \(B \in X, C \in Y\)，三角形 \((A, B, C)\) 中 \(A\)-\(B\) 为 +、\(A\)-\(C\) 为 − → 需奇数正 → \(B\)-\(C\) 为 − ✓

记忆："基点 \(A\) → 朋友归一队、敌人归另队 → 平衡条件自然推出两队内部全友、两队间全敌"

5.4 一般图（非完全）的平衡

关键定理：一般符号图平衡 \(\Leftrightarrow\) 图中不存在含奇数条负边的环。

证明思路：

\(\Rightarrow\)：分成 \(X, Y\) 两组后，任一环穿越两组的次数为偶数 → 负边数为偶数
\(\Leftarrow\)：从任一节点 BFS，按路径负边数奇偶性分组，无冲突即可染色

5.5 BFS 检验平衡性（做题必会）

一步法（直接 BFS 染色）：

从任一节点开始 BFS，给每个节点标 0 或 1：

遇 + 边：两端同组
遇 − 边：两端异组
矛盾 → 不平衡；无冲突 → 平衡

两步法（正边分量 + 缩点）：

Lecture 里的正式版本会先看正边（positive edges）、再压成 supernodes；但手算时更直观的等价写法是：

正边分量：只看正边找连通分量（supernodes）；若分量内部含负边 → 立即不平衡
缩点：supernode 缩为单点，原负边变为超图边；BFS 检查是否为二部图 → 二部 → 平衡

手算落地步骤：

任选一个点放进阵营 \(X\)
遇到正边，就把另一端放进同一阵营
遇到负边，就把另一端放进另一阵营
一直沿着图往外推
如果某个节点被同时要求属于两个不同阵营，就说明图不平衡

三句话记忆：

正边：同组
负边：异组
推出矛盾：不平衡

复杂度：\(O(|V| + |E|)\)

六、链接分析与搜索（Link Analysis）

6.1 HITS 算法（Hub & Authority）

知识点：

Authority：高质量内容页
Hub：指向许多好 authority 的列表页
双重递归定义：好 hub 指好 authority；好 authority 被好 hub 指

公式（更新规则）：

\[\text{auth}(p) \leftarrow \sum_{q \to p} \text{hub}(q)\]

\[\text{hub}(p) \leftarrow \sum_{p \to q} \text{auth}(q)\]

算法：

初始化所有 \(\text{hub} = \text{auth} = 1\)
交替应用两条更新规则 \(k\) 次
归一化（除以总和）

矩阵形式：

\(\mathbf{a} = L^T \mathbf{h}\)
\(\mathbf{h} = L \mathbf{a}\)
\(\mathbf{h}^{(k)} \propto (LL^T)^k \mathbf{h}^{(0)}\) → 收敛到 \(LL^T\) 主特征向量

做题步骤（k 步计算）：

可以省略的分数：
- 无出链的节点（如 \(A, B\) 只做 authority）：hub = 0，不用算
- 无入链的节点（如 \(C, D, E, F\) 只做 hub）：auth = 0，不用算
Round 1：先 auth 更新，再 hub 更新
Round 2：同上
归一化：auth 除以 auth 之和；hub 除以 hub 之和

关键性质：

无 dead end / spider trap 问题（不需 teleport）
原始版本查询相关（每个查询重算）

6.2 PageRank 基本版

知识点：每个页面均分 PR 到所有出链。

公式（Basic Update）：

\[v'_i = \sum_{j \to i} \frac{v_j}{d_j^{out}}\]

矩阵形式：\(\mathbf{v}' = M \mathbf{v}\)，\(M\) 是列随机矩阵（每列和 = 1）。

均衡条件：

\[\mathbf{v} = M \mathbf{v} \quad \text{且} \quad \sum_i v_i = 1\]

\(\mathbf{v}\) 是 \(M\) 的主特征向量（\(\lambda = 1\)）。

死端处理：若页面无出链 → PR 传给自己（Easley-Kleinberg 约定）。

6.3 PageRank 的问题

问题	描述	后果
死端（Dead End）	无出链节点	PR 泄漏，其他节点归 0
蜘蛛陷阱（Spider Trap）	有出链但永远出不去	PR 全部聚集在陷阱
不收敛	如周期性循环	PR 振荡

基本收敛条件：图强连通且非周期。

6.4 Web 图蝴蝶结结构

Broder et al. 1999：

SCC（56M）：核心，互达
IN（44M）：可达 SCC，反向不通
OUT（44M）：被 SCC 达，不能回
Tendrils / Tubes / Disconnected：周边

七、高频证明题（必背思路）

7.1 STC → 局部桥为弱联系（反证）

假设 \(A\)-\(B\) 是强局部桥
\(A\) 还有另一强联系 \(A\)-\(C\)
由 STC → \(B\)-\(C\) 有边
但 \(A\) 是 \(B, C\) 的共同邻居 → 违反局部桥定义
矛盾 ∎

7.2 Harary 定理（完全图）

\(\Rightarrow\)：基点 \(A\) → \(X=\{A\text{+朋友}\}\)、\(Y=\{A\text{的敌人}\}\) → 由平衡三角形推出组内全正、组间全负
\(\Leftarrow\)：任一三角形，三节点分组必出现"3 同组（3 正）"或"2+1（1 正 2 负）" → 奇数正边 → 平衡

八、核心公式速查

概念	公式
聚类系数	\(C(v) = \dfrac{2 m_v}{d_v(d_v-1)}\)
邻域重叠	\(O(A,B) = \dfrac{\|N(A)\cap N(B)\|}{\|N(A)\cup N(B) \setminus \{A,B\}\|}\)
边中介性	\(b(e) = \sum_{s \neq t} \dfrac{\sigma_{st}(e)}{\sigma_{st}}\)
模块度	\(Q = \sum_s \left[\dfrac{m_s}{m} - \left(\dfrac{D_s}{2m}\right)^2\right]\)
同质性检测	实际跨组比例 vs \(2pq\)
Authority 更新	\(\text{auth}(p) = \sum_{q \to p} \text{hub}(q)\)
Hub 更新	\(\text{hub}(p) = \sum_{p \to q} \text{auth}(q)\)
Basic PR	\(v'_i = \sum_{j \to i} v_j/d_j^{out}\)
Scaled PR	\(v'_i = \alpha (Mv)_i + (1-\alpha)/n\)
Spam Farm 放大	\(y = x/(1-\beta^2) + \beta/(1+\beta) \cdot m/n\)

祝考试顺利！