Details: Star spread & merging

下面把 star spread 与 star merging 整理成一套完整、可执行的伪代码。为保持与论文一致，符号尽量沿用原文：$S_v$ 为星，$S_v^s$ 为谱划分后的簇，$\beta$ 为相对阈值，$\gamma$ 为 Personalized PageRank 传送概率，$\varepsilon$ 为 push 残差阈值。

---

0. 数据结构与总体流程

输入：

• $k$ 个 PPI 网络 $G_1,\ldots,G_k$；
• 功能相似图 $G_{\text{sim}}$：$k$ 部完全加权图，边权 $w(v_i,v_j)=R_{ij}$ 由原版 IsoRank 给出；
• 阈值 $\beta$（论文取 0.01）；
• PR 参数 $\gamma$、push 精度 $\varepsilon$；
• 物种处理顺序 $\pi$（如人、鼠、蝇、线虫、酵母）。

输出：

• 簇集合 $\mathcal{C}=\{C_1,C_2,\ldots\}$，每个簇是跨物种蛋白集合；
• 每个蛋白最终属于一个簇。

总体流程：

IsoRankN(G_1,...,G_k, G_sim, β, γ, ε, π):
1.  C ← ∅                                  // 已形成的簇
2.  assigned ← ∅                           // 已分配蛋白
3.  for each species G_L in order π:
4.      ComputeStars(G_L, G_sim, β)        // 计算 G_L 中每个 v 的星 S_v
5.      order proteins v ∈ G_L \ assigned
        by weight_sum(S_v) descending
6.      for each v in this order:
7.          if v ∈ assigned: continue
8.          S_v^s ← SpectralPartition(S_v, G_sim, γ, ε)
9.          if S_v^s \ {v} ≠ ∅:
10.             C_new ← (S_v^s \ assigned) ∪ {v}   // 只分配未分配蛋白
11.             C ← C ∪ {C_new}
12.             assigned ← assigned ∪ C_new
13.     StarMerge(C, G_sim, β)            // 合并满足条件的簇
14.     if assigned = all proteins: break
15. if assigned ≠ all proteins:
        // 对剩余未分配蛋白，可换顺序或放宽阈值再处理
16. return C

说明：

• 第 4 行：星 $S_v$ 只计算一次；后文合并时会复用。
• 第 5 行：按 $S_v$ 诱导子图的总边权降序处理，信号强的先形成簇。
• 第 8 行：谱划分在 $S_v$ 的诱导子图上做，输出 $S_v^s \subseteq S_v$。
• 第 10 行：论文说“excluding proteins already assigned”，因此新簇只纳入未分配蛋白；已分配蛋白保持原簇，重叠问题交给 StarMerge。
• 第 13 行：每处理完一个物种，做一次合并。

---

1. ComputeStars：计算每个蛋白的星

ComputeStars(G_L, G_sim, β):
1.  for each protein v ∈ G_L:
2.      N(v) ← neighbors of v in G_sim        // 即所有其他物种的蛋白
3.      if N(v) = ∅: S_v ← ∅; continue
4.      w_max ← max_{u ∈ N(v)} w(v,u)
5.      S_v ← { u ∈ N(v) | w(v,u) ≥ β · w_max }
6.      weight_sum(S_v) ← Σ_{x,y ∈ S_v} w(x,y)   // 诱导子图总边权
7.  return {S_v} and {weight_sum(S_v)}

对应论文：

$$S_v = \{ v_j \in N(v) \mid w(v,v_j) \ge \beta \max_j \{w(v,v_j)\} \}$$

• 用相对阈值 $\beta \cdot w_{\max}$，适应不同蛋白的分数尺度；
• $S_v$ 只含跨物种邻居，因为 $G_{\text{sim}}$ 是 $k$ 部图，同物种无边；
• weight_sum(S_v) 用于第 5 行的排序。

---

2. SpectralPartition：谱划分 $S_v \to S_v^s$

这是 2.3 节的核心，包含三部分：构造诱导子图 → 近似 Personalized PageRank → 扫描割。

SpectralPartition(S_v, G_sim, γ, ε):
1.  if |S_v| ≤ 1: return S_v
2.  H ← induced subgraph of G_sim on S_v       // 节点 S_v，边权同 G_sim
3.  p ← ApproxPPR(H, start=v, γ, ε)            // 近似 Personalized PageRank
4.  sort nodes in S_v by p(u) descending       // 按 PR 质量排序
5.  best_set ← ∅; best_cond ← +∞
6.  for j = 1 to |S_v|:
7.      T_j ← first j nodes in sorted order    // 前缀集合
8.      cond ← Conductance(H, T_j)
9.      if cond < best_cond:
10.         best_cond ← cond
11.         best_set ← T_j
12. return best_set                             // 即 S_v^s

对应论文：

• 第 3 行：$p \approx Pr(\gamma,v)$，满足 $$Pr(\gamma,v) = \gamma \chi_v + (1-\gamma) Pr(\gamma,v) W,\quad W=\frac12(I+D^{-1}R)$$
• 第 4–11 行：扫描割 $$S_v^s = \min_j \Phi(T_j^p)$$ 其中 $T_j^p$ 是按 $p$ 排序后的前 $j$ 个节点。

注意： 原文 $T_j^p$ 的归一化写法有歧义；实现上通常直接按 $p(u)$ 降序取前缀，或按 $p(u)/\deg(u)$ 排序。伪代码采用直接按 $p(u)$ 排序的常见做法。

---

3. ApproxPPR：push 近似 Personalized PageRank

ApproxPPR(H, start, γ, ε):
1.  p ← 0 for all nodes in H                  // PR 估计
2.  r ← 0 for all nodes in H                  // 残差
3.  r[start] ← 1
4.  queue ← {start}
5.  while queue ≠ ∅:
6.      u ← pop(queue)
7.      if r[u] ≤ ε · deg_H(u): continue      // 残差足够小，跳过
8.      δ ← r[u]
9.      p[u] ← p[u] + γ · δ                   // 传送部分留在 u 的估计
10.     r[u] ← (1-γ) · δ / 2                  // 懒惰游走：1/2 不动
11.     for each neighbor w of u in H:
12.         r[w] ← r[w] + (1-γ) · δ / 2 · w(u,w)/deg_H(u)
13.         if r[w] > ε · deg_H(w): push w into queue
14. return p

解释：

• 第 9 行：以概率 $\gamma$ 传送回 $v$，在 push 实现中体现为把 $\gamma r(u)$ 累加到 $p(u)$；严格来说传送项应回到 $v$，但 Anderson et al. 的 push 算法把传送质量留在当前节点作为近似，最终 $p$ 仍近似 $Pr(\gamma,v)$。
• 第 10 行：以概率 $1-\gamma$ 继续游走，其中 1/2 不动，所以留在 $u$ 的残差是 $(1-\gamma)\delta/2$。
• 第 12 行：另外 1/2 按边权比例分给邻居。
• 第 7、13 行：残差阈值 $\varepsilon \cdot \deg_H(u)$ 是常见归一化，保证近似误差可控。

复杂度： 只 push 残差大的节点，远离 $v$ 的节点因 $(1-\gamma)^t$ 衰减很快低于阈值，因此实际只探索 $v$ 附近的一小部分图。

---

4. Conductance：计算子集 conductance

Conductance(H, S):
1.  if S = ∅ or S = V(H): return +∞
2.  cut ← Σ_{u ∈ S, w ∉ S} w(u,w)            // 割权 σ(S)
3.  vol_S ← Σ_{u ∈ S} deg_H(u)
4.  vol_total ← Σ_{u ∈ V(H)} deg_H(u)        // 即 2m
5.  denom ← min(vol_S, vol_total - vol_S)
6.  return cut / denom

对应论文：

$$\Phi(S)=\frac{\sigma(S)}{\min[\mathrm{vol}(S),\,2m-\mathrm{vol}(S)]}$$

---

5. StarMerge：合并满足条件的簇

StarMerge(C, G_sim, β):
1.  changed ← true
2.  while changed:
3.      changed ← false
4.      for each pair of clusters (C_a, C_b) in C:
5.          if C_a and C_b have centers v1, v2 in the same PPI network:
6.              cond1 ← ∀ u ∈ C_b \ {v2}: w(v1,u) ≥ β · max_x w(v1,x)
7.              cond2 ← ∀ u ∈ C_a \ {v1}: w(v2,u) ≥ β · max_x w(v2,x)
8.              if cond1 and cond2:
9.                  C_new ← C_a ∪ C_b
10.                 remove C_a, C_b from C; add C_new to C
11.                 changed ← true
12.                 break out of inner loop and restart
13. return C

对应论文步骤 (4)：

$$\forall v_i \in S_{v_2}^s \setminus \{v_2\},\quad w(v_1,v_i) \ge \beta \max_j \{w(v_1,v_j)\}$$

且

$$\forall v_j \in S_{v_1}^s \setminus \{v_1\},\quad w(v_2,v_j) \ge \beta \max_j \{w(v_2,v_j)\}$$

理解：

• 只有当两个簇的中心 $v_1,v_2$ 在同一 PPI 网络中时才考虑合并——这正是为了解决 $k$ 部图部内无边、同物种旁系同源无法同簇的问题。
• 条件检查的是：$C_b$ 中除 $v_2$ 外的每个成员，都与 $v_1$ 有足够高的相似度；反之亦然。这等价于说 $v_1$ 和 $v_2$ 互相“认可”对方的簇成员。
• 合并后簇可包含同一物种的多个蛋白（旁系同源）。
• 用 while changed 反复扫描，因为一次合并可能使新的簇对满足条件。

实现注意：

• 每个簇需要记录其中心蛋白（最初是 $v$，合并后可能多个；可保留一个代表或集合）。
• 合并条件中的 $\max_x w(v_1,x)$ 是 $v_1$ 在功能相似图中的最强边权，可预先计算。
• 如果簇没有明确的“中心”（例如多次合并后），可对簇内每个同物种蛋白分别检查，或只保留初始中心。论文未细化，通常保留初始星中心作为代表。

---

6. 完整主算法（含所有子程序）

Algorithm IsoRankN:
Input: G_1,...,G_k, β, γ, ε, species order π
Output: cluster set C

1.  G_sim ← PairwiseIsoRank(G_1,...,G_k)        // 原版 IsoRank，不求贪心对齐
2.  C ← ∅; assigned ← ∅
3.  for each species G_L in π:
4.      Stars ← ComputeStars(G_L, G_sim, β)
5.      order ← sort {v ∈ G_L \ assigned} by weight_sum(S_v) desc
6.      for v in order:
7.          if v ∈ assigned: continue
8.          S_v^s ← SpectralPartition(S_v, G_sim, γ, ε)
9.          if S_v^s \ {v} = ∅: continue
10.         C_new ← (S_v^s \ assigned) ∪ {v}
11.         C ← C ∪ {C_new}
12.         assigned ← assigned ∪ C_new
13.     C ← StarMerge(C, G_sim, β)
14.     if assigned = V(G_1) ∪ ... ∪ V(G_k): break
15. return C

与论文 2.5 步骤对应：

伪代码行	论文步骤
1	Step (1)：对每对网络跑原版 IsoRank，得到 $R_{ij}$
4	Step (2)：计算每个蛋白的星 $S_v$
5–12	Step (3)：选网络 $G_L$，按 $S_v$ 总权重排序，谱划分得到 $S_v^s$
13	Step (4)：星合并
14	Step (5)：重复直到所有蛋白被分配

---

7. 复杂度与实现注意事项

7.1 复杂度

• 成对 IsoRank：$O(k^2 \cdot |E_{\text{sim}}|)$ 次迭代，主导开销；可并行。
• ComputeStars：对每个蛋白扫其邻居，$O(|V| \cdot \bar{d})$。
• SpectralPartition：push 近似 PPR 只探索 $v$ 附近节点，复杂度与输出集合大小相关，远小于全图。
• StarMerge：最坏 $O(|C|^2)$ 次簇对检查，但实际簇数不大，且合并后簇数减少。

7.2 实现注意

1. 星 $S_v$ 只含跨物种邻居：因为 $G_{\text{sim}}$ 是 $k$ 部图，部内无边。因此初始 $S_v^s$ 不含同物种蛋白；同物种旁系同源只能通过 StarMerge 进入同一簇。
2. 已分配蛋白的处理：第 10 行只把 $S_v^s$ 中未分配的蛋白加入新簇；已分配蛋白保持原簇。若 $S_v^s$ 与已有簇大量重叠，StarMerge 会负责合并。
3. 阈值 $\beta$ 的双重作用：既用于定义星 $S_v$，也用于 StarMerge 的邻居条件。论文统一取 0.01。
4. 物种顺序 $\pi$：影响结果但不大；论文用 120 种排列验证稳健性，并选平均归一化熵最小的顺序（人、鼠、蝇、线虫、酵母）。
5. 终止条件：若所有蛋白已分配则停止；若某物种处理完仍有未分配蛋白，可换下一个物种继续。论文未明确说是否会无限循环，实际实现需保证每个蛋白最多被作为中心处理一次。

---

8. 论文公式与伪代码对应表

论文内容	伪代码位置
$S_v = \{v_j \in N(v) \mid w(v,v_j) \ge \beta \max_j w(v,v_j)\}$	ComputeStars 第 5 行
$Pr(\gamma,v) = \gamma \chi_v + (1-\gamma)Pr(\gamma,v)W$	ApproxPPR 第 9–12 行
$W = \frac12(I+D^{-1}R)$	ApproxPPR 第 10、12 行的 1/2 因子与度归一化
$\Phi(S) = \frac{\sigma(S)}{\min[\mathrm{vol}(S),2m-\mathrm{vol}(S)]}$	Conductance 第 2–6 行
$S_v^s = \min_j \Phi(T_j^p)$	SpectralPartition 第 6–11 行
Star merging 条件	StarMerge 第 6–8 行
算法步骤 (1)–(5)	主算法第 1、4、5–12、13、14 行

---

9. 一句话总结

Star spread 的伪代码核心是：对每个蛋白 $v$，取其高权跨物种邻居构成星 $S_v$，在 $S_v$ 诱导子图上用 push 近似 Personalized PageRank，再按 PR 质量排序做扫描割，取最小 conductance 前缀作为 $S_v^s$；Star merging 则对同一网络中中心不同的两个簇，检查彼此成员是否互相“认可”，满足阈值条件就合并，从而把同物种旁系同源纳入同一跨物种簇。

如果你愿意，下一步我可以把 Table 1–3 的数据读法做成一张“指标—含义—如何比较”的速查表，或者整理全文的符号表。