超图聚类论文阅读1：Kumar算法

《超图中模块化的新度量：有效聚类的理论见解和启示》

《A New Measure of Modularity in Hypergraphs: Theoretical Insights and Implications for Effective Clustering》

COMPLEX NETWORKS 2020, SCI 3区

具体实现源码见HyperNetX库

工作：

针对超图聚类问题推广了模块度最大化框架
引入了一个超图空模型，它与无向图的配置模型完全对应。
推导出一个保留超图节点度序列的邻接矩阵缩减

成果：

使用 Louvain 方法最大化由此产生的模块化函数，已知在图实践中效果很好
在几个真实世界的数据集上展示了我们的方法的有效性

简介

先前工作

注意力限制在 k-均匀超图上，其中所有超边具有相同的固定大小。

提出合适的超图拉普拉斯算子来扩展一般超图的谱聚类框架——隐含了图扩展的思想
模块度最大化是图上聚类的另一种方法，它提供了一个标准来衡量模块化函数中的集群质量

经典方法为louvain算法
团扩展问题：会丢失编码在超边结构中的关键信息。也不会保留超图的节点度——这是模块度最大化方法基于的零模型所必需的
有多种切割超边的方法。根据切割不同侧节点的比例和分配，聚类将发生变化。需要考虑超边权重

本文贡献

在超图上定义了一个空模型（可以保持超图节点度信息），并使用上述定义了一个模块化函数，可以使用 Louvain 方法将其最大化。
提出了一种迭代超边重新加权过程，该过程利用来自超图结构的信息和超边切割的平衡。
在几个真实世界的数据集上凭经验评估了生成的算法，证明了其相对于竞争基线的有效性和效率。

背景知识

超图——关联矩阵、团扩展
模块度

超图模块度

节点的采样概率与其参与的超边的数量（或在加权情况下，总权重）成正比
$P_{i j}^{h y p}=\frac{d(i) \times d(j)}{\sum_{v \in V} d(v)}$

在进行团扩展时，相应图中节点的度数与它在图中的度数不同原始超图

对于每个超边 e，节点度被多算了一个因子 (δ(e) − 1)。因此，我们可以通过将每个 w(e) 缩小一个因子 (δ(e) − 1) 来纠正它。这导致以下更正的邻接矩阵：
$A^{h y p}=H W\left(D_e-I\right)^{-1} H^T$
我们可以使用这种保留节点度数的缩减，将对角线归零，以实现方程式中的空模型。

超图模块度的表达式：
$Q^{h y p}=\frac{1}{2 m} \sum_{i j}\left[A_{i j}^{h y p}-P_{i j}^{h y p}\right] \delta\left(g_i, g_j\right)$
与任何加权图一样，此函数的范围是 [−1, 1]。当超边中没有一对节点属于同一集群时，我们将得到 Qhyp = −1，而当属于同一超边的任何两个节点始终属于同一集群时，我们将得到 Qhyp = 1。 Qhyp = 0，对于任何一对节点 i 和 j，同时包含 i 和 j 的超边数等于包含 i 和 j 的随机连线超边数，由空模型给出。

迭代超边重新加权

问题：最小切割算法会支持尽可能不平衡的切割

思路：我们希望在簇中保留不平衡的超边，并切割更平衡的超边——可以通过增加获得不平衡切割的超边的权重，并减少获得更平衡切割的超边的权重来完成。

超边被一分为二，两边节点数分别为k1、k2：
$t=\left(\frac{1}{k_1}+\frac{1}{k_2}\right) \times \delta(e)$

t值示例

当 $k1=k2=\delta(e)/2$ 时，t取最小值4，推广上式：
$w^{\prime}(e)=\frac{1}{m} \sum_{i=1}^c \frac{1}{k_i+1}[\delta(e)+c]$
——+1 和 +c 项都被添加用于平滑，以解决任何 ki 为零的情况。我们除以 m 来归一化权重