超图(Hypergraph)理论与应用

1、超图理论和应用、由美鹏、动机、共同志消化(Coreference Resolution)是指消化的多种方法也是分割(graph partitions)(威廉莎士比亚，哈姆雷特，书) (威廉莎士比亚，温斯顿)，都是指解构的方法，规则方法利用句法层面的知识进行启发性解构。统计方法基于训练语料库统计概率分布，然后预测。机器学习决策树、朴素贝叶斯、规则学习等。图示方法使用节点表示名词短语，边缘表示名词短语之间的共同关联度。图方法，节点表示名词短语边缘用于表示球体和球体之间的特定连接(牙齿连接应贡献于“公用手指”，如个人、性别、单数等属性)边的权重，以表示此关联对公用手指的贡献程度。简单图，一条边只能连

2、接两个顶点、一个超图和一个。总地消化也有类似的信息。例如“像多个指称性牙齿”、“多个指称数量相同”(即单数或复数)等。顶点表示文章，每个边表示两个顶点(文章)，您可以享受同一作者。假设为什么引入超图(一个茄子示例)，有三篇文章，v1、v2和v3牙齿。作者分别将v 13360 A、b v2:b、c v:c、d v1:A、B v2:A、c v:a、D c v:a、D、简单的图片分割、目标：最小化分割后的两个子图片之间的关联因为可能会有孤立点，与外部的连接本身很小，所以很有可能被独立分开。Normalized-Cut，解决方案：一个Cut为“OK”，比子图形中节点跨越分割边界的边的权重和子图形节点出

3、发的所有边的权重之和小。通俗地说，分割的子图和外部世界的关系主要来自子图内部。Normalized-Cut，np-hard，拉普拉斯矩阵，频谱方法，NP-Hard频谱方法近似解决方案minz(ZTLZ/ZT1=0；意义：L将拉普拉斯矩阵L=B A，超图理论的目标，简单图的表示推广为超图表示，将简单图分割算法扩大到超图分割之上，将超图分割和简单图分割的内部标准(criteria) V推广到顶点集V=v1，v2，v3，v4，每个超边都是V的子集E=E1、E2、E3、E4=V1、V2、V3、V2、V3、V3、V3、V5、V6、V4、超图形的矩阵表示、顶点的度D。A是用右方法表示的A(超图形的邻接矩阵

4、)，A(i，I)是0，A(i，j)是VI和VJ共享的所有超边的权重之和。Dv是对角线阵列，对角线元素是每个顶点的度d(v)。超图分割(cut)，如何将简单图的分割标准放大到超图之上？，牙齿子图形由eG和eG-个顶点切割，因此切割的边缘都是| eG | eG- |。超图形的Normailzed-cut，超图形和简单图形的Normailzed-Cut的格式匹配，超图形的Normailzed-Cut，随机漫步，超图形分割的随机移动说明目的：证明超图分割也满足相同的随机游走特性。随机漫步Google Pagerank算法、Google Pagerank算法、基本模型：矢量I表示所有页面的重要性，I的第

5、一个组件Ii表示第一页的重要性。另外，假设一个页面有指向另一个页面的LJ链接，则指向的每个页面都获得该页面1/lj的重要性。还假定一页的重要性完全来自指向该页的贡献数学表示。其中Pj表示J页。Lj表示j页上的链接数，PjBi表示j页指向Pi。这么多页面徐璐连接，你怎么知道特定页面的重要性呢？Google PageRank算法，Google Pagerank算法，I=HI如何计算I？(I是h的固有向量，对应的特征值1)迭代方法：Ik 1=HIk，Google Pagerank算法，Google Pagerank算法，问题：黑洞连接(不能出入)，Google Pagerank(David assell，Northern Exposure(美国TV电视剧)，bradian Exposure(Northern Exposure)假设在随机漫步的整个过程中，在Pj停留的时间是Tj，Google Pagerank算法，随机漫步到第2页(链接的黑洞)时，Pi (v)表示随机停留在v的概率。超图分割de随机游走解释，超图分割的随机游走解释，在随机游走子图内停留的概率尽可能大，越过分割边界的概率尽可能小。超图真的比简单的图好吗？超图是简单图的推广，所以超