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

Posted on 2026-04-16 Edited on 2026-10-02 In Course Notes , COMP5313 Word count in article: 7.1k Reading time ≈ 26 mins.

COMP5313 考试 cheatsheet，按六大模块（图与网络基础、局部结构、强弱联系、PageRank/HITS、社群与图划分、拍卖与博弈）整理知识点、公式、思路与做题步骤，配合 Easley & Kleinberg《Networks, Crowds, and Markets》教材使用。

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）
原始版本查询相关（每个查询重算）
适合 prominent pages 不直接互相链接、需要 hub 页面连接 authority 的场景
与 PageRank 区别：HITS 每页两个分数；PageRank 每页一个全局重要性分数

6.2 PageRank 基本版

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

Equilibrium / 固定点：PageRank 的均衡值不是任意概率向量，而是满足"更新一次后不变"的概率分布。

归一化：\(\sum_i v_i = 1\)
Basic PageRank：\(\mathbf{v} = M\mathbf{v}\)
Scaled PageRank：\(\mathbf{v} = \alpha M\mathbf{v} + \dfrac{1-\alpha}{n}\mathbf{1}\)
\(n\)：图中节点 / 页面总数

做题时可以理解为：Basic 用 \(\mathbf{v} = M\mathbf{v}\)；Scaled 就把右边的 \(M\mathbf{v}\) 换成 \(\alpha M\mathbf{v} + \dfrac{1-\alpha}{n}\mathbf{1}\)，再配合 \(\sum_i v_i = 1\) 解方程。

公式（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 约定）。

小图手算：

给每个节点写入链方程：\(v_i = \sum_{j \to i} v_j/d_j^{out}\)
加归一化：\(\sum_i v_i = 1\)
解线性方程；若图很小，也可设某个节点为 \(x\)，沿出链推出其他节点，再用总和为 1 求 \(x\)

老师强调：

Basic PageRank 只是理论基础，实际使用的是 Scaled PageRank
强连通图保证 equilibrium 唯一，但 Basic 迭代仍可能因周期结构振荡
无向连通非二部图的 Basic PR equilibrium：\(v_i = d_i/(2m)\)

6.3 PageRank 的问题

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

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

Spider Trap 直觉：如果某些下游 SCC 可达但不能回到其他部分，Basic PR 会积累到这些底部 SCC，其他节点趋近 0。

6.4 Scaled PageRank【实际使用版本】

更新公式：

\[v'_i = \alpha (M\mathbf{v})_i + \frac{1-\alpha}{n}\]

\(\alpha\)：阻尼因子，\(0 < \alpha < 1\)，常用 \(0.85\)
\(n\)：图中节点 / 页面总数
\(\dfrac{1-\alpha}{n}\)：每个节点每轮获得的 teleport 基础量

均衡方程：

\[\mathbf{v} = \alpha M\mathbf{v} + \frac{1-\alpha}{n}\mathbf{1}, \quad \sum_i v_i = 1\]

为什么解决问题：

先按 Basic PR 传递，再把结果乘 \(\alpha\)
剩余 \(1-\alpha\) 平均分给所有节点，相当于每轮往网络注入新 PR
等价于把任意图变成带权 complete graph，因此有唯一 equilibrium
即使初始全 0，第一轮后每个节点也得到 \((1-\alpha)/n\)

Random Surfer 解释：

以概率 \(\alpha\) 沿当前页面随机出链走
以概率 \(1-\alpha\) 随机跳到任意页面
长期停留在某页面的比例就是该页面 Scaled PR

6.5 Personalized PageRank

用途：衡量节点相对于某个目标节点 / 目标集合 \(S\) 的重要性，而不是全局重要性。

和 Scaled PR 的区别：teleport 不跳到所有页面，而是跳到预选集合 \(S\)。

公式：

\[\mathbf{v} = \alpha M\mathbf{v} + (1-\alpha)\mathbf{s}\]

\(\mathbf{s}\) 是 teleport distribution
若只关注节点 \(a\)：\(s_a=1\)，其他为 0
若关注两个节点 \(a,b\)：\(s_a=s_b=1/2\)，其他为 0
Scaled PR 是特殊情况：\(\mathbf{s}=\frac{1}{n}\mathbf{1}\)

6.6 Web 图蝴蝶结结构

Broder et al. 1999：

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

七、图机器学习与 GNN（Week 07-08）

7.1 Graph ML 典型任务

核心思想：把离散图结构映射到连续向量空间；节点向量叫 node embedding，整图向量叫 graph embedding。

层级	任务	例子
节点	Node Classification	预测论文主题
边	Link Prediction	Knowledge graph 补全
社区	Community Detection	无监督划分节点
图对	Graph Similarity	比较两张图相似度
整图	Graph Classification	分子是否 toxic

传统流程：手工构造 feature matrix（degree / PageRank / clustering coefficient 等）→ 普通 ML。缺点是人工 feature engineering 且图结构常被丢掉。

图数据难点：节点数不固定、degree 不同、无固定 node ordering、无固定 reference point。

7.2 GNN 与 Neighbourhood Aggregation

Node classification 输入：

图 \(G=(V,E)\)，邻接矩阵 \(A\)
节点特征矩阵 \(X \in \mathbb{R}^{n \times q}\)
部分节点有 ground-truth labels
\(C\) 类分类通常用 one-hot label

GNN 核心：预测节点 \(u\) 时，使用 \(u\) 自己和邻居的表示；\(K\) 层 GNN 使用 \(K\)-hop neighbourhood。

通用两步：

Aggregate：聚合邻居上一层表示
Combine：把邻居 message 和自己上一层表示合并

GCN 层公式：

\[H^{(k)}=\sigma\left(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}H^{(k-1)}W^{(k)}\right)\]

\(\tilde A=A+I\)：给每个节点加 self-loop
同一层所有节点共享 \(W^{(k)}\)
参数数量不依赖节点数 \(n\)
每层传播一次，复杂度约 \(O(|E|)\)
可泛化到 unseen nodes

7.3 GraphSAGE / GIN / Graph Embedding

GraphSAGE：

Aggregate 邻居表示：mean / max / LSTM 等
Combine：常用 concat，把自己上一层表示和邻居 message 拼接

GIN：

使用 sum aggregator
sum 比 mean / max 更 expressive：mean 和 max 可能无法区分不同 multiset，sum 保留更多数量信息

Graph Embedding：

先得到每个节点 embedding
对节点 embeddings 做 sum / mean
得到整张图向量，用于 graph classification

7.4 Label Propagation

假设：Homophily，相连节点倾向属于同类。

二分类时，用 \(p_v\) 表示节点 \(v\) 属于 class 1 的概率：

\[p_v^{(k)}=\frac{1}{d_v}\sum_{u\in N(v)}p_u^{(k-1)}\]

初始化：

class 1 训练节点：\(p_v=1\)
class 0 训练节点：\(p_v=0\)
未标注节点：\(p_v=0.5\)

预测：\(p_v>0.5\) 预测 class 1；\(p_v<0.5\) 预测 class 0；相等则任选。

与 PageRank 区别：

Label Propagation：pull 邻居平均，用目标节点度数 \(d_v\) 归一化
PageRank：source node 把分数 push 给出链，用源节点出度 \(d_u^{out}\) 归一化
更新顺序不影响结果：第 \(k\) 轮只用第 \(k-1\) 轮的值

7.5 Correct and Smooth

用途：把 label propagation 作为 post-processing，提高已有模型预测。

训练 base predictor（MLP / GNN 等）
输出每个节点的 soft labels
Correct：在训练节点上算 error = ground truth - soft label，把 error 沿图传播，再加回 soft labels
Smooth：把训练节点 reset 为 ground truth，再沿图传播 labels
最终比较各类别分数大小；分数不一定严格和为 1

7.6 PPR / APPNP / Feature Propagation

GNN 限制：

\(K\) 小：只看 \(K\)-hop，范围有限
\(K\) 大：over-smoothing，节点表示变得太相似

APPNP 高层思路：

先用 MLP 对每个节点输出预测
再用 PageRank-style propagation 传播预测 \(K\) 步
用 PPR 思想给更相关的节点更高权重

SGC：

去掉 GCN 的 nonlinear activation
先预计算传播后的特征：\(\tilde A^K X\)
再训练普通分类器 / MLP
propagation 无可训练参数，可作为 preprocessing

AGP：对不同长度的 feature propagation 做 weighted sum；exact formula 不重要，理解为 generalized feature propagation。

八、网络动力学与去中心化搜索（Week 09-11）

8.1 Information Cascade

定义：人们按顺序决策，后面的人能看到前面人的行动，但看不到前面人的私人信息。当公共行动信息足够强时，后面的人会忽略自己的私人信号，直接模仿前人。

重点区分：

Informational effects：别人可能有我不知道的信息，所以我跟随。
Direct-benefit / network effects：别人使用会直接提高我使用的收益。

本讲考的是 informational effects。

Urn / Herding 实验：

两种状态：多数红 / 多数蓝，先验各 \(1/2\)
每人抽一次球，抽完放回
每人只看自己的球色和前面人的猜测
如果前两个人都猜蓝，第三个人即使抽到红也会猜蓝，cascade 开始

Bayes rule：

\[P(A\mid B)=\frac{P(A)P(B\mid A)}{P(B)}\]

老师强调要会用 posterior 做决策，而不是只看单个信号。

8.2 General Cascade Model

设世界状态为 Good / Bad，私人信号为 High / Low：

\(P(G)=p\)
\(P(H\mid G)=q\)
\(P(L\mid B)=q\)
\(q>1/2\)
动作：accept / reject

如果已经透露的信息里 high signals 数量为 \(a\)，low signals 数量为 \(b\)：

条件	动作
\(a>b\)	accept
\(b>a\)	reject
\(a=b\)	indifferent / tie-breaking

Cascade 条件：

当 accept/reject 透露出来的信号差距不超过 1，后续行动还能透露私人信号。
当差距达到 2，cascade takes over。
之后所有人忽略自己的私人信号。

概率结论：

连续 3 个相同信号一定触发 cascade。
人数增长时，发生 cascade 的概率趋近 1。
老师说详细证明不是重点，记结论和 Bayes 计算。

8.3 Power Law Distribution

定义：

\[f(k)\approx \frac{A}{k^c}\]

\(f(k)\)：value / degree 等于 \(k\) 的节点比例
\(c\)：power-law exponent
Web 入链、城市人口、论文引用、音乐下载等都可能出现 power law

Log-log 检测：

\[\log f(k)=\log A-c\log k\]

如果 \(\log f(k)\) 对 \(\log k\) 近似直线，则可能是 power law；斜率为 \(-c\)。

Preferential Attachment / Rich-get-richer：

节点越流行，未来越容易获得新链接。
新链接选择目标的概率与目标当前 popularity / in-degree 成比例。
早期小差异会被放大，所以最终谁最流行可能很偶然。

8.4 Small World 与 Decentralized Search

Small world 要同时解释三件事：

社交网络有很多三角形。
任意两点之间有短路径。
人们只用局部信息也能找到短路径。

Greedy routing：

每个节点只知道自己的邻居和目标位置。
当前节点把消息转给距离目标最近的邻居。
这是 decentralized search，不需要全图信息。

Watts-Strogatz 直觉：

Homophily / local links 产生很多三角形。
Weak ties / random links 产生短路径。
但完全随机 weak ties 缺少结构，不一定适合 greedy search。

8.5 Kleinberg Model

二维 grid 上，节点 \(u\) 到 \(v\) 的长程边概率：

\[P(u\to v)\propto d(u,v)^{-q}\]

\(q\) 是 clustering exponent。
\(q=0\)：长程边完全随机。
\(q\) 越大，边越偏向短距离。
二维 grid 中 decentralized search 最有效时 \(q=2\)。

为什么 \(q=2\)：

距离 \(d\) 到 \(2d\) 的 ring 中，节点数约与 \(d^2\) 成正比。
连接概率 \(d^{-2}\) 正好抵消节点数量增长。
每个距离尺度都有差不多机会获得 weak tie。
搜索可以按尺度逐步接近目标。

8.6 Rank-based Friendship

真实人口分布不均匀，所以用 rank 代替距离。

对节点 \(v\) 来说：

\[\text{rank}_v(w)=\#\{\text{比 }w\text{ 更接近 }v\text{ 的节点}\}\]

连接概率：

\[P(v\to w)\propto \text{rank}_v(w)^{-p}\]

在 uniform 2D grid 中，\(\text{rank}\approx d^2\)，所以 \(p=1\) 对应 Kleinberg 的 \(q=2\)。

结论：高效 decentralized search 需要连接概率大约与 closer nodes 数量成反比，即 \(1/\text{rank}\)。

8.7 Distributed Hash Table / Consistent Hashing

Lookup problem：给定 key，在没有中心服务器的情况下，找到负责该 key 的 computer node。

DHT 比普通 hash table 多一步：

普通 hash table：get(key) 找 value。
DHT：先 lookup(key) 找负责 key 的 computer，再取 value。

8.8 Chord Ring

设 ID 和 key 都用 \(m\) bits 表示，ID space 大小是 \(2^m\)。

Consistent hashing：

把 nodes 和 keys hash 到同一个 circular ID space。
nodes 按顺时针 ID 递增排列。
key \(k\) 存在顺时针第一个 ID \(\ge k\) 的 node 上，即 successor。

如果每个 node 只知道 successor，lookup 最坏要 \(O(n)\)。

8.9 Finger Table 与 Chord Lookup

node \(i\) 的第 \(j\) 个 finger 指向负责下面 key 的 node：

\[i+2^{j-1}\pmod{2^m}\]

lookup 原则：

Go as far as possible, but never pass the target.

做题步骤：

看 key 是否在当前 node 和 successor 之间；如果是，交给 successor。
否则从 finger table 中选不超过 key 的最大 ID。
转发请求，重复直到找到 successor。

复杂度：

lookup time：\(O(\log n)\)
每节点空间：\(O(\log n)\)

8.10 CAN

CAN 把 key 和 node 放到 \(d\) 维空间：

每个 node 负责一个 zone。
key 落在哪个 zone，就由该 node 负责。
routing 时转发给欧氏距离目标最近的邻居。

复杂度：

lookup：\(O(dn^{1/d})\)
每节点空间：\(O(d)\)

CAN 细节不是重点，记思想和复杂度即可。

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

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

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

9.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}\)
Basic PR equilibrium	\(\mathbf{v}=M\mathbf{v},\ \sum_i v_i=1\)
无向图 Basic PR	\(v_i = d_i/(2m)\)
Scaled PR	\(v'_i = \alpha (Mv)_i + (1-\alpha)/n\)
Scaled PR equilibrium	\(\mathbf{v}=\alpha M\mathbf{v}+\dfrac{1-\alpha}{n}\mathbf{1},\ \sum_i v_i=1\)
Personalized PR	\(\mathbf{v}=\alpha M\mathbf{v}+(1-\alpha)\mathbf{s}\)
GCN layer	\(H^{(k)}=\sigma(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}H^{(k-1)}W^{(k)})\)
Label Propagation	\(p_v^{(k)}=\dfrac{1}{d_v}\sum_{u\in N(v)}p_u^{(k-1)}\)
SGC feature propagation	\(\tilde A^K X\)
Bayes rule	\(P(A\mid B)=\dfrac{P(A)P(B\mid A)}{P(B)}\)
Cascade decision	\(a>b\Rightarrow accept,\ b>a\Rightarrow reject\)
Power law	\(f(k)\approx A/k^c\)
Power law log-log	\(\log f(k)=\log A-c\log k\)
Kleinberg long-range link	\(P(u\to v)\propto d(u,v)^{-q}\)
Rank-based friendship	\(P(v\to w)\propto \text{rank}_v(w)^{-p}\)
Chord finger entry	\(i+2^{j-1}\pmod{2^m}\)
Chord lookup / space	\(O(\log n)\) / \(O(\log n)\)
CAN lookup / space	\(O(dn^{1/d})\) / \(O(d)\)
Spam Farm 放大	\(y = x/(1-\beta^2) + \beta/(1+\beta) \cdot m/n\)

祝考试顺利！