11

超图是一种图泛化，其中边可以连接许多顶点。最近我看到很多关于超图（分割、聚类等）的出版物。所以我的问题是：

  • 是否有任何超图（可能还有实现）在现实世界中的应用，或者这只是不打算被工程师使用的学术研究？
  • 是否有可以与超图一起使用的常见图算法的类似物，例如 max-flow 或 Dijkstra？

我对正态图有直觉。例如，图可以用来表示传输网络或贝叶斯网络的繁忙度规则。但是我对超图没有这种直觉，它们对我来说绝对是违反直觉的。

4

4 回答 4

7

超图可表示为二分图，二分图可用于构造超图。这实际上只是说您可以将某种形式的参与者之间的交互表示为顶点或（超）边。

一旦我们认识到这种等价性，我们就可以得出结论，当您可能使用二分图时，超图是可用的，并且图算法的类似物更直接地适用于二分图上的算法。

于 2013-02-08T09:35:56.190 回答
4

使用超图可以很好地进行图像聚类：http: //vision.ucsd.edu/bpc/

幻灯片在这里：http: //vision.ucsd.edu/~sagarwal/bpc_cvpr05_slides.pdf

尽管该算法没有成为主流，但它是超间隙中链接的概念及其含义的一个优雅例证。我认为超图在数据挖掘中可能非常有用。

于 2014-10-29T15:13:51.483 回答
3

零件组装的数学模型基于超图。这在计算机辅助制造 (CAM) 系统中用于确定可能的和最佳的（在某种意义上）装配顺序。

于 2013-02-08T09:15:07.830 回答
0

在此处输入图像描述 图 1 - Battiston 等人的高阶交互表示。人 [1]

超图

在考虑组交互时，超图是一种有用的数据表示。考虑一个作者网络，其中一组作者 - 即 , Author-A,Author-B和Author-C在单一出版物中共同创作的人。使用传统的图边表示此信息，其中每条边连接两个作者以显示共同作者关系带来两个问题。首先，它引入了误导性信息，我们无法区分三位作者的单一出版物的情况；其中三位作者合着了三篇出版物（即Publication-1由Author-Aand合着Author-B；and合着；and合着）。第二个Publication-2Author-BAuthor-CPublication-3Author-AAuthor-C使用传统图表示表示超图的含义是图存储中的数据膨胀。例如，在我们之前的共同作者网络中，我们需要添加N*(N-1) 条边来表示单个出版物的N个作者之间的共同作者身份。通过学习如何将数据编码到这些结构中，以及如何操纵它们以提取有意义的数据，我们或许能够获得对数据的洞察，而这在以前是不可能的。

在此处输入图像描述 图 2 - 表示组 {0,1,2}、{1,2,3} 和 {0,3} 的示例超图及其来自 [2] 的二分表示

超图算法

网页排名

Pagerank 是一种常用的图分析算法。它用于查找网络中顶点的相对重要性。在广泛的应用中，pagerank 起着非常重要的作用，例如在recommendation systems、link prediction、search engines等中。我们可以从两种不同的方式来考虑 pagerank 在超图中的含义。首先，顶点在网络中的重要性基于它们的组参与。例如，在社交网络环境中，我们可以根据组成员身份来衡量用户的重要性，例如，拥有少数用户的组的管理员可能对整个网络有更大的影响。第二，超边的重要性基于它链接到的顶点。例如，从共同作者网络中，我们可以根据作者在网络中的相对重要性找到最有影响力的出版物。

参考

  1. Battiston, F.、Cencetti, G.、Iacopini, I.、Latora, V.、Lucas, M.、Patania, A.、Young, J.-G. 和 Petri, G. (2020)。超越成对交互的网络：结构和动力学。物理报告。https://doi.org/10.1016/j.physrep.2020.05.004
  2. 朱利安顺。2020.实用的并行超图算法。在第 25 届 ACM SIGPLAN 并行编程原理与实践研讨会论文集 (PPoPP '20) 上。计算机协会，纽约，纽约，美国，232–249。DOI：https ://doi.org/10.1145/3332466.3374527
  3. Abdullah Al Raqibul Islam，使用 Apache Spark 实现超图 PageRank 的实验代码。，（2021 年），GitHub 存储库，https://github.com/biqar/hypergraph-study
于 2021-02-18T00:58:07.417 回答