用于表征有向超图的四集超图模型（Four-set Hypergraphlets for Characterization of Directed Hypergraphs）

《IEEE Transactions on Knowledge and Data Engineering》：Four-set Hypergraphlets for Characterization of Directed Hypergraphs

本研究提出91种有向超图基（DHGs），并开发精确与近似计数算法，揭示现实系统中基于DHGs的局部结构模式，显著提升超图聚类和超弧预测性能，其中近似算法CODA-A速度提升达36倍。

　　

摘要：

有向超图是一种由节点和超弧组成的高级数据结构，能够自然地模拟具有方向性的群体交互（例如，分子的化学反应）。尽管已经对现实世界中（有向）图的局部结构进行了大量研究，但有向超图的局部结构仍较少被探索。在这项工作中，我们专注于与有向超图的局部结构相关的测量、发现和应用，这些共同有助于系统地理解通过有向群体交互相互连接的各类现实世界系统。我们的第一个贡献是定义了91种有向超图子结构（DHGs），这些子结构将构成两个相邻超弧的四个节点集之间的有向连接和重叠关系进行了分类。第二个贡献是开发了用于计算每种DHGs出现次数的精确算法和近似算法。最后一个贡献是利用DHGs的出现频率来描述11个现实世界中的有向超图及其内部的各个超弧，从而揭示出基于领域的清晰局部结构模式。实验表明，与基线描述方法相比，基于DHGs的描述方法在超图聚类和超弧预测方面的性能分别提高了12%和33%。此外，我们提出的近似算法CODA-A在性能上比具有类似描述质量的竞争算法快了36倍。