超图 Hypergraph

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

在数学中, 超图 hypergraph是一种广义上的图，是有限集合中最一般的离散结构，在信息科学、生命科学等领域有着广泛的应用。它的一条边 edge可以连接任意数量的顶点 vertices。相对而言，在普通图中，一条边只能连接两个顶点。形式上，超图 [math]\displaystyle{ H }[/math] 是一个有序二元组 [math]\displaystyle{ H = (X,E) }[/math] 其中[math]\displaystyle{ X }[/math] 是一个以节点 nodes或顶点为元素的非空集合，即顶点集，而 [math]\displaystyle{ E }[/math] 是[math]\displaystyle{ X }[/math] 的一组非空子集簇，[math]\displaystyle{ E }[/math]的元素被称为边或超边 hyperedges。 没有相同边的超图称为单超图。


因此，若[math]\displaystyle{ \mathcal{P}(X) }[/math]是 [math]\displaystyle{ E }[/math]的幂集 power set，则[math]\displaystyle{ X }[/math]是 [math]\displaystyle{ \mathcal{P}(X) \setminus\{\emptyset\} }[/math] 的一个子集。在[math]\displaystyle{ H }[/math]中，顶点集的大小被称为超图的阶数 order of the hypergraph，边集的大小被称为超图的大小 size of the hypergraph。


普通图的边是节点的二元子集，超边则是节点的任意集合，所以可以包含任意数量的节点。但我们总先需要研究具有相同基数超边的超图，即一个k-一致超图 k-uniform hypergraph（所有超边的大小都为 k，也译作k-均匀超图）。因此一个2-一致超图就是普通图，一个3-一致超图就是无序三元组 unordered triples 的集合，依此类推。超图也被称为从泛集 universal set 中抽取的一个集系统 set system 或集族 family of sets。


超图可以看做是关联结构 incidence structure。特别的，每个超图都有一个与超图相对应的二分 "关联图 incidence graph"或 "列维图 Levi graph"，反之，大多数（但不是全部）二分图 bipartite graph都可以看作是超图的关联图。


超图还有许多其它名称。在计算几何学 family of sets中，超图有时可以被称为范围空间 range space，将超图的边称为范围 ranges.[1]


在合作博弈论 cooperative game中，超图被称为简单博弈 simple games（投票博弈 voting games）；这个概念被应用于解决社会选择理论 social choice theory 中的问题。在一些文献中，超边被称为超连接或连接器。[2]


特殊类型的超图包括：上文简单讨论过的k-一致超图；散簇 clutter，也即没有一条边作是另一条边的子集；以及抽象单纯复形 abstract simplicial complexes，这里面包含每条边的所有子集。


超图是一个以超图同态 homomorphism 为态射 morphism 的范畴。


术语

定义

超图有不同的类型，如：

  • 空超图 Empty hypergraph：没有边的超图；
  • 非简单（或多重）超图 Non-simple (or multiple) hypergraph ：允许有环 loops（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点；
  • 简单超图 Simple hypergraph ：不包含循环和重复边的超图；
  • [math]\displaystyle{ k }[/math]-一致超图 [math]\displaystyle{ k }[/math]-uniform hypergraph：每条超边都正好包含 k 个顶点的超图；
  • [math]\displaystyle{ d }[/math]-正则超图 [math]\displaystyle{ d }[/math]-regular hypergraph：每个顶点的度数都是 𝑑 的超图；
  • 无环超图 Acyclic hypergraph：不包含任何环的超图。


因为超图中的连接可以有任意基数，所以有好几种关于子图的概念，分别是子超图 subhypergraphs、部分超图 partial hypergraphs和分段超图 section hypergraphs。


假定 [math]\displaystyle{ H=(X,E) }[/math] 是一个超图，包含顶点集：[math]\displaystyle{ X = \lbrace x_i | i \in I_v \rbrace, }[/math]和 “边集”： [math]\displaystyle{ E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace, }[/math] 其中 [math]\displaystyle{ I_v }[/math] 和 [math]\displaystyle{ I_e }[/math] 分别是顶点和边集的索引集 index set


  • 子超图 subhypergraph 是去掉某些顶点的超图。在形式上，若 [math]\displaystyle{ A \subseteq X }[/math] 是顶点子集，则子超图 [math]\displaystyle{ H_A }[/math] 被定义为：[math]\displaystyle{ H_A=\left(A, \lbrace e \cap A | e \in E \land e \cap A \neq \emptyset \rbrace \right). }[/math]。一个子超图的扩展 extension是一个超图，其中每个属于 [math]\displaystyle{ H }[/math] 的超边都部分包含在子超图的 [math]\displaystyle{ H_A }[/math]中，并且完全包含在扩展的 [math]\displaystyle{ Ex(H_A) }[/math] 中。即在形式上:[math]\displaystyle{ Ex(H_A) = (A \cup A', E' ) }[/math]和 [math]\displaystyle{ A' = \bigcup_{e \in E} e \setminus A }[/math] 和[math]\displaystyle{ E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace }[/math]。


  • 部分超图 partial hypergraph是去掉一些边的超图。给定一个边索引集的子集 [math]\displaystyle{ J \subset I_e }[/math] ，由 [math]\displaystyle{ J }[/math] 生成的部分超图就是[math]\displaystyle{ \left(X, \lbrace e_i | i\in J \rbrace \right). }[/math]


  • 而给定一个子集 [math]\displaystyle{ A\subseteq X }[/math]，则分段超图 section hypergraphs是部分超图:[math]\displaystyle{ H \times A = \left(A, \lbrace e_i | i\in I_e \land e_i \subseteq A \rbrace \right). }[/math]


[math]\displaystyle{ H }[/math] 的对偶 [math]\displaystyle{ H^* }[/math] 则是一个顶点和边互换的超图，因此顶点由 [math]\displaystyle{ \lbrace e_i \rbrace }[/math] 给出，边由 [math]\displaystyle{ \lbrace X_m \rbrace }[/math] 给出，其中:[math]\displaystyle{ X_m = \lbrace e_i | x_m \in e_i \rbrace. }[/math]。当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到[math]\displaystyle{ H }[/math] 的对偶：[math]\displaystyle{ \left(H^*\right)^* = H. }[/math]


对于连通的超图 G 和具有相同顶点连通的超图 H，如果 H 的每个超边都由 G 中一个子图导出 induce，则 G 是一个主图 host graph； 对于不连通的超图 H，如果 G 和 H 的连通部分之间存在一个双射，使得 G 的每个连通部分 G 都是对应的 H 的主图，则 G 是一个主图。


一个超图是二分 bipartite的，当且仅当它的顶点能被分成两类U 和 V ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。


2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。


二分图模型

设[math]\displaystyle{ G=(V,E) }[/math]是一个无向图，如果顶点V可分割为两个互不相交的子集[math]\displaystyle{ {(group1, group2)} }[/math]，并且图中的每条边[math]\displaystyle{ {（i，j）} }[/math]所关联的两个顶点[math]\displaystyle{ {i} }[/math]和[math]\displaystyle{ {j} }[/math]分别属于这两个不同的部分[math]\displaystyle{ {(i \in group1,j \in group2)} }[/math]，则称图[math]\displaystyle{ {G} }[/math]为一个二分图。

一个超图 [math]\displaystyle{ {H} }[/math]可以用二分图[math]\displaystyle{ {BG} }[/math]表示，其构成如下: 集合[math]\displaystyle{ X }[/math]和[math]\displaystyle{ E }[/math]是[math]\displaystyle{ BG }[/math]的分割，而且 ("x1", "e1") 与边连通当且仅当顶点"x1"包含在[math]\displaystyle{ H }[/math]的边" e1"中。 反之，任何具有固定的部分 part且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为关联图。


无环性

与只有圈 cycle和森林 forest的普通无向图相比，对于超图的特殊情形，那些坍缩为普通图的无环性超图天然地有多种不等价的无环性 acyclicity 定义。


由Claude Berge 给出了超图无环性的首个定义: [3] 如果它的关联图(上面定义的二分图)是无环的，则称这个超图是 Berge 无环的 Berge-acyclic。 这个定义是非常严格的：例如，假设一个超图有一些顶点[math]\displaystyle{ v \neq v' }[/math]和一些超边[math]\displaystyle{ f \neq f' }[/math] ，例如 [math]\displaystyle{ v, v' \in f }[/math] 和[math]\displaystyle{ v, v' \in f' }[/math]，那么它就是 Berge成环的 Berge-cyclic。 通过对关联图的探讨，Berge成环性 berge-cyclity可以在线性时间 linear time内得到有效验证 。


此处，我们可以定义一个减弱的超图无环性的概念[4]，后来被称为 [math]\displaystyle{ {\alpha} }[/math]-无环性 [math]\displaystyle{ {\alpha} }[/math] acyclicity。 这个无环性的概念等价于超图是同形的 conformal (原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 chordal graph ; 它也等价于通过 GYO 算法 Graham-Yu-Ozsoyoglu Algorithm （也称为格雷厄姆算法 Graham's algorithm) 得到具有可约性的空图[5][6]。GYO 算法是一个合流 confluence（抽象重写 abstract rewriting）迭代过程，该算法中使用耳朵 ear的广义定义去除超边 (图论中的耳朵就定义为一条路径，其中除了端点外的点的度数均为 2（端点可以重合），而且删去后不破坏图的连通性)。众所周知， 在数据库理论 database theory 的领域中，如果一个数据库模式 database schema的底层超图是[math]\displaystyle{ {\alpha} }[/math]无环的，那么它就具有某些理想的性质。 [7] 除此之外,[math]\displaystyle{ {\alpha} }[/math]无环性也与一阶逻辑 first-order logic 保护的片段 guarded fragment 的表达能力有关。


我们可以在线性时间 linear time内检验超图是否是-无环的。 [8]


注意到[math]\displaystyle{ {\alpha} }[/math]-无环性似乎与直觉不相符，即[math]\displaystyle{ {\alpha} }[/math]-成环超图添加超边可能使其成为[math]\displaystyle{ {\alpha} }[/math]-无环的（例如，添加一条包含超图所有顶点的超边总能其成为[math]\displaystyle{ {\alpha} }[/math]-无环的）。 为了克服这个缺点，Ronald Fagin[9] 定义了更强的 [math]\displaystyle{ {\beta} }[/math]-无环性 [math]\displaystyle{ {\beta} }[/math]-acylicity 和 [math]\displaystyle{ {\gamma} }[/math]无环性 [math]\displaystyle{ {\gamma} }[/math]-acylicity 概念。 应当指出：[math]\displaystyle{ {\gamma} }[/math]无环超图是推出其所有子超图都是[math]\displaystyle{ {\alpha} }[/math]无环的必要条件，这与 Graham 的早期定义[6] 等价。 [math]\displaystyle{ {\gamma} }[/math]无环性的概念是一个更加严苛的条件，它等价于数据库模式的几个理想性质，并且与Bachman 图 Bachman diagrams有关. [math]\displaystyle{ {\beta} }[/math]-无环性 和 [math]\displaystyle{ {\gamma} }[/math]无环性 都可以在多项式时间 polynomial time(PTIME)内完成检测。


无环性的四个概念具有可比性: berge-无环性意味着 [math]\displaystyle{ {\gamma} }[/math]- 无环性， [math]\displaystyle{ {\gamma} }[/math]- 无环性又意味着 [math]\displaystyle{ {\beta} }[/math]- 无环性， [math]\displaystyle{ {\beta} }[/math]- 无环性又可以推出 [math]\displaystyle{ {\alpha} }[/math] 无环性。 然而，反之均不成立。[9]


同构和相等

超图同态 homomorphism是指从一个超图的顶点集到另一个超图的顶点集的映射，如此使得每条边映射到另一条边。


如果一个超图 [math]\displaystyle{ H=(X,E) }[/math]与另外一个超图[math]\displaystyle{ G=(Y,F) }[/math]同构 isomorphic ，则存在一个双射：[math]\displaystyle{ H \simeq G }[/math] :[math]\displaystyle{ \phi:X \to Y }[/math]

和 关于[math]\displaystyle{ I }[/math]的置换 permutation 使得： :[math]\displaystyle{ \phi(e_i) = f_{\pi(i)} }[/math]

那么这个双射被称为图的同构 isomorphism，记作：[math]\displaystyle{ H \simeq G }[/math]但且仅当[math]\displaystyle{ H^* \simeq G^* }[/math]。


当超图的边被明确标记时，就有了“强同构 strong isomorphism ”这个新的概念。 当前面提及的置换是唯一的，则称[math]\displaystyle{ H }[/math] 强同构于 [math]\displaystyle{ G }[/math] 。 记作[math]\displaystyle{ H \cong G }[/math]。 注意，所有强同构图都是同构的，但反过来就不成立。


当超图的顶点被明确标记时，就有了“等价 equivalence”和“相等 equality”的概念。 我们称[math]\displaystyle{ H }[/math]和[math]\displaystyle{ G }[/math]等价，记作：[math]\displaystyle{ H\equiv G }[/math] 。如果同构[math]\displaystyle{ \phi }[/math] 满足:[math]\displaystyle{ \phi(x_n) = y_n }[/math]而且:[math]\displaystyle{ \phi(e_i) = f_{\pi(i)} }[/math]

记作: [math]\displaystyle{ H\equiv G }[/math] 当且仅当 [math]\displaystyle{ H^* \cong G^* }[/math]


超图自同构 automorphism是从顶点集到自身的同构，也就是顶点的重标号。 超图 [math]\displaystyle{ {H } }[/math](= ([math]\displaystyle{ X }[/math], [math]\displaystyle{ E }[/math]))的自同构集合是超图的群 group，称为超图的自同构群 automorphism group，并写成 [math]\displaystyle{ {Aut(H)} }[/math]。


例子

H、G的图

考虑超图[math]\displaystyle{ H }[/math]，它的边为：

[math]\displaystyle{ H = \lbrace e_1 = \lbrace a,b \rbrace, e_2 = \lbrace b,c \rbrace, e_3 = \lbrace c,d \rbrace, e_4 = \lbrace d,a \rbrace, e_5 = \lbrace b,d \rbrace, e_6 = \lbrace a,c \rbrace \rbrace }[/math]

和超图[math]\displaystyle{ G }[/math]：

[math]\displaystyle{ G = \lbrace f_1 = \lbrace \alpha,\beta \rbrace, f_2 = \lbrace \beta,\gamma \rbrace, f_3 = \lbrace \gamma,\delta \rbrace, f_4 = \lbrace \delta,\alpha \rbrace, f_5 = \lbrace \alpha,\gamma \rbrace, f_6 = \lbrace \beta,\delta \rbrace \rbrace }[/math]


很明显 [math]\displaystyle{ H }[/math] 和 [math]\displaystyle{ G }[/math] 同构（有[math]\displaystyle{ \phi(a)=\alpha }[/math]等），但是它们不是强同构，因为比如在超图[math]\displaystyle{ H }[/math]中，[math]\displaystyle{ a }[/math] 顶点连接1，4，6三条边，所以：[math]\displaystyle{ e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace }[/math]。在图[math]\displaystyle{ G }[/math]，不存在连接边1，4，6的顶点：[math]\displaystyle{ f_1 \cap f_4 \cap f_6 = \varnothing }[/math]


在这个例子，[math]\displaystyle{ H }[/math] 和 [math]\displaystyle{ G }[/math]是等价的， [math]\displaystyle{ H\equiv G }[/math]，而且两者的对偶图是强同构的：[math]\displaystyle{ H^*\cong G^* }[/math]。


对称超图

超图[math]\displaystyle{ H }[/math]的[math]\displaystyle{ r(H) }[/math]表示该超图中任何一条边的最大基数。如果所有边具有相同的基数k，则称该超图为一致的或k-一致的，或称之为k-超图。普通图只是一个2-一致的超图。


顶点[math]\displaystyle{ v }[/math]的度[math]\displaystyle{ d(v) }[/math]表示包含该顶点的边的数量。如果每个顶点的度都为k，则超图H是k-正则的。


一致超图的对偶是正则的，反之亦然。


如果存在一个形如[math]\displaystyle{ \phi(x)=y }[/math]的自同构，则超图H的两个顶点x和y对称 symmetric。如果存在一个自同构使得[math]\displaystyle{ \phi(e_i)=e_j }[/math]，则称两个边[math]\displaystyle{ e_i }[/math]和[math]\displaystyle{ e_j }[/math]对称。


如果超图的所有顶点都是对称的，则称其为顶点可传递的 vertex-transitive (或顶点对称的 vertex-symmetric)。类似地，如果超图的所有边都是对称的，则该超图是边传递的 edge-transitive。 如果一个超图既是边对称的又是顶点对称的，则该超图是简单传递的 simply transitive。


由于超图的对偶性，边传递性的研究与顶点传递性的研究是相似的。


横截面

超图[math]\displaystyle{ H = (X, E) }[/math]的横截集 transversal（或命中集 hitting set）是一个[math]\displaystyle{ T\subseteq X }[/math]集合，该集合与每条边都有非空的交集。如果[math]\displaystyle{ T }[/math]的真子集不是横截集，则称[math]\displaystyle{ T }[/math]为极小截集。[math]\displaystyle{ H }[/math]的横截超图是超图[math]\displaystyle{ （X, F） }[/math]，其边集[math]\displaystyle{ F }[/math]包含[math]\displaystyle{ H }[/math]的所有最小横截集。


计算横截面超图在组合优化 Combinatorial Optimization、博弈论 Game Theory和计算机科学 Computer Science的一些领域（例如机器学习 Machine Learning、数据库索引 Indexing of Databases、可满足性问题 the Satisfiability Problem、数据挖掘 Data Mining和计算机程序优化 Program Optimization）都有应用。


关联矩阵

分别设 [math]\displaystyle{ V = \{v_1, v_2, ~\ldots, ~ v_n\} }[/math]， [math]\displaystyle{ E = \{e_1, e_2, ~ \ldots ~ e_m\} }[/math]。 每一个超图都有一个 [math]\displaystyle{ n \times m }[/math] 关联矩阵 incidence matrix[math]\displaystyle{ A = (a_{ij}) }[/math]，其为：

[math]\displaystyle{ a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right. }[/math]。


其关联矩阵的转置 transpose [math]\displaystyle{ A^t }[/math]定义了 [math]\displaystyle{ H^* = (V^*,\ E^*) }[/math]称为[math]\displaystyle{ H }[/math]的对偶，其中[math]\displaystyle{ V^* }[/math]是一个m元集合， [math]\displaystyle{ E^* }[/math]是[math]\displaystyle{ V^* }[/math]的一个n元子集。


对于[math]\displaystyle{ v^*_j \in V^* }[/math] 和 [math]\displaystyle{ e^*_i \in E^*, ~ v^*_j \in e^*_i }[/math] 当且仅当 [math]\displaystyle{ a_{ij} = 1 }[/math]。


超图着色

经典超图着色是将集合[math]\displaystyle{ \{1,2,3,...\lambda\} }[/math]中的其中一种颜色赋予给超图的每个顶点，使每个超边至少包含两个不同颜色的顶点。换句话说，不能存在基数至少为2的单色超边。从此意义上出发，它是广义图着色的直接推广。在所有着色行为中，使用到最小的不同颜色数称为超图的色数。


存在着使用多达[math]\displaystyle{ k }[/math]种颜色着色的超图称为k- 可着色图。2-可着色超图就是二分图。


经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。


划分

由E. Dauber[10]所提出的一个定理表明，对于边传递超图 [math]\displaystyle{ H=(X,E) }[/math]存在一个划分 partition：[math]\displaystyle{ (X_1, X_2,\cdots,X_K) }[/math]对于顶点集 [math]\displaystyle{ X }[/math]使得由[math]\displaystyle{ X_k }[/math]生成的子超图[math]\displaystyle{ H_{X_k} }[/math]在[math]\displaystyle{ 1\le k \le K }[/math]时是可传递的，并且使得[math]\displaystyle{ \sum_{k=1}^K r\left(H_{X_k} \right) = r(H) }[/math]，其中[math]\displaystyle{ r(H) }[/math]是 [math]\displaystyle{ H }[/math]的秩。


作为推论，不是点传递的边传递超图则是2可着色的。


图划分(特别是超图划分)在集成电路设计 IC design [11] 和并行计算 parallel computing [12][13][14]中有很多应用。此外，在机器学习任务中，高效、可扩展的超图划分算法对于处理大规模超图也很重要。[15]

定理

许多涉及图的定理和概念也适用于超图，典型的例子有拉姆齐定理 Ramsey's theorem和超图的线图 Line graph of a hypergraph。一些研究图的对称性的方法也被扩展到超图。


一致超图上有Erdős-Ko-Rado theorem和Kruskal-Katona theorem两个著名定理。

超图绘制

This circuit diagram can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.（这个线路图可以解释为一个超图，其中四个顶点（用白色的矩形和圆盘表示）由三个用树表示的超图连接）

尽管超图比普通图更难画在纸上，但一些研究者对超图可视化方法已展开研究。


其中超图的一种可视化表示法，类似于标准的图的画法 graph drawing：用平面内的曲线来描绘图的边，将超图的顶点画成点状、圆盘或盒子，超边则被描绘成以顶点为叶子的树。[16][17] 。 如果顶点表示为点，超边也可以被描绘成连接点集的平滑曲线，或显示为封闭点集的简单闭合曲线。[18][19][20]

文件:Venn's four ellipse construction.svg
An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses).（一个4阶维恩图，可以被解释为一个15个顶点（15个着色区域）和4个超边（4个椭圆）的超图的细分图）


超图的另一种表示法被称做 PAOH[21]，如上图所示，边是连接顶点的垂线，顶点是左对齐的。右边的图例显示了边的名称。它是为动态超图而设计的，但也可以用于简单的超图。

超图语法 Hypergraph grammars

Main article: Hypergraph grammar

By augmenting a class of hypergraphs with replacement rules, graph grammars can be generalised to allow hyperedges.

通过扩充一组替换规则于超图，图语法 graph grammar可以被推广到超边上。

Generalizations

One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of term algebra; edges correspond to terms and vertices correspond to constants or variables.

For such a hypergraph, set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is [math]\displaystyle{ V= \{a,b\} }[/math] and whose edges are [math]\displaystyle{ e_1=\{a,b\} }[/math] and [math]\displaystyle{ e_2=\{a,e_1\} }[/math]. Then, although [math]\displaystyle{ b\in e_1 }[/math] and [math]\displaystyle{ e_1\in e_2 }[/math], it is not true that [math]\displaystyle{ b\in e_2 }[/math]. However, the transitive closure of set membership for such hypergraphs does induce a partial order, and "flattens" the hypergraph into a partially ordered set.

Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges [math]\displaystyle{ e_1 }[/math] and [math]\displaystyle{ e_2 }[/math], and zero vertices, so that [math]\displaystyle{ e_1 = \{e_2\} }[/math] and [math]\displaystyle{ e_2 = \{e_1\} }[/math]. As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph.

The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply

[math]\displaystyle{ \left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right]. }[/math]


超图概念的延伸

超图的相关概念可以进行进一步的延伸，如超图中的一些边可以指向另一些边。这种延伸有两种变体。在第一种变体中，超图的边不仅包含一组节点，而且还可以包含这组节点的子集、子集的子集等等。本质上，超图的每条边只是树结构或有向无环图的一个内部节点，而节点就是叶子。从这个意义上来说，超图就是具有共享节点的树的集合（即内部节点或叶子可能出现在不同的树结构中），反过来说，每个树的集合又可以理解为一个超图。因为树结构在计算机科学和许多数学分支中被广泛使用，所以超图的出现也是自然而然的。比如这种延伸是作为项代数的模型而自然产生的：边对应项，节点对应常量或变量。


对于上述的超图，节点集提供了一种排序。但是该排序既不是偏序也不是预序，因为它是不可传递的。与这一延伸方式的Levi图相对应的图是有向无环图。例如，一个超图的节点集为[math]\displaystyle{ V= \{a,b\} }[/math]，边为[math]\displaystyle{ e_1=\{a,b\} }[/math]和[math]\displaystyle{ e_2=\{a,e_1\} }[/math]。那么，虽然[math]\displaystyle{ b\in e_1 }[/math]且[math]\displaystyle{ e_1\in e_2 }[/math]，但[math]\displaystyle{ b\in e_2 }[/math]却不是真的。然而，这类超图节点集的封闭传递确实诱导了偏序，并将超图“展平”为一个偏序集。


第二种变体中，超图中的边可以指向其他边，同时不用考虑必须形成有向无环图的要求。这允许超图具有成环的边，而不需要有任何节点。例如，考虑由两条边e1和e2组成的，节点个数为零的广义超图，使得[math]\displaystyle{ e_1 = \{e_2\} }[/math]且[math]\displaystyle{ e_2 = \{e_1\} }[/math]。因为这个循环是无限递归的，所以边的集合违反了基础公理。具体来说，对于这样的超图，不存在节点集的封闭传递。虽然这样的结构乍看起来可能很奇怪，但只要注意到它的Levi图的等价延伸不再是二分图，而是一般的有向图，就可以很容易地去理解。

根据定义，这种超图的广义关联矩阵是一个方阵，其秩等于节点和边的总数。因此，对于上面的示例，关联矩阵为: [math]\displaystyle{ \left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] }[/math]。

Hypergraph learning

Hypergraphs have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics).[22] The applications include recommender system (communities as hyperedges),[23] image retrieval (correlations as hyperedges),[24] and bioinformatics (biochemical interactions as hyperedges).[25] Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian,[26] and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results.[27] For large scale hypergraphs, a distributed framework[15] built using Apache Spark is also available.


超图与机器学习

超图已被广泛用于机器学习中，常作为一种数据结构或一种正则化属性分类器 classifier regularization。 [28] 这些应用包括推荐系统 recommender system (社团作为超边)[29]、图像检索 image retrieval(相关性作为超边) [30] 、和生物信息学(生物、化学分子间相互作用作为超边)[31]。比较典型的超图机器学习方法包括：超图谱聚类法 spectral clustering（用拉普拉斯超图 hypergraph Laplacian 扩展光谱图理论 spectral graph theory）[32] 和超图半监督学习 semi-supervised learning（通过引入超图结构来对结果进行限定）。[33]对于大尺寸的超图，可以使用Apache Spark构建的分布式框架[15]。

See also

模板:Commons category

Notes

  1. ↑ Haussler, David; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry, 2 (2): 127–151, doi:10.1007/BF02187876, MR 0884223.
  2. ↑ Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25.
  3. ↑ Claude Berge,Graphs and Hypergraphs
  4. ↑ C. Beeri, Ronald Fagin|R. Fagin, D. Maier, Mihalis Yannakakis|M. Yannakakis, On the Desirability of Acyclic Database Schemes
  5. ↑ C. T. Yu and M. Z. Özsoyoğlu. An algorithm for tree-query membership of a distributed query. In Proc. IEEE COMPSAC, pages 306-312, 1979
  6. ↑ 6.0 6.1 M. H. Graham. On the universal relation. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979
  7. ↑ Serge Abiteboul, Richard B. Hull, Victor Vianu|V. Vianu, Foundations of Databases
  8. ↑ Robert Tarjan|R. E. Tarjan, Mihalis Yannakakis|M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. on Computing, 13(3):566-579, 1984.
  9. ↑ 9.0 9.1 Ronald Fagin, Degrees of Acyclicity for Hypergraphs and Relational Database Schemes
  10. ↑ E. Dauber, in Graph theory, ed. F. Harary, Addison Wesley, (1969) p. 172.
  11. ↑ Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (March 1999), "Multilevel hypergraph partitioning: applications in VLSI domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 (1): 69–79, CiteSeerX 10.1.1.553.2367, doi:10.1109/92.748202.{{citation}}: CS1 maint: multiple names: authors list (link)
  12. ↑ Hendrickson, B., Kolda, T.G. (2000), "Graph partitioning models for parallel computing", Parallel Computing (Submitted manuscript), 26 (12): 1519–1545, doi:10.1016/S0167-8191(00)00048-X.{{citation}}: CS1 maint: multiple names: authors list (link)
  13. ↑ Catalyurek, U.V.; Aykanat, C. (1995). A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers. Proc. International Conference on Hi Performance Computing (HiPC'95).
  14. ↑ Catalyurek, U.V.; Aykanat, C. (1999), "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems, 10 (7): 673–693, CiteSeerX 10.1.1.67.2498, doi:10.1109/71.780863.
  15. ↑ 15.0 15.1 15.2 Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015), "Scalable Hypergraph Learning and Processing", Proceedings of the IEEE International Conference on Data Mining
  16. ↑ Sander, G. (2003), "Layout of directed hypergraphs with orthogonal hyperedges", Proc. 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, Springer-Verlag, pp. 381–386 {{citation}}: Text "contribution-url" ignored (help).
  17. ↑ Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Orthogonal hypergraph drawing for improved visibility" (PDF), Journal of Graph Algorithms and Applications, 10 (2): 141–157, doi:10.7155/jgaa.00122.
  18. ↑ Mäkinen, Erkki (1990), "How to draw a hypergraph", International Journal of Computer Mathematics, 34 (3): 177–185, doi:10.1080/00207169008803875.
  19. ↑ Bertault, François; Eades, Peter (2001), "Drawing hypergraphs in the subset standard", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 45–76, doi:10.1007/3-540-44541-2_15.
  20. ↑ Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Hypergraph Drawing by Force-Directed Placement", 28th International Conference on Database and Expert Systems Applications (DEXA 2017), Lecture Notes in Computer Science, vol. 10439, Springer International Publishing, pp. 387–394, doi:10.1007/_31.
  21. ↑ 引用错误：无效<ref>标签；未给name属性为paoh的引用提供文字
  22. ↑ Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Learning with hypergraphs: clustering, classification, and embedding", Advances in Neural Information Processing Systems (2): 1601–1608
  23. ↑ Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (2013), "Using rich social media information for music recommendation via hypergraph model", ACM Transactions on Multimedia Computing, Communications, and Applications (1), Bibcode:2011smma.book..213T
  24. ↑ Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hypergraph with sampling for image retrieval", Pattern Recognition, 44 (10–11): 2255–2262, doi:10.1016/j.patcog.2010.07.014
  25. ↑ Patro, Rob; Kingsoford, Carl (2013), "Predicting protein interactions via parsimonious network history inference", Bioinformatics, 29 (10–11): 237–246, doi:10.1093/bioinformatics/btt224, PMC 3694678, PMID 23812989
  26. ↑ Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Visual-textual joint relevance learning for tag-based social image search", IEEE Transactions on Image Processing, 22 (1): 363–376, Bibcode:2013ITIP...22..363Y, doi:10.1109/tip.2012.2202676, PMID 22692911
  27. ↑ Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009), "A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge", Bioinformatics, 25 (21): 2831–2838, doi:10.1093/bioinformatics/btp467, PMID 19648139
  28. ↑ Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Learning with hypergraphs: clustering, classification, and embedding", Advances in Neural Information Processing Systems (2): 1601–1608
  29. ↑ Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; He, Xiaofei (2013), "Using rich social media information for music recommendation via hypergraph model", ACM Transactions on Multimedia Computing, Communications, and Applications (1), Bibcode:2011smma.book..213T
  30. ↑ Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hypergraph with sampling for image retrieval", Pattern Recognition, 44 (10–11): 2255–2262, doi:10.1016/j.patcog.2010.07.014
  31. ↑ Patro, Rob; Kingsoford, Carl (2013), "Predicting protein interactions via parsimonious network history inference", Bioinformatics, 29 (10–11): 237–246, doi:10.1093/bioinformatics/btt224, PMC 3694678, PMID 23812989
  32. ↑ Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Visual-textual joint relevance learning for tag-based social image search", IEEE Transactions on Image Processing, 22 (1): 363–376, Bibcode:2013ITIP...22..363Y, doi:10.1109/tip.2012.2202676, PMID 22692911
  33. ↑ Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009), "A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge", Bioinformatics, 25 (21): 2831–2838, doi:10.1093/bioinformatics/btp467, PMID 19648139

References

  • Claude Berge, "Hypergraphs: Combinatorics of finite sets". North-Holland, 1989.
  • Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag
  • Hazewinkel, Michiel, ed. (2001) [1994], "Hypergraph", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN
  • Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.
  • Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.
  • Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.
  • This article incorporates material from hypergraph on PlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

编者推荐

超图的第一本专著，作者是近代图论之父法国数学家Claude Berge，将图里的普通边拓展为超边，小小的一步拓展却引发了一个大的领域。

取自“https://wiki.swarma.org/index.php?title=超图_Hypergraph&oldid=5063”