广义中位数图与多媒体社交网络专家发现技术

### 广义中位数图与多媒体社交网络专家发现技术 #### 广义中位数图计算 在图计算领域，广义中位数图的计算是一个重要的研究方向。在计算广义中位数图时，边及其属性的更新是关键步骤。 在每一步下降过程中，通过最小化 $s_e$ 来计算图 $\overline{G}$ 的边及其属性。去除 $s_e$ 中的常数项后，最小化 $s_e$ 可重写为： \[ \arg \min_{A\in\{0,1\}^{\overline{n}\times\overline{n}},\Phi\in F_{\overline{n}\times\overline{n}}^e} s_e(A, \varphi) = \arg \min_{A\in\{0,1\}^{\overline{n}\times\overline{n}},\Phi\in F_{\overline{n}\times\overline{n}}^e} \sum_{i=1}^{\overline{n}}\sum_{j=1}^{\overline{n}} f_{i,j}(a_{i,j}, \varphi_{i,j}) \] 其中函数 $f_{i,j} : \{0, 1\} \times F_e \to R^+$ 定义为： \[ f_{i,j}(a_{i,j}, \varphi_{i,j}) = a_{i,j} \sum_{p=1}^{|G|} \delta_{\pi_p^i \pi_p^j} a_p^{\pi_p^i, \pi_p^j} c_{efs}(\varphi_{i,j}, \varphi_p^{\pi_p^i, \pi_p^j}) + c_{er}a_{i,j} \sum_{p=1}^{|G|} (1 - \delta_{\pi_p^i \pi_p^j} a_p^{\pi_p^i, \pi_p^j}) + c_{ei}(1 - a_{i,j}) \sum_{p=1}^{|G|} \delta_{\pi_p^i \pi_p^j} a_p^{\pi_p^i, \pi_p^j} \] \[ = a_{i,j} \sum_{p=1}^{|G|} \delta_{\pi_p^i \pi_p^j} a_p^{\pi_p^i, \pi_p^j} c_{efs}(\varphi_{i,j}, \varphi_p^{\pi_p^i, \pi_p^j}) + c_{er}a_{i,j} (|G| - |S_{i,j}|) + c_{ei}(1 - a_{i,j})|S_{i,j}| \] 这里 $S_{i,j} = \{(\pi_p^i, \pi_p^j) | \pi_p^i \in [n_p] \land \pi_p^j \in [n_p] \land a_p^{\pi_p^i, \pi_p^j} = 1, p = 1, \ldots, |G|\}$ 是通过映射 $\pi_p$ 替代 $(i, j)$ 的边的集合。 由于 $f_{i,j}$ 各项为正且相互独立，上述式子等价于： \[ \forall(i, j) \in [\overline{n}] \times [\overline{n}], i \neq j, (\overline{a}_{i,j}, \overline{\varphi}_{i,j}) \leftarrow \arg \min_{a_{i,j}\in\{0,1\},\varphi_{i,j}\in F_e} f_{i,j}(a_{i,j}, \varphi_{i,j}) \] 因为 $a_{i,j}$ 只能取两个值，当 $a_{i,j} = 0$ 时，$f_{i,j}(0, \varphi_{i,j}) = c_{ei}|S_{i,j}|$；当 $a_{i,j} = 1$ 时，$f_{i,j}(1, \varphi_{i,j})$ 在 $\varphi_{i,j}^* \in \arg \min_{\varphi_{i,j}\in F_e} \sum_{p=1}^{|G|} \delta_{\pi_p^i \pi_p^j} a_p^{\pi_p^i, \pi_p^j} c_{efs}(\varphi_{i,j}, \varphi_p^{\pi_p^i, \pi_p^j})$ 时取得最小值。 最终，$f_{i,j}$ 在 $\overline{\varphi}_{i,j} = \varphi_{i,j}^*$ 时最小化，且 \[ \overline{a}_{i,j} = \begin{cases} 1, & \text{if } f_{i,j}(1, \overline{\varphi}_{ij}) < c_{ei}|S_{i,j}| \\ 0, & \text{else} \end{cases} \] 当 $F_v \subset N$ 且 $c_{efs}(x, y) = c_{es}(1 - \delta_{x,y})$ 时，$f_{i,j}$ 变为： \[ f_{i,j}(a_{i,j}, \varphi_{i,j}) = a_{i,j} \left(