超图 Hypergraph - 版本历史

2024年6月3日 (一) 06:50 13944556914

2024-06-03T06:50:22Z

十三维：修订幂集和子集定义错误

2021-04-27T11:52:42Z

修订幂集和子集定义错误

乐多多：/* 例子 */

2020-05-06T03:37:32Z

例子

乐多多：/* 参阅 */

2020-04-23T06:26:51Z

参阅

乐多多：/* 超图绘制 */

2020-04-23T06:24:08Z

超图绘制

乐多多：/* 定理 */

2020-04-23T06:18:51Z

定理

乐多多：/* 编者推荐 */

2020-04-23T06:08:03Z

编者推荐

乐多多：/* 进一步阅读 */

2020-04-23T04:54:24Z

进一步阅读

2020年4月23日 (四) 04:45 乐多多

2020-04-23T04:45:34Z

乐多多：/* 编者推荐 */

2020-04-23T04:41:13Z

编者推荐

←上一版本		2024年6月3日 (一) 06:50的版本
第10行：		第10行：
	[[File:PAOH representation of the hypergraph.png\|alt=PAOH visualization of a hypergraph\|thumb\|超图的替代表示, 称做 PAOH.<ref name="paoh">{{Cite journal\|last=Valdivia\|first=Paola\|last2=Buono\|first2=Paolo\|last3=Plaisant\|first3=Catherine\|last4=Dufournaud\|first4=Nicole\|last5=Fekete\|first5=Jean-Daniel\|date=2020\|title=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization\|journal=IEEE Transactions on Visualization and Computer Graphics\|publisher=IEEE\|volume=26\|pages=12\|doi=10.1109/TVCG.2019.2933196\|pmid=31398121\|issn=1077-2626\|eissn=1941-0506}}</ref>边是连接顶点的垂直线。顶点在左侧对齐。右侧的图例显示了边缘的名称。]]		[[File:PAOH representation of the hypergraph.png\|alt=PAOH visualization of a hypergraph\|thumb\|超图的替代表示, 称做 PAOH.<ref name="paoh">{{Cite journal\|last=Valdivia\|first=Paola\|last2=Buono\|first2=Paolo\|last3=Plaisant\|first3=Catherine\|last4=Dufournaud\|first4=Nicole\|last5=Fekete\|first5=Jean-Daniel\|date=2020\|title=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization\|journal=IEEE Transactions on Visualization and Computer Graphics\|publisher=IEEE\|volume=26\|pages=12\|doi=10.1109/TVCG.2019.2933196\|pmid=31398121\|issn=1077-2626\|eissn=1941-0506}}</ref>边是连接顶点的垂直线。顶点在左侧对齐。右侧的图例显示了边缘的名称。]]

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

←上一版本		2021年4月27日 (二) 11:52的版本
第13行：		第13行：


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

@@ 第144行： / 第144行： @@
 考虑超图<math>H</math>，它的边为：
-<math>H = \lbrace
+::<math>H = \lbrace
 e_1 = \lbrace a,b \rbrace,
 e_2 = \lbrace b,c \rbrace,
@@ 第155行： / 第155行： @@
 和超图<math>G</math>：
-<math>G = \lbrace
+::<math>G = \lbrace
 f_1 = \lbrace \alpha,\beta \rbrace,
 f_2 = \lbrace \beta,\gamma \rbrace,

@@ 第326行： / 第326行： @@
 * [https://en.wikipedia.org/wiki/Factor_graph Factor graph 因子图]
 * [https://en.wikipedia.org/wiki/Greedoid Greedoid 序阵]
-* [https://en.wikipedia.org/wiki/Incidence_structure Incidence structure 入射结构 ]
+* [https://en.wikipedia.org/wiki/Incidence_structure Incidence structure 关联结构 ]
 * [https://en.wikipedia.org/wiki/Matroid Matroid 拟阵]
 * [https://en.wikipedia.org/wiki/Multigraph Multigraph 多重图]

@@ 第234行： / 第234行： @@
 ==超图绘制==
-[[File:CircuitoDosMallas.png|thumb|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.（这个线路图可以解释为一个超图，其中四个顶点（用白色的矩形和圆盘表示）由三个用树表示的超图连接）]]
+[[File:CircuitoDosMallas.png|thumb|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.（这个线路图可以解释为一个超图，其中四个顶点（用白色的矩形和圆盘表示）由三个用树表示的超图连接）]]
 尽管超图比普通图更难画在纸上，但一些研究者对超图可视化方法已展开研究。

←上一版本		2020年4月23日 (四) 06:18的版本
第231行：		第231行：


−	一致超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。	+	一致超图上有[https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős-Ko-Rado theorem]和[https://en.wikipedia.org/wiki/Line_graph_of_a_hypergraph Kruskal-Katona theorem]两个著名定理。

	==超图绘制==		==超图绘制==

←上一版本		2020年4月23日 (四) 06:08的版本
第362行：		第362行：

	----		----
−	~~本中文词条由~~[[用户:费米子\|费米子]]、[[用户:厚朴\|厚朴]]、[[用户:Liushikang1992\|Liushikang1992]]用户参与编译，[[用户:费米子\|费米子]]审校，[[用户:乐多多\|乐多多]]编辑，欢迎在讨论页面留言。	+	本中文词条由十三维、[[用户:费米子\|费米子]]、[[用户:Pjhhh\|Pjhhh]]、[[用户:厚朴\|厚朴]]、[[用户:Liushikang1992\|Liushikang1992]]用户参与编译，[[用户:费米子\|费米子]]审校，[[用户:乐多多\|乐多多]]编辑，欢迎在讨论页面留言。

@@ 第319行： / 第319行： @@
 超图已被广泛用于机器学习中，常作为一种数据结构或一种正则化属性分类器 classifier regularization。 <ref>{{citation| last1 = Zhou | first1 = Dengyong| last2 = Huang | first2 = Jiayuan | last3=Scholkopf | first3=Bernhard| issue = 2| journal = Advances in Neural Information Processing Systems| pages = 1601–1608| title = Learning with hypergraphs: clustering, classification, and embedding| year = 2006}}</ref> 这些应用包括推荐系统  recommender system (社团作为超边)<ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei|issue = 1| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model| year = 2013|url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T }}</ref>、图像检索 image retrieval(相关性作为超边) <ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> 、和生物信息学(生物、化学分子间相互作用作为超边)<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref>。比较典型的超图机器学习方法包括：超图谱聚类法 spectral clustering（用拉普拉斯超图 hypergraph Laplacian 扩展光谱图理论 spectral graph theory）<ref>{{citation|last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha|first3=Zheng-Jun|last4=Shen|first4=Jialie|last5=Li|first5=Xuelong|last6=Wu|first6=Xindong|issue = 1| journal = IEEE Transactions on Image Processing| volume=22 | title = Visual-textual joint relevance learning for tag-based social image search| year = 2013| pages=363–376|url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676| pmid=22692911 | bibcode=2013ITIP...22..363Y }}</ref> 和超图半监督学习 semi-supervised learning（通过引入超图结构来对结果进行限定）。<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref>对于大尺寸的超图，可以使用Apache Spark构建的分布式框架<ref name=hyperx />。
-==进一步阅读==
+==参阅==
 * [https://en.wikipedia.org/wiki/Simplicial_complex Simplicial complex 简单复合体]

@@ 第1行： / 第1行： @@
 [[File:Hypergraph-wikipedia.png|300px|thumb|right|超图示例, 其中
-<math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math> and
+<math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math> 和
 <math>E = \{e_1,e_2,e_3,e_4\} = </math>
 <math>\{\{v_1, v_2, v_3\},</math>

←上一版本		2020年4月23日 (四) 04:41的版本
第362行：		第362行：

	----		----
−	~~本中文词条由，~~[[用户:费米子\|费米子]]、[[用户:厚朴\|厚朴]]、[[用户:Liushikang1992\|Liushikang1992]]用户参与编译，[[用户:费米子\|费米子]]审校，[[用户:乐多多\|乐多多]]编辑，欢迎在讨论页面留言。	+	本中文词条由[[用户:费米子\|费米子]]、[[用户:厚朴\|厚朴]]、[[用户:Liushikang1992\|Liushikang1992]]用户参与编译，[[用户:费米子\|费米子]]审校，[[用户:乐多多\|乐多多]]编辑，欢迎在讨论页面留言。