基于超图的超网络研究综述

doi:10.12005/orms.2021.0066

摘要/Abstract

摘要： 超网络是一般网络的一类自然推广。超网络的研究将会有助于理解“复杂系统之所以复杂”这一极其重要的问题。现实世界中,很多复杂的系统都可以用超网络描述。超网络分为基于网络的超网络与基于超图的超网络。本文主要介绍的是基于超图的超网络,首先对超图理论进行描述,然后对基于超图的超网络进行分析,接着提出了基于超图的超网络和多层超网络的转换及实例并提出了基于超图的超网络演化模型。本文最后对超网络今后的研究方向进行了探讨,其中,超网络的指标构建、动力学研究、链路预测、应用等方面还有待于深入研究。

关键词: 超图, 超网络, 拓扑结构, 演化模型

Abstract: Hypernetwork is a natural generalization of normal network. The study of hypernetwork will help us to understand the very important issue, i.e. the complex system has “complexity”. In the real world, the hypernetwork can be used to describe many complex systems. Hypernetwork is divided into network-based supernetwork and hypergraph-based hypernetwork. In this paper, we focus on the hypergraph-based hypernetwork. Firstly, the hypergraph theory is described, and we analyze the hypergraph-based hypernetwork. Then the transformation and examples of hypergraph-based hypernetwork and multilayer supernetwork are presented. The hypernetwork evolving model based on hypergraph is also proposed. At the end of this paper, the application and the future research direction of the hypernetwork are discussed. Among them, the index construction, dynamics and link prediction of the hypernetwork need to be further studied.

Key words: hypergraph, hypernetwork, topological structure, evolving model

中图分类号:

N949

马涛, 索琪. 基于超图的超网络研究综述[J]. 运筹与管理, 2021, 30(2): 232-239.

MA Tao, SUO Qi. Review of Hypernetwork Based on Hypergraph[J]. Operations Research and Management Science, 2021, 30(2): 232-239.

参考文献

[1] Nagurney A, Dong J. Supernetworks: decision-making for the information age[J]. E Elgar, 2002, 76(2): 93-95.
[2] 方锦清.多层超网络探索中的若干问题与思考[J].科技导报,2017,35(14):34-41.
[3] 方锦清.从单一网络向《网络的网络》的转变进程——略论多层次超网络模型的探索与挑战[J].复杂系统与复杂性科学,2016,13(1):40-47.
[4] Berge C. Graphs and hypergraphs[M]. New York: Elsevier, 1973.
[5] Berge C. Hypergraphs: combinatorics of finite sets[M]. New York: Elsevier, 1984.
[6] 贝热尔·C.超图——有限集的组合学[M].卜月华,张克民译.南京:东南大学出版社,2002.
[7] Kim J. Regular subgraphs of uniform hypergraphs[J]. Journal of Combinatorial Theory, 2016, 119: 214-236.
[8] Tran T H, Scaparra M P, O'Hanley J R. A hypergraph multi-exchange heuristic for the single-source capacitated facility location problem[J]. European Journal of Operational Research, 2017, 263(1): 173-187.
[9] Purkait P, Chin T J, Sadri A. Clustering with hypergraphs: the case for large hyperedges[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2017, 39(9): 1697-1711.
[10] 王建方.信息超图理论[M].北京:科学出版社,2008.
[11] Feng K, Li W C W. Spectra of hypergraphs and applications[J]. Journal of Number Theory, 1996, 60(1): 1-22.
[12] Lim L H. Singular values and eigenvalues of tensors: a variational approach[J]. Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005, 1: 129-132.
[13] Bollobás B, Janson S, Scott A. Packing random graphs and hypergraphs[J]. Random Structures & Algorithms, 2017, 51(1): 3-13.
[14] Estrada E, Rodríguez-Velázquez J A. Subgraph centrality and clustering in complex hyper-networks[J]. Physica A, 2006, 364: 581-594.
[15] Ghoshal G, Zlatic＇ V, Caldarelli G, Newman M E. Random hypergraphs and their applications[J]. Physical Review E, 2009, 79(6): 066118.
[16] 索琪,郭进利.基于超图的超网络:结构及演化机制[J].系统工程理论与实践,2017,37(3):720-734.
[17] 史定华.网络度分布理论[M].北京:高等教育出版社,2011.
[18] Pan X W, He S L, Zhu X Y, Fu Q M. How users employ various popular tags to annotate resources in social tagging: an empirical study[J]. Journal of the Association for Information Science & Technology, 2016, 67(5): 1121-1137.
[19] 郭进利.非均齐超网络中标度律的涌现——富者愈富导致幂律分布吗[J].物理学报,2014,63(20):208901.
[20] 索琪,郭进利,王福红.电视节目竞争关系的超网络分析[J].复杂系统与复杂性科学,2016,13(3):33-39.
[21] 王建方.超图的理论基础[M].北京:高等教育出版社,2006.
[22] Freeman L C. Centrality in social networks: conceptual clarification[J]. Social Networks, 1978, 1(3): 215-239.
[23] Lü L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63.
[24] 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,59(13):1175-1197.
[25] 李阳.一种基于熵的超网络重叠社团检测算法[J].科学技术与工程,2013,13(7):1856-1859.
[26] 马涛,郭进利,王福红.企业非正式组织社团划分的超网络模型研究[J].技术经济与管理研究,2017,5:3-7.
[27] Cheng Q, Liu Z, Huang J C, Cheng G Q. Community detection in hypernetwork via density-ordered tree partition[J]. Applied Mathematics & Computation, 2016, 276: 384-393.
[28] 田儒雅,孙巍,吴蕾,张学福.基于超网络的图书情报领域知识合作特征分析[J].情报理论与实践,2016,39(10):25-30.
[29] 马宁,刘怡君.基于超网络的舆论领袖识别应用研究[J].中国科学院院刊,2012,27(5):586-594.
[30] Guo J L, Suo Q. Brand effect versus competitiveness in hypernetworks[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2015, 25(2): 023102.
[31] Guo J L, Suo Q, Shen A Z, Forrest J. The evolution of hyperedge cardinalities and Bose-Einstein condensation in hypernetworks[J]. Scientific Reports, 2016, 6: 33651.
[32] Xiao Q. Node importance measure for scientific research collaboration from hypernetwork perspective[J]. Tehnicˇki Vjesnik, 2016, 23(2): 397-404.
[33] 马涛,郭进利.基于超图的矩阵制企业项目小组超网络形成机制研究[J].计算机应用研究,2018,35(1):79-82.
[34] 马涛,郭进利.基于加权超图的产学研合作申请专利超网络——以上海ICT产业为例[J].系统工程,2018,36(1):140-152.
[35] 王众托.关于超网络的一点思考[J].上海理工大学学报,2011,33(3):229-237.
[36] 王众托,王志平.超网络初探[J].管理学报,2008,5(1):1-8.
[37] Liu J G, Yang G Y, Hu Z L. A knowledge generation model via the hypernetwork[J]. Plos One, 2014, 9(3): e89746.
[38] Ma T, Guo J L. Study on information transmission model of enterprise informal organizations based on the hypernetwork[J]. Chinese Journal of Physics, 2018, 56(5): 2424-2438.
[39] 索琪,郭进利.超网络中的舆情传播模型及仿真研究[J].计算机应用研究,2017,34(9):2629-2632.
[40] 方哲,游宏梁,薛非,耿伟波,高强.专家知识协作加权超网络模型及其超链路预测研究[J].科研管理,2017,38(4):251-258.
[41] 潘旭伟,傅青苗.基于超网络的社会化标注行为[J].系统工程,2015(3):78-83.
[42] Pan X W, He S L, Zhu X Y, Fu Q M. How users employ various popular tags to annotate resources in social tagging: an empirical study[J]. Journal of the Association for Information Science & Technology, 2016, 67(5): 1121-1137.
[43] Kai W S, Chong H L. Addressing class-imbalance in multi-label learning via two-stage multi-label hypernetwork[J]. Neurocomputing, 2017, 266: 375-389.
[44] 李勇建,王治莹,乔晓娇.基于超图的非常规突发事件链网络模型研究[J].管理评论,2015,27(12):192-201.
[45] 刘胜久,李天瑞,洪西进,王红军,珠杰.超网络模型构建及特性分析[J].计算机科学与探索,2017,11(2):194-211.