带权超网络的度量方法及其性质

刘胜久 李天瑞 杨宗霖 珠杰

摘 要：超网络是较通常意义上的复杂网络更为复杂的网络，该网络的每一条超边能连接任意多个节点的特性使其比复杂网络能更好地描述真实世界中的复杂系统。针对现有超网络研究中对超网络度量方法的缺陷与不足，提出了一种超网络度量方法——超网络维数（HD），即为所有超边包含的节点权重之和与对应超边权重乘积和的对数值和节点权重之和与超边权重之和乘积对数值的比值的两倍。超网络维数可以应用于节点权重与超边权重为正实数、负实数、纯虚数，乃至复数等多种不同数值类型的带权超网络中。最后给出了超网络维数的若干性质。

关键词：复杂网络;超图;超网络;分形维数;网络维数;超网络维数

中图分类号： TP393

文献标志码：A

Measure method and properties of weighted hypernetwork

LIU Shengjiu1，2， LI Tianrui1，2*， YANG Zonglin1，2， ZHU Jie3

1.School of Information Science and Technology， Southwest Jiaotong University， Chengdu Sichuan 611756， China;

2.Sichuan Key Laboratory of Cloud Computing and Intelligent Technique， Chengdu Sichuan 611756， China;

3. School of Information Science and Technology， Tibet University， Lhasa Tibet 850000， China

Abstract：

Hypernetwork is a kind of networks which is more complex than the ordinary complex network. Hypernetwork can describe complex system existing in the real world more appropriately than complex network since every hyperedge of it can connect any number of nodes. A new method to measure hypernetwork — Hypernetwork Dimension （HD） was proposed aiming to the shortcomings and deficiencies of existing measure method of hypernetwork. Hypernetwork dimension was expressed as twice as much as the ratio of the logarithm of the sum of all nodes weights and product of corresponding hyperedges weight in all hyperedges to the logarithm of the product of sum of hyperedges weights and sum of nodes weights. The hypernetwork dimension was able to be applied to the weighted hyperworks with many different numerical types of both nodes weights and hyperedges weights， such as positive real numbers， negative real numbers， pure imaginary numbers， and even complex numbers. Finally， several important properties of the proposed hypernetwork dimension were discussed.

Key words：

complex network; hypergraph; hypernetwork; Fractal Dimension （FD）; Network Dimension （ND）; hypernetwork dimension

0 引言

圖论是复杂网络研究的基础。自18世纪欧拉对哥尼斯堡七桥问题的研究而开创图论以来，图论已在很多领域得到极为广泛的应用。现代意义上复杂网络的研究发轫于20世纪中叶两位匈牙利数学家提出的ER（ErdosRenyi）随机网络模型[1]，随后，WS（WattsStrogatz）/NW（NewmanWatts）小世界网络模型[2-3]及BA（BarabasiAlbert）无标度网络模型[4]等多种其他类型的复杂网络模型相继出现，复杂网络逐渐成为一个独立的学科而日益受到人们极大的关注，由此导致复杂性科学的产生。

复杂网络起源于图。在通常意义上的复杂网络中，一条边能且只能连接2个节点，但在对现实生活中的复杂系统进行研究中人们发现，通常意义上的复杂网络并不能很好地刻画一条边连接多个节点的特殊网络，如作者合著网络等。在作者合著网络中，一个作者著有多篇作品，同时一篇作品由多个作者合作完成。这类特殊网络比通常意义上的复杂网络更为复杂，于是需要用比复杂网络更为复杂的网络来对其进行研究，这就是超网络[5-6]。

现阶段对超网络主要有两种不同的观点：一种观点认为凡是可以用超图描述的网络均可以视为超网络，也就是Hypernetwork型超网络[7];另一种观点认为由多层网络构成的网络可以视为超网络，也就是Supernetwork型超网络[8]。Hypernetwork型超网络突破了通常意义上的复杂网络一条边只能连接2个节点的局限;而Supernetwork型超网络超越了通常意义上的复杂网络不能刻画多层网络的局限，分别对复杂网络在不同的维度上进行了拓展。本文只对超图类型的超网络进行研究。

由于图及超图均可以通过邻接矩阵及关联矩阵进行描述，通过邻接矩阵及关联矩阵构建复杂网络及超网络是一种可行的方法。通过图的邻接矩阵及超图的关联矩阵构建不同类型的复杂网络及超网络是分析研究复杂网络及超网络的可行方法[9-10]。对于复杂网络而言，度量复杂网络的方法主要有网络阶数、网络直径、网络平均路径长度、网络聚集系数等多种不同的方法，但这些度量方法大多针对的是无权网络，对带权网络而言，很多度量方法并不适用。对带权网络而言，节点及边均可以赋予权重，而且权重类型可以包括正实数、负实数、纯虚数及复数等多种不同的类型。在这些度量中，网络维数是一种便捷可行的度量方法[11]。

由于超图比图更为复杂，超网络也比复杂网络更为复杂。类似于图中的节点与边，超图中也有与之对应的节点与超边。对超网络的度量方法而言，一般情况下是直接沿用复杂网络的度量方法。采用这些方法在继承复杂网络度量方法优点的同时也留存了一些固有的缺陷与不足，如效率过低、普适性弱等，而且难以移植并应用于带权超网络等。与带权图类似，带权超图中，节点及超边也可以赋予不同类型的权重，包括正实数、负实数、纯虚数及复数等; 于是可以将度量复杂网络的网络维数进行拓展并应用到超网络中，从而得到超网络的度量方法，也就是超网络维数。超网络维数可以度量超网络中节点与超边的权重分别为正实数、负实数、纯虚数及复数等多种不同类型的带权超网络。

1 预备知识

1.1 超图与超网络

假设集合V=（v1，v2，…，vn）是一个非空有限集，其中，若有ei≠（i=1， 2， …， |E|），且有∪|E|i=1ei=V，则称二元关系H=（V， E）为一个超图。在超图H中，V={v1， v2， …， vi， …}（1≤i≤|V|）是超图H中所有节点的集合，E={e1， e2， …， ej， …}（1≤j≤|E|）是超图H中所有超边的集合。|V|表示超图H中所有节点的数量，称为H的阶，|E|表示超图H中所有超边的数量，且有EP（V）＼，其中P（V）表示V的幂集。若超图H中两个节点同属于一条超边，则称这两个节点邻接;若两条超边的交集非空，则称这两条超边邻接。一般情况下研究的超图均是无向超图，尽管目前已有多种不同的有向超图理论[12-14]被提出，但对有向超图的研究并不是很多，相关的理论并不成熟，在理论与应用等方面仍存在很多需要进一步完善的地方。本文只对无向超图进行研究。

超图脱胎于图，超图中的超边有别于图中的边，图及超图均可以用邻接矩阵或关联矩阵进行刻画。下面分别论述超图的邻接矩阵及关联矩阵。

定义1[15]对超图H=（V， E）而言，其邻接矩阵A（H）是一个|V|×|V|阶的方阵，其中A（i， j）的值为在超图的关联二部图中，从节点i到节点j的2长路的数目。

定义2[16]对超图H=（V， E）而言，其关联矩阵C（H）是一个|V|×|E|阶的矩阵，其中，若节点vi包含在超边ej中，则有Cij=1，否则，Cij=0。

超图的邻接矩阵及关联矩阵的区别主要在于，邻接矩阵一定是对称矩阵，但关联矩阵不一定是对称矩阵;关联矩阵是01矩阵，但邻接矩阵不一定是01矩阵。若超图中每条边只关联两个节点，则超图H就退化为普通意义上的图，此时超图的邻接矩阵就是图的邻接矩阵。超图与其关联矩阵是一一对应的，一个超图只对应一个关联矩阵，反之也成立。但超图与其邻接矩阵并不一定是一一对应的，可能存在同一个邻接矩阵对应多个超图的情形。在超网络的研究中，往往通过与超图一一对应的关联矩阵对其进行分析研究。

1.2 超网络参数

对于图及通常意义上的复杂网络来说，由于一条边只能连接2个节点，度是描述网络的重要参数。在超网络中，由于一条超边可以连接任意数量的节点，描述超网络的参数有节点度、节点超度及超边度等，下面分别进行论述。

定义3[17]超图H中超边ei的节点度为超边ei连接的节点个数，记为dHd（ei）。

定义4[17]超图H中节点vi的节点超度为包含节点vi的超边个数，记为dHhd（vi）。

定义5[10]超图H中超边ei的超边度是指与超边ei邻接的其他超边个数，记为dHed（ei）。

在超图H的关联矩阵C（H）中，节点度即为对应的列中非零元素的数目，表述为：

dHd（ei）=∑Vj=1Cij （1）

节点超度即为对应的行中非零元素的数目，表述为：

dHhd（vi）=∑Ej=1Cji （2）

超边度即为与对应的列相乘结果非零的列的數目，表述为：

dHed（ei）=∑Vj=1Sgn（∑Vk=1CijCkj） （3）

通过初始超图的迭代TracySingh积运算可以得到自相似超网络，对自相似超网络而言，可以通过分形维数（Fractal Dimension， FD）对其进行分析。

定义6[10]超图的分形维数为其超边包含的节点数之和的对数值和节点数与超边数乘积对数值的比值的2倍，即：

FD（H）=2log∑i∈V∑j∈ECijlogVE （4）

定义7[10]超图的密度是指超图H的所有超边包含的节点数目之和与超图最多可包含的节点数目之和的比值，记为Density（H），即：

Density（H）=∑i∈V∑j∈ECijVE （5）

由于非空超图至少包含有一条非空超边，则有1≤∑i∈V∑j∈ECij≤VE，故一般情况下，0

由于超图中一条超边可以连接任意数目的节点，即其节点度可以取任意数值。但在对超图的研究中更多的是关注节点度相同的超图，即k均匀超图。在这种情况下，超图中的每个超边均连接有k个节点。因此，2均匀超图就是通常意义上的图。显然，图是超图的特例，而超图是广义上的图。这从另一方面论证了图是超图的子集，而超图是图的超集。

1.3 网络维数

对基于矩阵运算得到的自相似复杂网络进行分析，对节点权重及边权重为01形式的无权自相似复杂网络的分形维数进行拓展，可以得到适用于带权复杂网络的网络维数[11]。

定义8[11]复杂网络的网络维数（Network Dimension， ND）为其边权重和的对数值与其节点权重和的对数值的比值，即：

ND（G）=log∑e∈Ef（e）log∑v∈Vf（v） （6）

式（6）中：f（e）为复杂网络G的边权重， f（v）为复杂网络G的节点权重。

借助欧拉公式，可以将网络维数由节点权重及边权重均为正实数的带权图推广到节点权重及边权重为负实数、纯虚数及复数等多种不同权重类型的带权图。欧拉公式表述为：

eix=cosx+i sinx （7）

由于正弦函数及余弦函数均为周期函数，式（7）其实是一个多值周期函数，一般情况下，只在一个周期内对其进行分析即可。

2 超网络度量方法

本文将超网络的度量方法由节点权重及超边权重均为01形式的无权超网络逐步推广到节点权重及超边权重分别为正实数、负实数、纯虚数及复数等多种不同权重类型的带权超网络，先对无权超网络进行分析。

对节点权重及超边权重为01形式的无权超网络而言，其超网络维数即是其分形维数，即为式（4）所示。

结合式（4）及式（6），对带权图的网络维数进行拓展，可以得到带权超网络的超网络维数（Hypernetwork Dimension， HD），即为所有超边包含的节点权重之和与对应超边权重乘积和的对数值与节点权重之和与超边权重之和乘积对数值比值的两倍，表述为：

HD（H）=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （8）

很显然，对节点权重f（v）及超边权重f（e）均为正实数的带权超网络而言，可以直接应用式（8）进行计算。对于节点权重及超边权重为负实数、纯虚数及复数的带权超网络而言，需要借助式（7）中欧拉公式进行计算。

初始状况下，假设f（v）及f（e）均为正实数，即有：f（v）∈R+，且f（e）∈R+。利用式（7）中的欧拉公式，可以分析节点权重及超边权重为负实数、纯虚数及复数的其他情形。

对负实数形式的节点权重-f（v）及超边权重-f（e）而言，有：

log（-f（v））=logeiπf（v）

log（-f（e））=logeiπf（e）（9）

对纯虚数形式的节点权重if（v）及超边权重if（e）而言，有：

logif（v）=logeiπ2f（v）

logif（e）=logeiπ2f（e）（10）

对复数形式的节点权重（a+bi）f（v）及超边权重（a+bi）f（e）而言，有：

log（a+bi）f（v）=loga2+b2eitan-1baf（v）

log（a+bi）f（e）=loga2+b2eitan-1baf（e）（11）

由于超網络的节点权重及超边权重的值均可以取正实数、负实数、纯虚数及复数，本文分别对节点权重为正实数、负实数、纯虚数及复数情形下的不同权重组合进行分析，每一种情形下各有四种不同的权重组合。接下来分别对此进行分析，首先是节点权重为正实数的情形。

2.1 节点权重为正实数的超网络

对节点权重为正实数，超边权重分别为正实数、负实数、纯虚数、复数等四种不同的权重组合进行分析，共有四种不同的权重组合，下面分别进行讨论。

对节点权重为正实数、超边权重为正实数的超网络来说，其超网络维数为：

HDPP=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （12）

对节点权重为正实数、超边权重为负实数的超网络来说，其超网络维数为：

HDPN=2log∑e∈E（-f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈E-f（e）=

2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e）

（13）

对节点权重为正实数、超边权重为纯虚数的超网络来说，其超网络维数为：

HDPI=2log∑e∈E（if（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Eif（e）=

2logi∑e∈E（f（e）∑v∈ef（v））logi∑v∈Vf（v）∑e∈Ef（e）=

2logeiπ2∑e∈E（f（e）∑v∈ef（v））logeiπ2∑v∈Vf（v）∑e∈Ef（e） （14）

对节点权重为正实数、超边权重为复数的超网络来说，其超网络维数为：

HDPC=2log∑e∈E（a+bi）f（e）∑v∈ef（v）log∑v∈Vf（v）∑e∈E（a+bi）f（e）=2log（a+bi）∑e∈E（f（e）∑v∈ef（v））log（a+bi）∑v∈Vf（v）∑e∈Ef（e）=2loga2+b2eitan-1ba∑e∈E（f（e）∑v∈ef（v））loga2+b2eitan-1ba∑v∈Vf（v）∑e∈Ef（e）（15）

2.2 节点权重为负实数的超网络

接下来，对节点权重为负实数，超边权重分别为正实数、负实数、纯虚数、复数等四种不同的权重组合进行分析，共有四种不同的权重组合，下面分别进行讨论。

对节点权重为负实数、超边权重为正实数的超网络来说，其超网络维数为：

HDNP=2log∑e∈E（f（e）∑v∈e-f（v））log∑v∈V-f（v）∑e∈Ef（e）=2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e） （16）

对节点权重为负实数、超边权重为负实数的超网络来说，其超网络维数为：

HDNN=2log∑e∈E（-f（e）∑v∈e-f（v））log∑v∈V-f（v）∑e∈E-f（e）=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （17）

对节点权重为负实数、超边权重为纯虚数的超网络来说，其超网络维数为：

HDNI=2log∑e∈E（if（e）∑v∈e-f（v））loge∑v∈V-f（v）∑e∈Eif（e）=2log-i∑e∈E（f（e）∑v∈ef（v））log-i∑v∈Vf（v）∑e∈Ef（e）=2loge32iπ∑e∈E（f（e）∑v∈ef（v））loge32iπ∑v∈Vf（v）∑e∈Ef（e） （18）

对节点权重为负实数、超边权重为复数的超网络来说，其超网络维数为：

HDNC=2log∑e∈E（a+bi）f（e）∑v∈e-f（v）log∑v∈V（-f（v））∑e∈E（a+bi）f（e）=2log-（a+bi）∑e∈E（f（e）∑v∈ef（v））log-（a+bi）∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π）∑v∈Vf（v）∑e∈Ef（e） （19）

2.3 节点权重为纯虚数的超网络

继续对节点权重为纯虚数，超边权重分别为正实数、负实数、纯虚数、复数等四种不同的权重组合进行分析，共有四种不同的权重组合，下面分别进行讨论。

对节点权重为纯虚数、超边权重为正实数的超网络来说，其超网络维数为：

HDIP=2log∑e∈E（f（e）∑v∈eif（v））log∑v∈Vif（v）∑e∈Ef（e）=2logi∑e∈E（f（e）∑v∈ef（v））logi∑v∈Vf（v）∑e∈Ef（e）=2logeiπ2∑e∈E（f（e）∑v∈ef（v））logeiπ2∑v∈Vf（v）∑e∈Ef（e） （20）

对节点权重为纯虚数、超边权重为负实数的超网络来说，其超网络维数为：

HDIN=2log∑e∈E（-f（e）∑v∈eif（v））loge∑v∈Vif（v）∑e∈E-f（e）=2log-i∑e∈E（f（e）∑v∈ef（v））log-i∑v∈Vf（v）∑e∈Ef（e）=

2loge32iπ∑e∈E（f（e）∑v∈ef（v））loge32iπ∑v∈Vf（v）∑e∈Ef（e） （21）

对节点权重为纯虚数、超边权重為纯虚数的超网络来说，其超网络维数为：

HDII=2log∑e∈E（if（e）∑v∈eif（v））log∑v∈Vif（v）∑e∈Eif（e）=2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e） （22）

对节点权重为纯虚数、超边权重为复数的超网络来说，其超网络维数为：

HDIC=2log∑e∈E（a+bi）f（e）∑v∈eif（v）log∑v∈Vif（v）∑e∈E（a+bi）f（e）=2log（a+bi）i∑e∈E（f（e）∑v∈ef（v））log（a+bi）i∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π2）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π2）∑v∈Vf（v）∑e∈Ef（e） （23）

2.4 节点权重为复数的超网络

最后，本文对节点权重为复数，超边权重分别为正实数、负实数、纯虚数、复数四种不同的权重组合进行分析，共有四种不同的权重组合，下面分别进行讨论。

对节点权重为复数、超边权重为正实数的超网络来说，其超网络维数为：

HDCP=2log∑e∈Ef（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈Ef（e）=2log（a+bi）∑e∈E（f（e）∑v∈ef（v））log（a+bi）∑v∈Vf（v）∑e∈Ef（e）=2loga2+b2eitan-1ba∑e∈E（f（e）∑v∈ef（v））loga2+b2eitan-1ba∑v∈Vf（v）∑e∈Ef（e） （24）

对节点权重为复数、超边权重为负实数的超网络来说，其超网络维数为：

HDCN=2log∑e∈E-f（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈E（-f（e））=2log-（a+bi）∑e∈E（f（e）∑v∈ef（v））log-（a+bi）∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π）∑v∈Vf（v）∑e∈Ef（e） （25）

对节点权重为复数、超边权重为纯虚数的超网络来说，其超网络维数为：

HDCI=2log∑e∈Eif（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈Eif（e）=2log（a+bi）i∑e∈E（f（e）∑v∈ef（v））log（a+bi）i∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π2）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π2）∑v∈Vf（v）∑e∈Ef（e） （26）

对节点权重为复数、超边权重为复数的超网络来说，其超网络维数为：

HDCC=2log∑e∈Ef（a+bi）（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈E（a+bi）f（e）=2log（a+bi）2∑e∈E（f（e）∑v∈ef（v））log（a+bi）2∑v∈Vf（v）∑e∈Ef（e）=2log（a2+b2）eitan-12aba2-b2∑e∈E（f（e）∑v∈ef（v））log（a2+b2）eitan-12aba2-b2∑v∈Vf（v）∑e∈Ef（e） （27）

至此，本文分析了节点权重及超边权重分别为正实数、负实数、纯虚数及复数等多种不同类型的权重组合，共16种情形。通过2.1～2.4节，可以较为直观地看出16种不同的权重组合之间的关系。本文下面对这16种不同的权重组合进行分析，实际上就是对式（12）～（27）的16个公式进行分析。

3 超网络维数关系研究

通过上述分析发现，在16种不同的情形中，共有8种不同的类型，对8种不同的等价类进行分析，可以得到如图1所示的关系图。

从图1可以看出，从处于中心的节点权重及超边权重均为正实数的带权超网络出发，可以逐步转化到其他15种权重类别的带权超网络，而且16种带权超网络共有8种超网络维数。于是，在实际的分析研究中，只需要对8种不同的带权超网络进行研究即可全部涵盖所有的16种带权超网络。

进一步，本文对图1中列出的8种超网络类别进行分析，可以得到图2所示的超网络维数关系图。

从图2可以看出，8种不同的超网络维数呈现出极为对称的上下对称、左右对称的轴对称关系。于是，在深入的分析研究中，只需对4种不同的超网络维数进行分析即可推广并应用到其他类型的带权超网络中。

4 超网络维数性质研究

在论述了超网络的度量方法——超网络维数之后，本文对超网络维数的性质进行分析研究。由于对超网络的研究均是从最简单的无向无权超图开始的，本文对超网络维数性质的研究也从最简单的无向无权超图开始，再将其推广到更一般的其他情形。

定理1 任意超网络的超网络维数不小于0。

证明 根据定义，对式（4）进行分析，可以得到：

HD（H）=2log∑i∈V∑j∈ECijlogVE≥2log1logVE=0 （28）

定理1得证。

对由不同超图得到的TracySingh积超图进行分析，则可以得到如下定理。

定理2 对于n个超图H（i）（1≤i≤n）的TracySingh积超图H（n）而言，H（n）的超网络维数是所有构成此TracySingh积超图的H（i）（1≤i≤n）的超边包含的节点数目的对数值总和与节点数目与超边数目乘积对数值总和的比值的两倍，用公式表述，即：

若有：

H（n）=ni=1H（i） （29）

则有：

HD（H（n））=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i） （30）

证明 根据TracySingh积超图的定义，则有：

V（n）=∏ni=1V（i）E（n）=∏ni=1E（i）∑j∈V（n）k∈E（n）Cjk=∏ni=1∑j∈V（i）k∈E（i）Cjk（31）

将式（31）代入式（4），则可以得到：

HD（H（n））=2log∑j∈V（n）k∈E（n）CjklogV（n）E（n）=2log∏ni=1∑j∈V（i）k∈E（i）Cjklog∏ni=1V（i）∏ni=1E（i）=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i）（32）

定理2得证。

若由一个超图进行n次迭代TracySingh积运算，则得到的所有TracySingh积超图的超网络维数都相等，而且都等于初始超图的超网络维数，则可以得到如下引理。

引理1 迭代TracySingh积超图的超网络维数都相等，而且都等于初始超图的超网络维数。

证明 对式（32）进行分析，则可以得到：

HD（H（n））=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i）=2nlog∑j∈V（i）k∈E（i）CjknlogV（i）E（i）=2log∑j∈V（1）k∈E（1）CjklogV（1）E（1）（33）

引理1得证。

定理3 对k均匀超图H=（V， E）而言，其超网络维数可以表述为：

HD（H）=2logkElogVE （34）

证明 在k均匀超图H=（V， E）中，其一条超边连接有k个节点，则有：

∑i∈V∑j∈ECij=kE （35）

將式（35）代入式（4），即得式（34）。定理3得证。

由于图是超图的特例，图就是2均匀超图，对图形式的2均匀超图进行分析，则可以得到如下引理。

引理2 对图形式的2均匀超图H=（V， E）而言，其超网络维数可以表述为：

HD（H）=2log2ElogVE （36）

证明 根据2均匀超图的定义，结合定理2，引理2显然成立。引理2得证。

从引理2可以得知，分别从图及超图的视角度量通常意义上的图，得到的网络维数及超网络维数可能并不一致。

定理4 对超图H=（V， E）而言，其网络维数可以表述为：

HD（H）=2+2logDensity（H）logVE （37）

证明 将式（5）代入式（4），有：

HD（H）=2logVEDensity（H）logVE=2logVE+2logDensity（H）logVE=2+2logDensity（H）logVE （38）

定理4得证。

由于0

5 结语

超图是广义上的图，超网络是较通常意义上的复杂网络更为复杂的一种网络。针对现有超网络的度量方法并不能全面刻画超网络的各项特性，本文从自相似超网络的分形维数出发，结合复杂网络的网络维数，提出了一种度量超网络的新方法——超网络维数，具体表述为超网络中所有超边包含的节点权重之和与对应超边权重乘积之和的对数值与节点权重之和与超边权重之和乘积对数值的比值的两倍。本文提出的超网络维数可以应用于节点权重及超边权重为正实数、负实数、纯虚数及复数等多种不同数值类型的带权超网络。最后，本文以最简单的无向无权超图为例，论述了所提出的超网络维数的若干重要性质。后续研究的重点在于结合现实生活中真实复杂系统的具体特性对所提出的超网络维数进行深入细致的分析，尤其是对具体实例及实验仿真进行深入的分析研究，同时探讨动态环境下超网络维数的演化机理及演进趋势等。

参考文献 （References）

[1]ERDOS P， RENYI A. On random graphs I[J]. Publicationes Mathematicae， 1959， 6： 290-297.

[2]WATTS D J， STROGATZ S H. Collective dynamics of ′smallworld′ networks[J]. Nature， 1998， 393： 440-442.

[3]NEWMAN M E J， WATTS D J. Renormalization group analysis of the smallworld network model[J]. Physics Letter A， 1999， 293（4/5/6）： 341-346.

[4]BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）： 509-512.

[5]ERDOS P， HAJNAL A. On the chromatic number of graphs and set systems[J]. Acta Mathematica Academiae Scientiarum Hungarica， 1966， 17： 61-99.

[6]BERGE C. Graphs and Hypergraphs[M]. Amsterdam： NorthHolland Publishing Company， 1973： 3-11.

[7]ESTRADA E， RODR GUEZVEL ZQUEZ J A. Subgraph centrality in complex networks[J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 71（5 Pt 2）：056103.

[8]NAGURNEY A， DONG J. Supernetworks： DecisionMaking for the Information Age[M]. Cheltenham： Edward Elgar Publishing， 2002： 844-847.

[9]刘胜久， 李天瑞， 洪西进， 等. 基于矩阵运算的复杂网络构建方法[J]. 中国科学： 信息科学， 2016， 46（5）： 610-626. （LIU S J， LI T R， HORNG S J， et al. Complex network construction based on matrix operation[J]. SCIENTIA SINICA Informationis， 2016， 46（5）： 610-626.）

[10]刘胜久， 李天瑞， 洪西进， 等. 超网络模型构建及特性分析[J]. 计算机科学与探索， 2017， 11（2）： 194-211. （LIU S J， LI T R， HORNG S J， et al. Hypernetwork model and its properties[J]. Journal of Frontiers of Computer Science and Technology， 2017， 11（2）： 194-211.）

[11]刘胜久， 李天瑞， 刘小伟. 網络维数：一种度量复杂网络的新方法[J]. 计算机科学， 2019， 46（1）： 51-56. （LIU S J， LI T R， LIU X W. Network dimension： a new measure for complex networks[J]. Computer Science， 2019， 46（1）： 51-56.）

[12]GALLO G， LONGO G， NGUYEN S. Directed hypergraphs and applications[J]. Discrete Applied Mathematics， 1993， 42（2/3）： 177-201.

[13]ERGINCAN F， GREGORY D A. Directed Moore hypergraphs[J]. Discrete Applied Mathematics， 1995， 63（2）： 117-127.

[14]黃汝激. 超网络的有向k超树分析法[J]. 电子科学学刊， 1987， 9（3）： 244-255. （HUANG R J. Directedkhypertree method for hypernetwork analysis[J]. Journal of Electronics， 1987， 9（3）： 244-255.）

[15]FENG K， LI W. Spectra of hypergraphs and applications[J]. Journal of Number Theory， 1996， 60（1）： 1-22.

[16]王建方. 超图的理论基础[M]. 北京： 高等教育出版社， 2006： 1-3. （WANG J F. Theoretical Principle of Hypergraph[M]. Beijing： Higher Education Press， 2006： 1-3.）

[17]胡枫， 赵海兴， 马秀娟. 一种超网络演化模型构建及特性分析[J]. 中国科学： 物理学 力学 天文学， 2013， 43（1）： 16-22. （HU F， ZHAO H X， MA X J. An evolving hypernetwork model and its properties[J]. SCIENTIA SINICA Physica， Mechanica & Astronomica， 2013， 43（1）： 16-22.）

This work is partially supported by the National Natural Science Foundation of China （61262058， 61751216）.

LIU Shengjiu， born in 1988， Ph. D. His research interests include complex network， natural language processing， data mining.

LI Tianrui， born in 1969， Ph. D.， professor. His research interests include rough set， granular computing， data mining.

YANG Zonglin， born in 1994， M. S. candidate. His research interests include natural language processing， cloud computing.

ZHU Jie， born in 1973， Ph. D.， professor. His research interests include natural language processing， data mining.