基于矩阵运算的超网络构建方法研究及特性分析

刘胜久，李天瑞，洪西进,3，王红军，珠杰,4

（1. 西南交通大学 信息科学与技术学院，四川 成都 611756; 2. 西南交通大学 四川省云计算与智能技术高校重点实验室，四川 成都 611756; 3. 台湾科技大学 资讯工程系，台湾 台北 10607; 4. 西藏大学 计算机系，西藏 拉萨 850000）

复杂网络可较好地描述并刻画复杂系统，对其系统性研究起源于20世纪Erdos与Renyi二者合作提出的ER随机网络模型[1]。一些相近的其他模型，包括WS/NW小世界网络模型[2-3]及BA无标度网络模型[4]等同类别其他复杂网络模型相继提出。

小世界特性与无标度特性被称为复杂网络两大特性，对它们进行分析也成为复杂网络的研究热点[5-6]。近几年，自相似特性成为复杂网络新的研究热点[7-8]。小世界网络模型、无标度网络模型与自相似网络模型的各种改进是复杂网络的重点研究内容[9]。同时，采用矩阵运算对复杂网络进行构建与分析已得到一定的研究与应用[10]。

真实世界中，通常意义上的网络或图并不能对实际网络的所有特性进行刻画。对超大规模网络系统进行研究，往往会出现网络中有网络，即超网络等问题。超网络的特性和传统复杂网络的特性有很大差异[11-12]。对超网络的分析仍处于初始阶段，并没有形成公认的超网络的定义。本文主要对层次形态的Supernetwork型超网络进行分析研究。

当前，人们仍在积极探寻借助全新的分析理论及研究策略对超网络进行研究。本文尝试根据邻接矩阵来分析研究超网络，借助矩阵运算生成不同类型的超网络，即根据简单初始图序列得到超网络邻接矩阵的迭代Khatri-Rao积运算操作生成自相似超网络，同时根据多个简单初始图序列得到超网络邻接矩阵的Khatri-Rao和运算操作生成随机超网络，并对二者的特性进行深入的分析研究。

1 预备知识

1.1 超网络

对任意图序列G(1),G(2),···,G(i),···,G(n)， 其中G(i)=(V(i),E(i))(1≤i≤n)是一个无向无环无|权无|重边简单图，而且V(i)=(v(i)1,v(i)2,···,v(i)j,···)(1≤ j≤||V(i)||)、E(i)=(e(i)1,e,···,e,···)(1 ≤ k ≤ |||E|||)分 别是G 中的节点集及(i)2(i)k(i)(i)||边集，且 E(i)⊆V(i)×V(i)， n 表示图序列长度，|| V(i)||及分 别表示G 中节点数目及边数目。(i)

定义1 超网络是指由图序列G(1),G(2),···,G(i),···,G(n)构 成且对应节点序列 v(1)j,v(2)j,···,v(i)j,···,v(n)j相互关联的层次形态的网络，记为 S，表述为

定义2 超网络的邻接矩阵 A (S)是指由构成超网络 S的图序列邻接矩阵构成的分块矩阵，即

定义3 超网络的边际度是指超网络各层网络的节点度。

定义4 超网络的边际度分布是指超网络中各层网络节点度的分布，包括概率分布及频率分布。

定义5 超网络的边际度分布多项式是指超网络中各层网络以节点度为次数、以节点度频数为系数的各个单项式构成的多项式。

根据定义1～5，可对超网络联合度、联合度分布与联合度分布多项式进行定义。

以 n =2 时 ，2个节点数目相同的网络G(1)与 G(2)构成的最简单超网络 S为例，超网络 S的边际度分布多项式与联合度分布多项式为

定义6 超网络的密度是指超网络 S中边数与最多可能边数的比值，记为Density ( S)，则有

1.2 分形理论

分形几何为分形理论数学基础，并进而发展到分形图案等分形方面的多个研究应用领域[13]。

定义7[14]分形矩阵是由迭代相加生成的一簇具备分形性质的矩阵。

图案生成是分形矩阵最初应用领域[15]。对于矩阵 Am×n， 用 A 的 各 元 素 aij(1 ≤i≤ m,1≤ j≤ n) 与 A的各元素进行相加，再用生成的新矩阵更换 aij，生成局部和整体自相似的一个新矩阵。若一直将上述操作延续下去，则会生成自相似的一簇新矩阵：各元素与 A进行相加后更换而生成的。分形矩阵就是上述更换操作生成的一簇新矩阵样可以根据迭代Kronecker积运算而得到。本文在超网络邻接矩阵中引入矩阵运算。

1.3 矩阵理论

对图来说，其邻接矩阵的每列或每行代表一节点，图序列间通过节点之间相互的关联生成的超网络可用图序列邻接矩阵构成的分块矩阵进行刻画，而且分块矩阵中的每一个分块都是一个图的邻接矩阵。对分块矩阵形式超网络的邻接矩阵进行分析研究，基于Kronecker积运算、Kronecker和运算有Khatri-Rao积运算、Khatri-Rao和运算。

AB与的Khatri-Rao积运算[17]可表示为

AB与的Khatri-Rao和运算[18]可表示为

2 基于矩阵运算超网络模型

2.1 自相似超网络模型

对于一个节点数目相同图序列的邻接矩阵构成的分块矩阵A，分别用A的各分块矩阵与自身相乘生成的矩阵去更换自身，会生成局部与整体自相似的一个新矩阵，将此操作不断延续下去，可以生成自相似的一簇新矩阵。这些新矩阵可看成邻接矩阵，对应超网络即为A迭代Khatri-Rao积运算的结果，也就是自相似超网络。

在文献[18]中，Liu研究了Khatri-Rao积运算的一些特性。此处，将超网络对应的邻接矩阵看成各个图邻接矩阵构成的分块矩阵，则其Khatri-Rao积运算的结果就是各个图邻接矩阵Kronecker积运算所得到的结果。

对超网络来说，其邻接矩阵中，各分块矩阵的列数或行数代表此层网络节点数目，分块矩阵的数目代表超网络的层数，超网络密度为各层中网络密度的算术平均值，于是有

超网络边际度分布多项式与联合度分布多项式都将节点度看成单项式次数。直接对初始超网络边际度分布多项式与联合度分布多项式进行计算可得到超网络迭代Khatri-Rao积运算的边际度分布多项式与联合度分布多项式，则有定理1。

定理1 超网络迭代Khatri-Rao积超网络的边际度分布多项式可对边际度分布多项式进行系数相乘且次数相乘得到。

证明 分块矩阵迭代Khatri-Rao积运算等同于对分块矩阵的各分块进行迭代Kronecker积运算操作，而超网络边际度分布多项式就是各分块对应网络的度分布多项式。Kronecker积运算为两个矩阵的各行分别进行相乘运算，生成的结果矩阵中各行非零元素的数目就是节点所对应的边际度。可将矩阵各行非零元素数目看成单项式次数，通过超网络边际度分布多项式对超网络边际度分布进行处理时，行之间的相乘在边际度分布多项式中就是次数与次数之间的相乘。定理1得证。

超网络邻接矩阵Khatri-Rao积运算过程中，各分块矩阵Kronecker积运算相互独立，定理1涉及的超网络边际度分布多项式的规律可应用到联合度分布多项式中，则有引理1。

引理1 超网络迭代Khatri-Rao积超网络联合度分布多项式可对联合度分布多项式进行系数相乘且次数相乘得到。

证明 分块矩阵Khatri-Rao积运算操作中，各分块矩阵Kronecker积运算相互独立，则可进行组合。各分块矩阵Kronecker积运算结果可通过边际度分布多项式系数相乘且次数相乘得到，则分块矩阵Khatri-Rao积运算结果同样可根据联合度分布多项式系数相乘及次数相乘操作获取。引理1得证。

分形理论方面，论证一图形是分形图形的实质是计算其分形维数。本文通过对自相似超网络进行研究，计算出此类自相似超网络分形维数。

定理2 超网络迭代Khatri-Rao积运算生成自相似超网络分形维数表述为生成此超网络各自相似网络分形维数几何平均值与1之和，即

证明 文献[9]中，迭代Kronecker积图的自相似网络分形维数表述为图边数两倍对数值与节点数对数值之比。自相似超网络方面，其分形维数体现为自相似网络分形维数的融合，由于其层次形态的特征，根据余维相加定律[19]，故为各自相似网络的分形维数几何平均值与1之和。定理2得证。

定理3 超网络迭代Khatri-Rao积运算生成自相似超网络分形维数一定不会超过3。

证明 自相似网络分形维数一定不会超过2，式(9)中有

显然，定理3成立。定理3得证。

通常情况下，只对连通且非二分图序列的迭代Khatri-Rao积运算生成的超网络进行研究，基于定理3，则有引理2。

引理2 连通且非二分图序列迭代Khatri-Rao积运算生成超网络分形维数在2～3之间。

式(9)中有

结合定理3，有 2 ＜FD(S)＜3。引理2得证。

同时，通过超网络分块矩阵形式邻接矩阵迭代Khatri-Rao积运算生成的矩阵一样为分块矩阵，对此进行研究，可得到定理4。

定理4 连通且非二分图序列迭代Khatri-Rao积运算生成超网络直径不超过初始图直径和的两倍。

证明 文献[9]中，连通且非二分图邻接矩阵迭代Kronecker积运算生成Kronecker积图直径不超过初始图直径两倍。设构成超网络任一图 G(i)直径为 d(i)，于是自相似超网络任意一层网络中的任意一个节点均可在不超过内抵达任意一层网络中的任意一个节点。定理4得证。

根据定理4，计算超网络直径时，通过初始图直径可较为便捷得到所生成的自相似超网络直径。进一步，有引理3。

引理3 N 个完全图且非二分图序列迭代Khatri-Rao积运算生成超网络直径为 2 N。

证明 对完全图且非二分图来说，其迭代Kronecker积图直径为2，完全图且非二分图序列迭代Khatri-Rao积运算生成超网络各层直径均为2，此N 层超网络直径即为2 N 。引理3得证。

与定理4相似，引理3同样只在由连通且非二分图序列生成超网络情形下成立。

为更清晰论述自相似超网络不同维度的特性，将连通且非二分图序列迭代Khatri-Rao积运算生成自相似超网络与门格海绵[20]进行比较，门格海绵分形维数同样在2～3之间。

门格海绵中，设初始情况下正方体棱长 T0=1，正方体数量 N0=1 ， 周长 L0=12 ， 表面积 S0=6，体积V0=1， Tn、 Nn、 Ln、 Sn和 Vn分 别为第 n步迭代后生成门格海绵正方体的棱长、数量、周长、表面积及体积，则可以得到：

自相似超网络与门格海绵对比如表1所示。

表1 自相似超网络与门格海绵对比表Table 1 Comparison between self-similarity supernetwork and Menger sponge

2.2 随机超网络模型

基于矩阵运算随机超网络构建方法为：对于一簇随机选取初始超网络 S(1),S(2),···,S(i),···，将Khatri-Rao和运算顺次应用于此超网络对应邻接矩阵，可得到一个新矩阵，其对应超网络就是随机超网络。

超网络 Sa及 Sb对应边际节点度分布多项式PolyM(i)(Sa)、 PolyM(i)(Sb)中，将Khatri-Rao积运算应用于 Sa及 Sb对应邻接矩阵生成超网络 Sab的边际节点度分布可通过 P olyM(i)(Sa)与 P olyM(i)(Sb)的Khatri-Rao积运算而得到，即

类似地，将Khatri-Rao和运算应用于 Sa及 Sb对应邻接矩阵生成超网络的边际节点度分布可通过式(15)得到：

式(15)为通常意义上多项式乘法。对Khatri-Rao积采用系数相乘且次数相乘，类似地，对Khatri-Rao和采用系数相乘且次数相加可得到新超网络边际度分布。将两个超网络Khatri-Rao积运算边际度分布看成初始超网络边际节点度分布的非线性组合，同理，可将两个超网络Khatri-Rao和运算结果边际度分布看成初始超网络边际节点度分布的线性组合。随机选取的初始超网络，其边际度分布服从高斯分布，鉴于有限个高斯分布的线性组合同样是高斯分布，通过多个初始超网络Khatri-Rao和运算所得到超网络的边际度分布同样服从高斯分布。

与此类似，对超网络联合度分布进行分析也可得到与边际度分布相近{的结论。}

初始超网络集合 S(1),S(2),···,S(i),···中，对顺次选取 S(i)且通过Khatri-Rao和运算生成超网络 S(n)来说，其各层网络节点数目、边数目及密度可根据边际度分布多项式的分析研究得到：

2.3 不同组合超网络模型

拓展上文中超网络生成方法，可得出一般情形下基于矩阵运算超网络生成方法。通过一个、有限多个，乃至无限多个超网络Khatri-Rao积运算和/或Khatri-Rao和运算，可得到9类超网络模型，如表2所示，9类超网络相互之间的关系如图1所示。

表2 9类超网络统计表Table 2 Statistics of 9 supernetworks

图1 9类超网络关系图Fig. 1 Diagram of 9 supernetworks

3 基于矩阵运算超网络模型理论分析

3.1 基于矩阵运算超网络数量

边际度分布多项式与联合度分布多项式均无法反映超网络拓扑结构等特性，相同边际度分布多项式与联合度分布多项式可能对应不同超网络。

定理5 边际度分布相同超网络数量为各边际度分布对应网络数量的乘积，即

证明 n层超网络中，仅分析边际度分布，各层网络度分布相互独立，n层超网络数量等于各层相互独立网络数量之乘积。定理5得证。

定理5仅研究边际度分布相同超网络数量，不涉及联合度分布。因联合度分布涉及各层网络之间的关联与耦合等特征，对联合度分布欠缺必要的应对策略。对联合度分布相同超网络数量及边际度分布与联合度分布都相同超网络数量的分析有待进一步深入研究。

3.2 基于矩阵运算超网络敏感性

超网络敏感性分析主要对初始超网络波动对基于矩阵运算生成超网络的干扰进行研究。本文主要分析对超网络直径、分形维数和度分布的影响。

定理6 增添一个节点与至少一条边到构成自相似超网络的任意一个初始图后，自相似超网络直径增加量不超过2。

证明 增添一个节点与至少一条边到构成自相似超网络任一初始图，初始图节点间最短距离不变，而初始图原节点到新增节点距离不超过原始图直径加1，故超网络直径增量不超过2。定理6得证。

定理7 增添一条边到构成自相似超网络任意一个初始图后，自相似超网络直径减少量不超过该初始图直径。

证明 增添一条边到构成自相似超网络任一初始图，因增添边连接的节点为原图中不邻接的两节点，致使原图会增多至少一个回路，而此回路上任意一对节点间隔不超过回路长度的半数，所以此图直径为超网络直径减少量的上限。定理7得证。

式(9)为基于初始超网络生成自相似超网络分形维数，分析增添或去掉生成超网络初始图一个节点与一条边对超网络分形维数的影响就是对其分形维数一阶导数进行分析。不失一般性，对 Ga及 Gb生成的2层超网络 Sab分形维数的一阶导数进行分析：

式(20)中，分形维数和度分布多项式二阶导数联系紧密。这说明，在增添或去掉节点或者边时，可对度分布多项式进行计算，进而得到分形维数的波动情况。此研究可拓展到任意层次超网络。

分析自相似超网络边际度分布敏感性，具体方面，是对边际度分布多项式采用系数相乘，次数也相乘的操作。式(19)中，对边际度分布多项式进行分析，可得到：

通过式(21)可以发现，增添或去掉一个节点或一条边后，不能用微分公式来增量式更新，即不可微，也即敏感。所以，初始情形下，增添或去掉一个节点或一条边的微弱差异将伴随迭代次数的增加而因为连锁反应无限放大。分析自相似超网络联合度分布，可得出相似结论。

继续分析随机超网络敏感性，具体而言，是分析随机超网络边际度分布敏感性。随机超网络中，是将边际节点度分布多项式进行系数相乘且次数相加。式(19)中，对边际度分布多项式进行分析，可得

从式(22)中可以看出，增添或去掉一个节点或一条边后，可用微分公式来增量式更新，即可微，也即不敏感。所以初始情形下，尽管选取不同图但生成随机超网络度分布形态近似相同，均呈钟形高斯分布。分析随机超网络联合度分布，可得出相似结论。

引入微积分等理论与技术，在超网络敏感性分析方面有一些量化结论，但对超网络敏感性根源仍未完全透彻了解，后续研究中，重点在于继续使用微分方程等工具，对超网络敏感性进行深入研究。

4 结束语

本文主要对自相似超网络与随机超网络等通过矩阵运算生成超网络进行分析，通过超网络的邻接矩阵迭代Khatri-Rao积运算可生成自相似超网络，自相似特性在于其邻接矩阵为分形矩阵，连通且非二分图序列构成自相似超网络同时有小世界特性，在与门格海绵的对比中，阐明了自相似超网络的各项性质。多个超网络邻接矩阵Khatri-Rao和运算可生成随机超网络，随机特性在于有限个高斯分布的线性组合。通过边际度分布多项式及联合度分布多项式可计算出基于矩阵运算生成的超网络边际度分布与联合度分布等特性。此外，对超网络数量及敏感性等进行一定程度的量化分析。