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

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

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

　　《信息安全研究》(月刊)创刊于1998年，由国家信息中心主办中文学术期刊，主要刊登信息安全研究领域的原创性研究成果，其内容覆盖信息安全领域的各个学科。

　　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均匀超图就是通常意义上的图。显然，图是超图的特例，而超图是广义上的图。这从另一方面论证了图是超图的子集，而超图是图的超集。

期刊VIP网，您身边的高端学术顾问

文章名称： 带权超网络的度量方法及其性质

文章地址： http://www.qikanvip.com/jisuanjixinxiguanli/49882.html