Directed Network Clustering
Definition. 对有向加权图 G = (V, E, A) (邻接矩阵 A 不对称) 做节点划分, 找 k-partition C_1, \ldots, C_k 最大化某种"块结构"指标。关键区别于无向聚类: 目标函数可以利用边方向, 例如"最大化两两 flow imbalance"或"最大化 directed modularity"。
目标函数谱系
| 目标 | 代表算法 | 适用场景 |
|---|---|---|
| Edge density (无方向) | Naive symmetrisation A + A^\top + spectral; Louvain / Leiden on undirected | 只关心"是否相连" |
| In/Out co-occurrence | Bibliometric symmetrisation (Satuluri 2011) | 节点有相似入/出邻居 |
| Co-clustering send vs receive | DI-SIM (Rohe 2016) | 找两类划分: senders + receivers |
| Flow imbalance | Hermitian spectral (Cucuringu 2020) | 直接优化"成对流向" — lead-lag / 排名场景 |
| Modularity (directed) | Leiden (Traag 2019) + directed modularity (Dugué 2015) | 社区发现, 但不优化"流" |
| Motif-based | Underwood 2020 | 高阶结构 (feed-forward loop 等) |
Cut imbalance 形式化
对有向图邻接 A, 两个 cluster 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 spectral 是这个目标 (或其归一化版本) 的谱松弛最优 (Cucuringu 2020)。
与 symmetric 谱聚类的差异
标准 spectral clustering 跑对称邻接, 取最大特征值对应的特征向量 (Fiedler 向量), 找"最小 cut"。Hermitian 利用反对称部分 A - A^\top, 取最大模特征值 (可能是复数, 但 Hermitian 保证实特征值), 找"最大流"。
在 lead-lag 上的算法选型 (Bennett 2022 §3.2 / §4.3)
| 算法 | Linear DGP | Cosine DGP | 美股 ARI |
|---|---|---|---|
| Naive symmetrisation | ~0.5 | ~0.2 | (基线) |
| Bibliometric symmetrisation | ~0.7 | ~0.5 | 中等 |
| DI-SIM co-clustering | ~0.95 | ~0.85 | 接近 Hermitian |
| Hermitian RW | ~0.99 | ~0.9 | 最优 |
| Leiden (directed modularity) | 不适合 (modularity 基于密度) | — | — |
结论: 涉及"流"的场景 (lead-lag、ranking、PageRank-like) 用 Hermitian; 纯社区发现用 Leiden; 找 send/recv 两类划分用 DI-SIM。
邻近概念
- Lead-Lag Detection — 上游 pairwise metric
- Hermitian Spectral Clustering — 推荐算法
- Meta-Flow Graph — 聚类结果可视化
- Cartea Cucuringu Jin 2023 SPONGE — signed graph 聚类变体
起源 / 标准文献
- Cucuringu, Li, Sun, Zanetti (2020) "Hermitian matrices for clustering directed graphs" — Hermitian spectral 原型
- Rohe, Qin, Yu (2016) "Co-clustering directed graphs" — DI-SIM
- Satuluri & Parthasarathy (2011) — Bibliometric symmetrisation
- Traag, Waltman, van Eck (2019) "From Louvain to Leiden" — Leiden 改进
- Dugué & Perez (2015) — Directed modularity
- Bennett, Cucuringu, Reinert (2022) — 金融 lead-lag 系统对比 (本 wiki 摘要)
- Marti et al. (2019) — 同步相关网络聚类综述
Open Questions
- 聚类数 k 自动选择: 能否用 |\lambda_{k+1}| - |\lambda_k| 谱间隙 + BIC 联合?
- Hermitian 谱对异质性出/入度分布是否仍鲁棒 (即度归一化的最优形式)?
- 与 Graph Neural Network (He 2021 DGCN / MagNet) 联合, 能否把节点特征融入 Hermitian 谱分解?