高效更新时序网络中的最大(Δ,γ)-团及学生班级友谊网络发现

# 高效更新时序网络中的最大(Δ, γ)-团及学生班级友谊网络发现 ## 1. 时序网络相关概念与问题定义 ### 1.1 基本定义 - **时序网络**：时序网络定义为一个三元组 \(G(V, E, T)\)，其中 \(V(G)\) 是网络的顶点集，\(E(G) \subseteq \binom{V(G)}{2} \times T\) 是边集，\(T = [T_1, T_2]\) 是观察网络的时间区间。通常用 \(|V(G)| = n\) 和 \(|E(G)| = m\) 表示顶点数和边数。 - **(Δ, γ)-团**：对于给定的时间周期 \(\Delta\) 和正整数 \(\gamma\)，时序网络 \(G\) 的一个 \((\Delta, \gamma)\)-团是一个顶点集和时间区间对 \((X, [t_a, t_b])\)，其中 \(X \subseteq V(G)\)，\(|X| \geq 2\)，且 \([t_a, t_b] \subseteq T\)。对于任意 \(v_i, v_j \in X\) 和 \(t \in [t_a, \max(t_b - \Delta, t_a)]\)，必须存在 \(\gamma\) 条或更多的边 \((v_i, v_j, t_{ij}) \in E(G)\)，且 \(f(v_iv_j) \geq \gamma\)，其中 \(t_{ij} \in [t, \min(t + \Delta, t_b)]\)。当 \(\gamma = 1\) 时，\((\Delta, \gamma)\)-团即为 \(\Delta\)-团。 - **最大(Δ, γ)-团**：时序网络 \(G(V, E, T)\) 的一个 \((\Delta, \gamma)\)-团 \((X, [t_a, t_b])\) 是最大的，需满足以下三个条件均不成立： - 存在 \(v \in V(G) \setminus X\)，使得 \((X \cup \{v\}, [t_a, t_b])\) 是一个 \((\Delta, \gamma)\)-团。 - \((X, [t_a - dt, t_b])\) 是一个 \((\Delta, \gamma)\)-团（仅当 \(t_a - 1 \geq T_1\) 时适用）。 - \((X, [t_a, t_b + dt])\) 是一个 \((\Delta, \gamma)\)-团（仅当 \(t_b + 1 \leq T_2\) 时适用）。 ### 1.2 最大(Δ, γ)-团更新问题 给定一个时序网络 \(G(V, E, T)\)，已知其截至时间戳 \(T_1\) 的边集和 \((\Delta, \gamma)\)-团，以及从时间戳 \(T_1\) 到 \(T_2\) 的边 \(E_{(T_1,T_2]}\)，最大 \((\Delta, \gamma)\)-团更新问题就是更新截至 \(T_1\) 的现有最大 \((\Delta, \gamma)\)-团，以获得截至 \(T_2\) 的最大 \((\Delta, \gamma)\)-团。 ## 2. 时序网络最大(Δ, γ)-团更新的解决方案 ### 2.1 “边在团上”方法概述 提出的方法称为“边在团上”（Edge on Clique，EOC）方法，其输入包括截至时间戳 \(T_1\) 的最大 \((\Delta, \gamma)\)-团集合 \(C_{T_1}\)、可能要扩展的团集合 \(C_{T_1}^{ex}\)、在 \(T_1 - \Delta\) 到 \(T_2\) 期间到达的边 \(E_{[T_1 - \Delta,T_2]}\)、\(T_1\)、\(T_2\)、\(\Delta\) 和 \(\gamma\)，输出为截至 \(T_2\) 的最大 \((\Delta, \gamma)\)-团集合 \(C_{T_2}\) 以及在下一次更新中要扩展的团集合（即使用 \(T_3 > T_2\) 时的边 \(E_{(T_2,T_3]}\)）。 ### 2.2 算法步骤 算法 1 展示了该方法的具体实现，主要分为三个部分： ```plaintext Algorithm 1: Maximal (Δ, γ)-clique enumeration using ‘Edge on Clique’ (EOC) Approach Data: The Clique Set till Time T1; i.e.; CT1, CT1ex, The link set E[T1−Δ,T2] of G(V, E, T ), Δ, γ, T1, and T2. Result: Initialized Clique Set for the links ET2\T1. 1 CI ←−CT1ex ; 2 CT2\T1 ←−∅, CT2\T1ex ←−∅, Cim ←−CI; 3 while CI ̸= ∅ do 4 take and remove (Z, [tx, ty]) from CI; 5 r flag = Extend Right TS((Z, [tx, ty]), E[T1−Δ,T2]); 6 if r flag == TRUE then 7 add (Z, [tx, ty]) to CT2\T1; 8 if ty ≥ T2 then 9 add (Z, [tx, ty]) to CT2\T1ex; 10 CI ←−Execute Algorithm 1 of [2] on the links E[T1−Δ,T2]; 11 Cim ←−Cim ∪ CI; 12 while CI ̸= ∅ do 13 take and remove (Z, [tx, ty]) from CI; 14 if ty − tx == Δ then 15 Prepare the static graph G for the duration [tx, ty]; 16 Associate NG(Z) to (Z, [tx, ty]); 17 v flag = Expand Vertex Set( (Z, [tx, ty] ```