Directed Network Clustering
大白话：把「谁把信息传给谁」的有向网络分成几块，让「块与块之间传递得最不均衡」——因为方向本身带信息（信息从 A 流向 B 不等于反向），这是无向聚类做不到的。
定义。 对有向加权图 G = (V, E, A)（邻接矩阵 A 不对称）做节点划分， 找 k-partition C_1, \ldots, C_k 以最大化某种「块结构」指标。 与无向聚类的关键区别：目标函数可以利用边的方向， 例如「最大化两两之间的流不平衡」或「最大化有向模块度」。
目标函数谱系
| 目标 | 代表算法 | 适用场景 |
|---|---|---|
| 边密度（无方向） | 朴素对称化 A + A^\top + 谱方法；无向图上的 Louvain / Leiden | 只关心「是否相连」 |
| 入 / 出共现 | 文献计量式对称化 (Satuluri 2011) | 节点有相似的入邻居 / 出邻居 |
| 发送方 vs 接收方共聚类 | DI-SIM (Rohe 2016) | 找两类划分：发送者 + 接收者 |
| 流不平衡 | Hermitian 谱方法 (Cucuringu 2020) | 直接优化「成对流向」——lead-lag / 排名场景 |
| 模块度（有向） | Leiden (Traag 2019) + 有向模块度 (Dugué 2015) | 社区发现，但不优化「流」 |
| 基于 motif | Underwood 2020 | 高阶结构（前馈环等） |
Cut imbalance 形式化
对有向图邻接 A，两个簇 C_a, C_b 之间的流不平衡为： \Delta_{ab} = \text{Cut}(C_a, C_b) - \text{Cut}(C_b, C_a) = \sum_{i \in C_a, j \in C_b} (A_{ij} - A_{ji}) 总目标： \max \sum_{a < b} \Delta_{ab} = \max \sum_{a < b} |\text{Cut}(C_a, C_b) - \text{Cut}(C_b, C_a)| Hermitian 谱方法是这个目标（或其归一化版本）的最优谱松弛 (Cucuringu 2020)。
与 symmetric 谱聚类的差异
标准谱聚类跑对称邻接，取最大特征值对应的特征向量（Fiedler 向量），找「最小割」。 Hermitian 则利用反对称部分 A - A^\top，取模最大的特征值 （特征值可能是复数，但 Hermitian 矩阵保证实特征值），找「最大流」。
在 lead-lag 上的算法选型 (Bennett 2022 §3.2 / §4.3)
| 算法 | 线性 DGP | 余弦 DGP | 美股 ARI |
|---|---|---|---|
| 朴素对称化 | ~0.5 | ~0.2 | （基线） |
| 文献计量式对称化 | ~0.7 | ~0.5 | 中等 |
| DI-SIM 共聚类 | ~0.95 | ~0.85 | 接近 Hermitian |
| Hermitian RW | ~0.99 | ~0.9 | 最优 |
| Leiden（有向模块度） | 不适合（模块度基于密度） | — | — |
结论：涉及「流」的场景（lead-lag、排序、PageRank 类）用 Hermitian； 纯社区发现用 Leiden；找发送方 / 接收方两类划分用 DI-SIM。
邻近概念
- Lead-Lag Detection —— 上游的成对度量
- Hermitian Spectral Clustering —— 推荐算法
- Meta-Flow Graph —— 聚类结果的可视化
- Cartea Cucuringu Jin 2023 SPONGE —— 带符号图聚类的变体
起源 / 标准文献
- Cucuringu, Li, Sun, Zanetti (2020) "Hermitian matrices for clustering directed graphs" —— Hermitian 谱方法的原型
- Rohe, Qin, Yu (2016) "Co-clustering directed graphs" —— DI-SIM
- Satuluri & Parthasarathy (2011) —— 文献计量式对称化
- Traag, Waltman, van Eck (2019) "From Louvain to Leiden" —— Leiden 的改进
- Dugué & Perez (2015) —— 有向模块度
- Bennett, Cucuringu, Reinert (2022) —— 金融 lead-lag 系统的横向对比（本 wiki 摘要）
- Marti et al. (2019) —— 同步相关网络聚类综述
待研究问题
- 簇数 k 的自动选择：能否把 |\lambda_{k+1}| - |\lambda_k| 的谱间隙与 BIC 结合起来？
- Hermitian 谱对异质的出 / 入度分布是否仍然鲁棒（即度归一化的最优形式是什么）？
- 与图神经网络 (He 2021 DGCN / MagNet) 联合，能否把节点特征融进 Hermitian 谱分解？