1.2　国内外研究现状

本节将对国内外相关文献进行梳理，围绕超图理论、超图的应用、基于超图的超网络的理论研究、基于超图的超网络的应用研究四个方面进行综述。

1.2.1　超图理论

Berge C（1973）撰写了第一部关于超图的专著Graph and Hypergraphs之后，超图的理论和应用研究陆续展开，并产生了许多经典的结论，有关超图理论及其应用的研究越来越受到重视；Berge C（1973）首次系统地建立了无向超图理论，并应用拟阵方法研究了超图理论在运筹学中的应用；黄汝激（1987）首先把超图理论发展成为有向超图理论，引入了超通路、分解超图、k-超树、超回路、超边分解、单向超通路和单向超树等概念；随后许小满等（1994）对有向超图、超图的超回路、着色和t-设计等进行了研究；C.贝尔热（2002）研究了超图的Helly性质、Ramsey数、横贯与匹配、分数横贯、着色等；Kim J（2016）研究了均齐超图中的规则子图；王建方（2006）在《超图的理论基础》一书中，将超网络的超边和关系数据库中的属性进行了一一对应，并且给出了无圈超图和信息超图的概念，促进了超图理论在数据挖掘理论中的应用研究。超图理论的研究还包括k-超树、超回路、超通路、超边分解、对偶超图、超图的秩、均匀超图、线性超图、简单超图、子超图、超路径、超图的直径、超树、超图的切割集及切割集矩阵、超图的谱研究、超图的关联矩阵、超图的邻接矩阵等。

1.2.2　超图的应用

近年来，超图理论被广泛应用于各个领域中。国内外学者在集成电路布图、图形处理、生物、数据挖掘、化学等领域对超图的应用进行研究。其中，超图在大规模集成电路布图设计、划分和综合问题中被广泛应用（Karypis G，1999）；在图形处理领域，有学者将超图与图像处理相结合，建立了图像领域的超图模型（Bretto A et al，2002）；在生物领域，有学者对细胞动态交流系统建立了超图模型（Sarkar S、Sivarajan K N，1998）；超图基于图论和集合论，已在数据挖掘研究中得到了运用（Ozdal M、Aykanat C，2004）；在化学领域，超图的拓扑指数被用来识别化合物的分子结构（Konstantinova E V、Skorobogatov V A，2001）；超图模型能够利用图的逻辑结构、有效组织，以及传递数据集的结构、关系和含义，实现关联规则、聚类和分类等知识的获取和表示（王建方，2006）。另外，超图还有其他方面的应用。这些应用可以清晰地表明超图的重要性。

1.2.3　基于超图的超网络的理论研究

超网络可以用超图的语言和符号来表示。超图为社会学家、管理学家、化学家、数学家、计算机学家、物理学家和生物学家提供了刻画超网络的工具，且其相关结论和完备的研究方法已被成功地推广到超网络的研究中。基于超图的超网络研究，虽仍处于模型的构建和描述阶段，但受到了各领域研究者的广泛关注，国内外很多研究者在开展这方面的工作。国内外学者从基于超图的超网络的拓扑特性、结构指标及模型等角度进行研究。Estrada E和Rodríguez-Velázquez J A（2006）从理论上详细推导出了复杂超网络的子图中心度和聚集系数的定义及公式，并对三个真实复杂系统的子图中心度和聚集系数在一般复杂网络和超网络之间的不同做了比较，研究的结论可作为进一步研究超网络的无标度特性、小世界特性、社团结构及可靠性等性质的基础；Zlatić V等（2009）基于三个超图模型的统计特性，定义和分析了超网络的几个拓扑量：超边度的分布、节点的相似性、超网络的聚集性、节点之间的距离及超网络的社团结构，并用这些拓扑量对真实超网络进行了仿真分析；Neubauer N和Obermayer K（2009）利用超图理论给出了一种在标签网络中寻找最大连通子图的方法；李阳（2013）提出了用基于熵的超网络社团检测算法来检测重叠社团的方法；武澎等（2014）针对当前GN算法的一些不足，从超图理论的视角出发，构建了一种新的复杂网络社团区划算法；Pretolani D（2000）研究了从有向超图中建立超网络；Guo J L等（2016）给出了基于加权超图的超网络中节点的超强度的定义；Kapoor K等（2013）给出了基于加权超图的超网络中节点的加权度中心性的定义。

Zhang Z K和Liu C（2010）建立了一种基于用户背景知识和对象、标签双重优先连接机制的超图增长模型，在此超图增长模型上模拟、解析超度、聚集系数及路径长度等特性；裴伟东等（2010）研究了基于一类三角形结构的动态网络结构的演化模型，通过平均场方法理论解析网络特性，发现该类演化模型具有无标度特性和小世界特性；Wang J W等（2010）给出了一种基于增长和超度优先连接机制的超网络动态演化模型：每个时间步t，网络中新增m>1个节点，将这些新节点与网络中已经存在的一个节点结合生成一条新的超边，该模型适用于社会标记网络，且网络模型简单。胡枫等（2013）构建了一种类似BA无标度网络的超网络模型，此模型的演化机制与Wang J W等（2010）提出的模型相对应：每个时间步t，网络中新增一个节点，并与网络中已有的m>1个节点结合生成一条新的超边，对比BA无标度网络生成的两大机制（节点增长和度优先），超网络中采取了超边增长和超度择优连接机制，导致超网络的无标度特性；Yang G Y和Liu J G（2014）构建了一种局域世界超网络演化模型，该模型的生长机理与胡枫等的模型相同；郭进利和祝昕昀（2014）基于现实网络中新增的若干节点更倾向于和网络中已有的多个旧节点结合生成超边的增长机制，提出了一种超网络和复杂网络中统一演化模型：每个时间步t，网络中新增m1>1个节点，将m1>1个新节点与网络中已有m2>1个节点构成一条超边，共形成m>1条超边；Pretolani D（2000）构建了超网络演化模型，用于探讨用户标签的使用特性和规律。

1.2.4　基于超图的超网络的应用研究

超网络可以看作一类特殊的复杂网络，在大数据时代，是令人关注的网络科学前沿领域之一。基于超图的超网络的应用研究涉及多个方面和领域。基于加权超图的超网络适合描述每条超边中节点间存在多次合作或竞争关系的情况，应用也比较广泛。

1.合作网络

Xiao Q（2013）以科研论文合作关系为对象构建了基于超图的科研合作超网络，提出了在科研合作组织中识别核心研究者是进行人才流失绩效评价和危机管理的重要问题，并利用带有可调参数的加权综合评价指标对研究者进行评价。数据实例分析验证了该方法测度科研合作超网络中节点重要性的合理性和有效性。

胡枫等（2013）用基于超图的超网络来表示科研合作关系，其中，作者用节点表示。一篇论文中可能包含多个作者，作者之间合作一篇论文就表示为超网络中的一条超边，每条超边中的多个节点即合作同一篇论文的作者之间采用完全连接的方式，来表示多个作者之间的相互合作。不同的论文可能包含相同的作者，即通过共同的节点使不同的超边之间邻接。因此，许多篇科研论文根据相同的作者就会形成一个作者合作论文关系的超网络。

马涛和郭进利（2018）针对某消费品公司的矩阵制企业项目小组结构进行了研究，以职能部门的人员为节点，以项目小组为超边，首先构建了基于超图的矩阵制企业项目小组超网络拓扑结构，然后建立了节点具有竞争力的矩阵制企业项目小组的非均齐超网络形成机制；马涛和郭进利（2018）以公司（企业、集团、厂）、大学（学院、学校）和研究所（研究院）为节点，以专利为超边，构建了基于加权超图的产学研合作申请专利超网络，并利用来自国家知识产权局发布的2015年上海市ICT产业产学研合作申请专利的数据进行实证分析。

2.知识表述及信息传播

基于超图的超网络的应用领域还包括知识表述及信息传播等方面。王众托（2011）对基于超图的超网络在知识表述上的应用进行了举例；王众托和王志平（2008）对超图在超网络的应用方面进行了归纳，对超网络的研究情况进行了总结；Liu J G等（2014）认为网络的统计特性对知识扩散会产生影响，提出了两个基于不同的演化机制知识生成的动态演化模型：一个是HDPH模型，另一个是KSPH模型；Yang G Y等（2015）对合作超网络中的知识扩散进行了描述；索琪和郭进利（2017）模拟基于超图的超网络中舆情传播过程，探讨舆情的传播时间和波及范围，进而揭示超网络舆情的传播规律；马宁和刘怡君（2012）对基于超网络的舆论领袖识别进行了应用研究；杨迎辉等（2016）针对网络化作战信息流转问题，给出了作战信息流转动态超图模型构建的一般流程及步骤。

3.超链路预测

超链路预测是指在超网络结构上对未知的超链接及未来超链接的预测。田儒雅等（2014）采用网络结构相似性方法对舆情传播进行了预测；刘怡君等（2014）基于超网络对社会舆论进行了建模；另一些研究者（Lü L Y et al，2012；刘建国等，2009）采用超网络的超边相似度概念，将超网络理论用在社交网络的信息推荐和超链路预测方面。

4.在线社会网络用户行为

肖玉芝和赵海兴（2014）提出利用超图的数学理论建立用户行为的超网络模型，同时挖掘出用户间的潜在朋友关系；通过用户、用户活动、用户兴趣三维度的映射关系，更真实地刻画了在线社交网络用户行为；用某论坛的真实数据验证了超网络模型能够快速定位用户并刻画出用户兴趣爱好的差异性；Suo Q等（2015）用超网络方法来分析社交网络中用户的评分。

5.社会标签

Ghoshal G等（2009）提出了一个随机超图模型来表示社会化标注系统的三元结构，在每条超边中包括三个不同的节点，分别为标签、用户、资源。一条超边由一个标签、一个用户和一个资源组成，用该模型再现了社会标注系统的很多属性，理论推导和仿真分析了随机超网络中的标签、用户和资源三个节点的度分布，得到了一些重要的结论。

潘旭伟和傅青苗（2015）构建了以标签为节点、以标注活动为超边的社会化标注行为超网络，定义了超度、超度分布、余平均超度和超度条件概率等刻画社会化标注超网络性质的指标，结合Delicious网站数据进行了实证分析；Pan X W等（2016）以标注活动为超边，以用户、资源和标签为节点，构建了社会标签超网络，对所构建的超网络进行了定量测度，并分析了基于Delicious网站的用户标注数据。

Kai W S和Chong H L（2017）认为现有的多标签学习主要集中在利用标签相关性来促进学习过程，提出了一个两阶段的多标签的超网络（TSMLHN）来挖掘标签的相关性，利用它们来解决在多标签学习中的不平衡问题。多标签数据集的实证研究表明TSMLHN实现竞争力的表现更好。

6.生物网络

Pearcy N等（2016）对代谢超网络的复杂性和稳健性进行研究；Segovia-Juarez J L等（2007）用超网络来辨别DNA切块；Zhang B T和Kim J K（2006）用DNA超网络对信息进行存储和获取；还有学者构建了蛋白质超网络（Ramadan E et al，2004）（以蛋白质为节点，以蛋白质复合物为超边）及新陈代谢超网络（Krishnamurthy L et al，2003）（以分子实体为节点，以代谢反应为超边）。

7.其他网络

其他学者关于超网络的应用研究也涉及多个方面和领域，包括李勇建等（2015）运用超图理论建立非常规突发事件链的超网络模型，并构造其投影网络模型；Bonacich P等（2004）构建了社会超网络（以行动者为节点，以过程为超边）；Guo J L和Suo Q（2015）提出了基于品牌效应和竞争力的非均齐超网络模型；Guo J L等（2016）提出了一个超网络特例，即玻色-爱因斯坦凝聚，并对凝聚度进行了讨论；Pearcy N等（2016）刻画了超网络模型的复杂性和稳健性；Kim J K和Zhang B T（2007）用进化超网络对模式进行了分类，建立了进化变阶的超网络模型；Mao C和Yokomori T（2006）、Maeshiro T等（2009）分别构建了信息存储和获取、描述乐器演奏相似细节的超网络模型。