第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201706055 网络出版t地址：http:/kns.cnki.net/cms/detail/23.1538.TP.20180412.0858.002.html 基于矩阵运算的超网络构建方法研究及特性分析 刘胜久2，李天瑞2，洪西进2，王红军2，珠杰24 (1.西南交通大学信息科学与技术学院，四川成都611756,2.西南交通大学四川省云计算与智能技术高校重点实 验室，四川成都611756：3.台湾科技大学资讯工程系，台湾台北10607：4.西藏大学计算机系，西藏拉萨850000) 摘要：基于邻接矩阵Khatri--Rao积运算及Khatri--Rao和运算，研究了构建超网络的方法，并通过边际节点度及联合 节点度来研究超网络的内在机理。将Khatri--Rao积运算迭代地应用于一个初始图序列组成超网络的邻接矩阵，得到 一个分形维数不超过3的自相似超网络。若所有初始图均是连通非二分图，则得到的超网络同时具有小世界特性， 其直径不超过所有初始图直径和的两倍。此外，将Khatri-Rao和运算顺次应用于多个初始图序列组成超网络的邻接 矩阵，得到一个边际节点度呈一维高斯分布而联合节点度呈高维高斯分布的随机超网络。最后，给出了基于矩阵运 算的超网络构建方法的若干性质。 关键词：矩阵运算；复杂网络；超网络：模型构建；分形维数：自相似超网络；随机超网络；特性分析 中图分类号：TP393文献标志码：A文章编号：1673-4785(2018)03-0359-07 中文引用格式：刘胜久，李天瑞，洪西进，等.基于矩阵运算的超网络构建方法研究及特性分析J.智能系统学报，2018,13(3)： 359-365. 英文引用格式：LIU Shengjiu,.LI Tianrui,,HORNG Xijin,etal.Supernetwork building based on matrix operation and property analysis[J.CAAI transactions on intelligent systems,2018,13(3):359-365. Supernetwork building based on matrix operation and property analysis LIU Shengjiu,LI Tianrui2,HORNG Xijin',WANG Hongjun'2,ZHU Jie3 (1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China;2.Sichuan Key Lab of Cloud Computing and Intelligent Technique,Southwest Jiaotong University,Chengdu 611756,China;3.Department of Computer Science and Information Engineering,National Taiwan University of Science and Technology,Taipei 10607,China;4.Department of Computer Science,Tibetan University,Lhasa 850000,China) Abstract:We study supernetwork building based on the Khatri-Rao product operation and the Khatri-Rao sum opera- tion on adjacency matrices.In addition,the marginal-and joint-node degrees are introduced to investigate the mechan- ism of a supernetwork.The Khatri-Rao product operation is iteratively applied to a simple initial network to form the ad- jacent supernetwork matrix and obtain a self-similarity supernetwork with fractal dimensions of no longer than 3.If all initial networks are connected with nonbipartite graphs,the obtained supernetwork has a diameter that does not exceed twice the summation of all initial networks.Furthermore,the Khatri-Rao sum operation is sequentially applied to mul- tiple simple initial networks to form adjacency matrices of supernetwork and obtain a random supernetwork with one marginal node degree,with one-dimensional Gaussian distribution,and a joint node degree,with a high-dimensional Gaussian distribution.Finally,several properties of the proposed supernetwork building based on matrix operation are presented. Keywords:matrix operation;complex network;supernetwork;model building;fractal dimension;self-similarity super- network;random supernetwork;property analysis 收稿日期：2017-06-14.网络出版日期：2018-04-12 复杂网络可较好地描述并刻画复杂系统，对其 基金项目：国家自然科学基金项目(61573292,61262058)】 通信作者：李天瑞.E-mail:tri@swjtu.cdu.cn. 系统性研究起源于20世纪Erdos与Renyi二者合
DOI: 10.11992/tis.201706055 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180412.0858.002.html 基于矩阵运算的超网络构建方法研究及特性分析 刘胜久1,2，李天瑞1,2，洪西进1,2,3，王红军1,2，珠杰1,2,4 （1. 西南交通大学 信息科学与技术学院，四川 成都 611756; 2. 西南交通大学 四川省云计算与智能技术高校重点实 验室，四川 成都 611756; 3. 台湾科技大学 资讯工程系，台湾 台北 10607; 4. 西藏大学 计算机系，西藏 拉萨 850000） 摘 要：基于邻接矩阵 Khatri-Rao 积运算及 Khatri-Rao 和运算，研究了构建超网络的方法，并通过边际节点度及联合 节点度来研究超网络的内在机理。将 Khatri-Rao 积运算迭代地应用于一个初始图序列组成超网络的邻接矩阵，得到 一个分形维数不超过 3 的自相似超网络。若所有初始图均是连通非二分图，则得到的超网络同时具有小世界特性， 其直径不超过所有初始图直径和的两倍。此外，将 Khatri-Rao 和运算顺次应用于多个初始图序列组成超网络的邻接 矩阵，得到一个边际节点度呈一维高斯分布而联合节点度呈高维高斯分布的随机超网络。最后，给出了基于矩阵运 算的超网络构建方法的若干性质。 关键词：矩阵运算；复杂网络；超网络；模型构建；分形维数；自相似超网络；随机超网络；特性分析 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2018)03−0359−07 中文引用格式：刘胜久, 李天瑞, 洪西进, 等. 基于矩阵运算的超网络构建方法研究及特性分析[J]. 智能系统学报, 2018, 13(3): 359–365. 英文引用格式：LIU Shengjiu, LI Tianrui, HORNG Xijin, et al. Supernetwork building based on matrix operation and property analysis[J]. CAAI transactions on intelligent systems, 2018, 13(3): 359–365. Supernetwork building based on matrix operation and property analysis LIU Shengjiu1,2 ，LI Tianrui1,2 ，HORNG Xijin1,2,3 ，WANG Hongjun1,2 ，ZHU Jie1,2,4 (1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China; 2. Sichuan Key Lab of Cloud Computing and Intelligent Technique, Southwest Jiaotong University, Chengdu 611756, China; 3. Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, Taipei 10607, China; 4. Department of Computer Science, Tibetan University, Lhasa 850000, China) Abstract: We study supernetwork building based on the Khatri-Rao product operation and the Khatri-Rao sum operation on adjacency matrices. In addition, the marginal-and joint-node degrees are introduced to investigate the mechanism of a supernetwork. The Khatri-Rao product operation is iteratively applied to a simple initial network to form the adjacent supernetwork matrix and obtain a self-similarity supernetwork with fractal dimensions of no longer than 3. If all initial networks are connected with nonbipartite graphs, the obtained supernetwork has a diameter that does not exceed twice the summation of all initial networks. Furthermore, the Khatri-Rao sum operation is sequentially applied to multiple simple initial networks to form adjacency matrices of supernetwork and obtain a random supernetwork with one marginal node degree, with one-dimensional Gaussian distribution, and a joint node degree, with a high-dimensional Gaussian distribution. Finally, several properties of the proposed supernetwork building based on matrix operation are presented. Keywords: matrix operation; complex network; supernetwork; model building; fractal dimension; self-similarity supernetwork; random supernetwork; property analysis 复杂网络可较好地描述并刻画复杂系统，对其 系统性研究起源于 20 世纪 Erdos 与 Renyi 二者合 收稿日期：2017−06−14. 网络出版日期：2018−04−12. 基金项目：国家自然科学基金项目 (61573292，61262058). 通信作者：李天瑞. E-mail：trli@swjtu.edu.cn. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
·360· 智能系统学报 第13卷 作提出的ER随机网络模型。一些相近的其他模 定义5超网络的边际度分布多项式是指超网 型，包括WSNW小世界网络模型2-及BA无标度 络中各层网络以节点度为次数、以节点度频数为系 网络模型等同类别其他复杂网络模型相继提出。 数的各个单项式构成的多项式。 小世界特性与无标度特性被称为复杂网络两 根据定义1~5，可对超网络联合度、联合度分 大特性，对它们进行分析也成为复杂网络的研究热 布与联合度分布多项式进行定义。 点5。近几年，自相似特性成为复杂网络新的研究 以n=2时，2个节点数目相同的网络Ga与G2构 热点。小世界网络模型、无标度网络模型与自相 成的最简单超网络S为例，超网络S的边际度分布多 似网络模型的各种改进是复杂网络的重点研究内 项式与联合度分布多项式为 容。同时，采用矩阵运算对复杂网络进行构建与 分析已得到一定的研究与应用。 Polyd(S)= 真实世界中，通常意义上的网络或图并不能对 实际网络的所有特性进行刻画。对超大规模网络系 Poly (S)=>) (3) 统进行研究，往往会出现网络中有网络，即超网络 等问题。超网络的特性和传统复杂网络的特性有很 Poly (S)=xyren) 大差异。对超网络的分析仍处于初始阶段，并 定义6 超网络的密度是指超网络S中边数与 没有形成公认的超网络的定义。本文主要对层次形 最多可能边数的比值，记为Density(S),则有 态的Supernetwork型超网络进行分析研究。 当前，人们仍在积极探寻借助全新的分析理论 2∑lEl N 及研究策略对超网络进行研究。本文尝试根据邻接 Density(S)= Density(G) 矩阵来分析研究超网络，借助矩阵运算生成不同类 Voldvl-1) 型的超网络，即根据简单初始图序列得到超网络邻 (4) 接矩阵的迭代Khatri-Rao积运算操作生成自相似超 1.2 分形理论 网络，同时根据多个简单初始图序列得到超网络邻 分形几何为分形理论数学基础，并进而发展到 接矩阵的Khatri-Rao和运算操作生成随机超网络， 分形图案等分形方面的多个研究应用领域。 并对二者的特性进行深入的分析研究。 定义分形矩阵是由迭代相加生成的一簇 具备分形性质的矩阵。 1预备知识 图案生成是分形矩阵最初应用领域。对于矩 1.1超网络 阵Amm,用A的各元素a(1≤i≤m,1≤j≤nm)与A 对任意图序列G,G2,…,G,…,Gm,其中G0= 的各元素进行相加，再用生成的新矩阵更换，生成 (Vo,Eo)(1≤i≤n)是一个无向无环无权无重边简单 局部和整体自相似的一个新矩阵。若一直将上述操 图，而且Vo=(wa1,a2,…,a…)(1≤jVa人Eo=(eo1, 作延续下去，则会生成自相似的一簇新矩阵： eo2…,ek,…1≤k≤Eo分别是Go中的节点集及 Amxm,A②mxm,A③mm,…,其中A4X:都是由 边集，且EC Vi×Vo,n表示图序列长度，Vo及 Amx:的各元素与A进行相加后更换而生成的。 Eo分别表示G。中节点数目及边数目。 分形矩阵就是上述更换操作生成的一簇新矩阵 定义1超网络是指由图序列G,G2,…,G0,…, Amxm,A②m,Amx,…文献[16中，分形矩阵同 样可以根据迭代Kronecker积运算而得到。本文在 Gm构成且对应节点序列va'2…,V…,ay相互 关联的层次形态的网络，记为S,表述为 超网络邻接矩阵中引入矩阵运算。 S={G,G2,…,Ga,…,Gm} (1) 1.3矩阵理论 定义2超网络的邻接矩阵A(S)是指由构成超 对图来说，其邻接矩阵的每列或每行代表一节 网络S的图序列邻接矩阵构成的分块矩阵，即 点，图序列间通过节点之间相互的关联生成的超网 A(S)=[A(G)A(G2)…A(Ga)…A(Gam】(2) 络可用图序列邻接矩阵构成的分块矩阵进行刻画， 定义3超网络的边际度是指超网络各层网络 而且分块矩阵中的每一个分块都是一个图的邻接矩 的节点度。 阵。对分块矩阵形式超网络的邻接矩阵进行分析研 定义4超网络的边际度分布是指超网络中各 究，基于Kronecker积运算、Kronecker和运算有 层网络节点度的分布，包括概率分布及频率分布。 Khatri-Rao积运算、Khatri-Rao和运算
作提出的 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(i)2,··· , e(i)k ,···)(1 ⩽ k ⩽ E(i) ) G(i) E(i) ⊆ V(i) ×V(i) n V(i) E(i) G(i) 对任意图序列 ，其中 是一个无向无环无权无重边简单 图，而且 、 分别是 中的节点集及 边集，且 ， 表示图序列长度， 及 分别表示 中节点数目及边数目。 G(1),G(2),··· ,G(i) ,··· , G(n) v(1)j , v(2)j ,··· , v(i)j ,··· , v(n)j S 定义 1 超网络是指由图序列 构成且对应节点序列 相互 关联的层次形态的网络，记为 ，表述为 S = { G(1),G(2),··· ,G(i) ,··· ,G(n) } (1) A(S ) S 定义 2 超网络的邻接矩阵 是指由构成超 网络 的图序列邻接矩阵构成的分块矩阵，即 A(S ) = [ A(G(1)) A(G(2)) ··· A(G(i)) ··· A(G(n)) ] (2) 定义 3 超网络的边际度是指超网络各层网络 的节点度。 定义 4 超网络的边际度分布是指超网络中各 层网络节点度的分布，包括概率分布及频率分布。 定义 5 超网络的边际度分布多项式是指超网 络中各层网络以节点度为次数、以节点度频数为系 数的各个单项式构成的多项式。 根据定义 1～5，可对超网络联合度、联合度分 布与联合度分布多项式进行定义。 n = 2 G(1) G(2) S S 以 时，2 个节点数目相同的网络 与 构 成的最简单超网络 为例，超网络 的边际度分布多 项式与联合度分布多项式为 PolyM(1)(S ) = ∑ |V(1)| i=1 x d(v(1)i ) PolyM(2)(S ) = ∑ |V(2)| i=1 y d(v(2)i ) PolyJ (S ) = ∑ |V| i=1 x d(v(1)i ) y d(v(2)i ) . (3) S (S ) 定义 6 超网络的密度是指超网络 中边数与 最多可能边数的比值，记为 Density ，则有 Density(S ) = 2 ∑N i=1 E(i) ∑N i=1 V(i) ( V(i) −1) = 1 N ∑N i=1 Density(G(i)) (4) 1.2 分形理论 分形几何为分形理论数学基础，并进而发展到 分形图案等分形方面的多个研究应用领域[13]。 定义 7 [14] 分形矩阵是由迭代相加生成的一簇 具备分形性质的矩阵。 Am×n A ai j(1 ⩽ i ⩽ m,1 ⩽ j ⩽ n) A ai j A (1) m2×n 2 A (2) m3×n 3 A (3) m4×n 4 A (i+1) mi+2×n i+2 A (i) mi+1×n i+1 A A (1) m2×n 2 A (2) m3×n 3 A (3) m4×n 4 ,··· 图案生成是分形矩阵最初应用领域[15]。对于矩 阵 ， 用 的各元素 与 的各元素进行相加，再用生成的新矩阵更换 ，生成 局部和整体自相似的一个新矩阵。若一直将上述操 作延续下去，则会生成自相似的一簇新矩阵： ， ， ，…，其中 都是由 的各元素与 进行相加后更换而生成的。 分形矩阵就是上述更换操作生成的一簇新矩阵 ， ， 文献[16]中，分形矩阵同 样可以根据迭代 Kronecker 积运算而得到。本文在 超网络邻接矩阵中引入矩阵运算。 1.3 矩阵理论 对图来说，其邻接矩阵的每列或每行代表一节 点，图序列间通过节点之间相互的关联生成的超网 络可用图序列邻接矩阵构成的分块矩阵进行刻画， 而且分块矩阵中的每一个分块都是一个图的邻接矩 阵。对分块矩阵形式超网络的邻接矩阵进行分析研 究，基于 Kronecker 积运算、Kronecker 和运算有 Khatri-Rao 积运算、Khatri-Rao 和运算。 ·360· 智 能 系 统 学 报 第 13 卷
第3期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·361· A与B的Khatri-Rao积运算可表示为 与次数之间的相乘。定理1得证。 A*B=(A⑧B) (5) 超网络邻接矩阵Khatri-Rao积运算过程中，各 A与B的Khatri-Rao和运算18可表示为 分块矩阵Kronecker积运算相互独立，定理1涉及 AVB=A*I+I*B (6) 的超网络边际度分布多项式的规律可应用到联合度 2基于矩阵运算超网络模型 分布多项式中，则有引理1。 引理1超网络迭代Khatri-Rao积超网络联合 2.1自相似超网络模型 度分布多项式可对联合度分布多项式进行系数相乘 对于一个节点数目相同图序列的邻接矩阵构成 且次数相乘得到。 的分块矩阵A,分别用A的各分块矩阵与自身相乘 证明分块矩阵Khatri-Rao积运算操作中，各 生成的矩阵去更换自身，会生成局部与整体自相似 分块矩阵Kronecker积运算相互独立，则可进行组 的一个新矩阵，将此操作不断延续下去，可以生成 合。各分块矩阵Kronecker积运算结果可通过边际 自相似的一簇新矩阵。这些新矩阵可看成邻接矩 度分布多项式系数相乘且次数相乘得到，则分块矩 阵，对应超网络即为A迭代Khatri-Rao积运算的结 阵Khatri-Rao积运算结果同样可根据联合度分布多 果，也就是自相似超网铬。 项式系数相乘及次数相乘操作获取。引理1得证。 在文献[I8]中，Liu研究了Khatri-Rao积运算的 分形理论方面，论证一图形是分形图形的实质 些特性。此处，将超网络对应的邻接矩阵看成各 是计算其分形维数。本文通过对自相似超网络进行 个图邻接矩阵构成的分块矩阵，则其Khatri-Rao积 研究，计算出此类自相似超网络分形维数。 运算的结果就是各个图邻接矩阵Kronecker积运算 定理2超网络迭代Khatri-Rao积运算生成自 所得到的结果。 相似超网络分形维数表述为生成此超网络各自相似 对超网络来说，其邻接矩阵中，各分块矩阵的 网络分形维数几何平均值与1之和，即 列数或行数代表此层网络节点数目，分块矩阵的数 目代表超网络的层数，超网络密度为各层中网络密 og22 E0 FD(S) log,Vol (9) 度的算术平均值，于是有 Vo =Vo 证明 文献[9]中，迭代Kronecker积图的自相 Eu=2E 似网络分形维数表述为图边数两倍对数值与节点数 (7) 对数值之比。自相似超网络方面，其分形维数体现 Density(S)= N i=l 为自相似网络分形维数的融合，由于其层次形态的 S可简记为 特征，根据余维相加定律，故为各自相似网络的分 S0=0S (8) 形维数几何平均值与1之和。定理2得证。 超网络边际度分布多项式与联合度分布多项式 定理3超网铬迭代Khatri-Rao积运算生成自 都将节点度看成单项式次数。直接对初始超网络边 相似超网络分形维数一定不会超过3。 际度分布多项式与联合度分布多项式进行计算可得 证明自相似网络分形维数一定不会超过2， 到超网络迭代Khatri-.Rao积运算的边际度分布多项 式(9)中有 式与联合度分布多项式，则有定理1。 定理1超网络迭代Khatri--Rao积超网络的边 FD(G) (10) 际度分布多项式可对边际度分布多项式进行系数相 显然，定理3成立。定理3得证。 乘且次数相乘得到。 通常情况下，只对连通且非二分图序列的迭代 证明分块矩阵迭代Khatri--Rao积运算等同于 Khatri-Rao积运算生成的超网络进行研究，基于定 对分块矩阵的各分块进行迭代Kronecker积运算操 理3，则有引理2。 作，而超网络边际度分布多项式就是各分块对应网 引理2连通且非二分图序列迭代Khatri- 络的度分布多项式。Kronecker积运算为两个矩阵 Rao积运算生成超网络分形维数在2~3之间。 的各行分别进行相乘运算，生成的结果矩阵中各行 证明对连通且非二分图Go而言，有Eo≥ 非零元素的数目就是节点所对应的边际度。可将矩 阵各行非零元素数目看成单项式次数，通过超网络 Vo-1≥2，则有 边际度分布多项式对超网络边际度分布进行处理 10g22 E 10g22(Vio-1) FD(G)= >1 (11) 时，行之间的相乘在边际度分布多项式中就是次数 log2 Vol log2 Vo
A 与 B 的 Khatri-Rao 积运算[17]可表示为 A∗ B = ( Ai j ⊗ Bi j) i j (5) A 与 B 的 Khatri-Rao 和运算[18]可表示为 A∇B = A∗ I+ I ∗ B (6) 2 基于矩阵运算超网络模型 2.1 自相似超网络模型 对于一个节点数目相同图序列的邻接矩阵构成 的分块矩阵 A，分别用 A 的各分块矩阵与自身相乘 生成的矩阵去更换自身，会生成局部与整体自相似 的一个新矩阵，将此操作不断延续下去，可以生成 自相似的一簇新矩阵。这些新矩阵可看成邻接矩 阵，对应超网络即为 A 迭代 Khatri-Rao 积运算的结 果，也就是自相似超网络。 在文献[18]中，Liu 研究了 Khatri-Rao 积运算的 一些特性。此处，将超网络对应的邻接矩阵看成各 个图邻接矩阵构成的分块矩阵，则其 Khatri-Rao 积 运算的结果就是各个图邻接矩阵 Kronecker 积运算 所得到的结果。 对超网络来说，其邻接矩阵中，各分块矩阵的 列数或行数代表此层网络节点数目，分块矩阵的数 目代表超网络的层数，超网络密度为各层中网络密 度的算术平均值，于是有 V(i) (k) = V(i) k+1 E(i) (k) = 2 k E(i) k+1 Density(S (k) ) = 1 N ∑N i=1 Density(G(i) (k) ) (7) S (k) 可简记为 S (i) = ∗(i) S (8) 超网络边际度分布多项式与联合度分布多项式 都将节点度看成单项式次数。直接对初始超网络边 际度分布多项式与联合度分布多项式进行计算可得 到超网络迭代 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 之和，即 FD(S ) = 1+ ∏n i=1 FD(G(i)) 1 n = 1+ ∏n i=1 log22 E(i) log2 V(i) 1 n (9) 证明 文献[9]中，迭代 Kronecker 积图的自相 似网络分形维数表述为图边数两倍对数值与节点数 对数值之比。自相似超网络方面，其分形维数体现 为自相似网络分形维数的融合，由于其层次形态的 特征，根据余维相加定律[19] ，故为各自相似网络的分 形维数几何平均值与 1 之和。定理 2 得证。 定理 3 超网络迭代 Khatri-Rao 积运算生成自 相似超网络分形维数一定不会超过 3。 证明 自相似网络分形维数一定不会超过 2， 式 (9) 中有 ∏N i=1 FD(G(i)) 1 N 1 (11) 第 3 期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·361·
·362· 智能系统学报 第13卷 式(9)中有 表1自相似超网络与门格海绵对比表 Table 1 Comparison between self-similarity supernet- FD(Gd) (12) work and Menger sponge 结合定理3，有2<FDS)<3。引理2得证。 维数 门格海绵 自相似超网络 同时，通过超网络分块矩阵形式邻接矩阵迭代 imTa→0 lim Density(So→0 Khatri--Rao积运算生成的矩阵一样为分块矩阵，对 imLa→o mlo→o 此进行研究，可得到定理4。 m,→o limE 定理4连通且非二分图序列迭代Khatri-Rao iSn→o 1 im D(G≤2DGo） 积运算生成超网络直径不超过初始图直径和的两倍。 证明文献[9]中，连通且非二分图邻接矩阵迭 1og220 分形维数 1og23 代Kronecker积运算生成Kronecker积图直径不超 log2 Vo 过初始图直径两倍。设构成超网络任一图G直径 3 m→0 lim D(S())D(G) 为do,于是自相似超网络任意一层网络中的任意 2.2随机超网络模型 个节点均可在不超过2∑d步内抵达任意一层网 基于矩阵运算随机超网络构建方法为：对于一 络中的任意一个节点。定理4得证。 簇随机选取初始超网络Su,Sa…,Sa,,将Khatri- 根据定理4，计算超网络直径时，通过初始图直 Rao和运算顺次应用于此超网络对应邻接矩阵，可 径可较为便捷得到所生成的自相似超网络直径。进 得到一个新矩阵，其对应超网络就是随机超网络。 步，有引理3。 超网络S。及Sb对应边际节点度分布多项式 引理3N个完全图且非二分图序列迭代 Poly(Sa)、Poly(Sb)中，将Khatri-Rao积运算应 Khatri-Rao积运算生成超网络直径为2W。 用于S.及S6对应邻接矩阵生成超网络Sb的边际节 证明对完全图且非二分图来说，其迭代Kro 点度分布可通过Poly(S.)与Poly(S)的Khatri- necker积图直径为2，完全图且非二分图序列迭代 Rao积运算而得到，即 Khatri-Rao积运算生成超网络各层直径均为2，此 N层超网络直径即为2W。引理3得证。 Poly(Sab】 (14) 与定理4相似，引理3同样只在由连通且非二 类似地，将Khatri-Rao和运算应用于S.及S,对 分图序列生成超网络情形下成立。 应邻接矩阵生成超网络S的边际节点度分布可通 为更清晰论述自相似超网络不同维度的特性， 过式(15)得到： 将连通且非二分图序列迭代Khatri-Rao积运算生成 Vanl Viol 自相似超网络与门格海绵2进行比较，门格海绵分 Poly(S)= drew+dre） (15) 1=1 形维数同样在2~3之间。 门格海绵中，设初始情况下正方体棱长T。=1, 式(I5)为通常意义上多项式乘法。对Khatri- Rao积采用系数相乘且次数相乘，类似地，对Khatri- 正方体数量No=1,周长Lo=12,表面积S。=6,体积 Rao和采用系数相乘且次数相加可得到新超网络边 Vo=l,Tm、Nn、Ln、Sn和Vn分别为第n步迭代后生成门 际度分布。将两个超网络Khatri-Rao积运算边际度 格海绵正方体的棱长、数量、周长、表面积及体积， 分布看成初始超网络边际节点度分布的非线性组 则可以得到： 合，同理，可将两个超网络Khatri-Rao和运算结果 1 limT=lim →0 边际度分布看成初始超网络边际节点度分布的线性 3 To=lim lim N.lim 20No lim 20oo 组合。随机选取的初始超网络，其边际度分布服从 高斯分布，鉴于有限个高斯分布的线性组合同样是 6/201 11 +7 (13) 高斯分布，通过多个初始超网络Khatri-Rao和运算 4 22+】 所得到超网络的边际度分布同样服从高斯分布。 lim S=lim 3 So=lim →00 +w3n- 与此类似，对超网络联合度分布进行分析也可 20 得到与边际度分布相近的结论。 lim V lim 27 V%→0 初始超网络集合{S,S2…,S…}中，对顺次 自相似超网络与门格海绵对比如表1所示。 选取Sa且通过Khatri-Rao和运算生成超网络Sm来
式 (9) 中有 ∏N i=1 FD(G(i)) 1 N > 1 (12) 结合定理 3，有 2 < FD(S ) < 3 。引理 2 得证。 同时，通过超网络分块矩阵形式邻接矩阵迭代 Khatri-Rao 积运算生成的矩阵一样为分块矩阵，对 此进行研究，可得到定理 4。 定理 4 连通且非二分图序列迭代 Khatri-Rao 积运算生成超网络直径不超过初始图直径和的两倍。 G(i) d(i) ∑N i=1 d(i) 证明 文献[9]中，连通且非二分图邻接矩阵迭 代 Kronecker 积运算生成 Kronecker 积图直径不超 过初始图直径两倍。设构成超网络任一图 直径 为 ，于是自相似超网络任意一层网络中的任意一 个节点均可在不超过 2 步内抵达任意一层网 络中的任意一个节点。定理 4 得证。 根据定理 4，计算超网络直径时，通过初始图直 径可较为便捷得到所生成的自相似超网络直径。进 一步，有引理 3。 N 2N 引理 3 个完全图且非二分图序列迭代 Khatri-Rao 积运算生成超网络直径为 。 N 2N 证明 对完全图且非二分图来说，其迭代 Kronecker 积图直径为 2，完全图且非二分图序列迭代 Khatri-Rao 积运算生成超网络各层直径均为 2，此 层超网络直径即为 。引理 3 得证。 与定理 4 相似，引理 3 同样只在由连通且非二 分图序列生成超网络情形下成立。 为更清晰论述自相似超网络不同维度的特性， 将连通且非二分图序列迭代 Khatri-Rao 积运算生成 自相似超网络与门格海绵[20]进行比较，门格海绵分 形维数同样在 2～3 之间。 T0 = 1 N0 = 1 L0 = 12 S 0 = 6 V0 = 1 Tn Nn Ln S n Vn n 门格海绵中，设初始情况下正方体棱长 ， 正方体数量 ，周长 ，表面积 ，体积 ， 、 、 、 和 分别为第 步迭代后生成门 格海绵正方体的棱长、数量、周长、表面积及体积， 则可以得到： lim n→∞ Tn = lim n→∞ ( 1 3 )n T0 = lim n→∞ 1 3 n → 0 lim n→∞ Nn = lim n→∞ 20nN0 = lim n→∞ 20n → ∞ lim n→∞ Ln = lim n→∞ 12[ 6 17( 20 3 )n + 11 17] → ∞ lim n→∞ S n = lim n→∞ ( 4 3 )n S 0 = lim n→∞ 2 2n+1 3 n−1 → ∞ lim n→∞ Vn = lim n→∞ ( 20 27)n V0 → 0 (13) 自相似超网络与门格海绵对比如表 1 所示。 2.2 随机超网络模型 S (1),S (2),··· ,S (i) ,··· 基于矩阵运算随机超网络构建方法为：对于一 簇随机选取初始超网络 ，将 KhatriRao 和运算顺次应用于此超网络对应邻接矩阵，可 得到一个新矩阵，其对应超网络就是随机超网络。 S a S b PolyM(i) (S a) PolyM(i) (S b) S a S b S ab PolyM(i) (S a) PolyM(i) (S b) 超网络 及 对应边际节点度分布多项式 、 中，将 Khatri-Rao 积运算应 用于 及 对应邻接矩阵生成超网络 的边际节 点度分布可通过 与 的 KhatriRao 积运算而得到，即 PolyM(i) (S ab) = | ∑Va(i)| j=1 | ∑Vb(i)| k=1 x d(v(a)j)×d(v(b)k ) (14) S a S b S ′ ab 类似地，将 Khatri-Rao 和运算应用于 及 对 应邻接矩阵生成超网络 的边际节点度分布可通 过式 (15) 得到： PolyM(i) (S ′ ab) = | ∑Va(i)| j=1 | ∑Vb(i)| k=1 x d(v(a)j)+d(v(b)k ) (15) 式 (15) 为通常意义上多项式乘法。对 KhatriRao 积采用系数相乘且次数相乘，类似地，对 KhatriRao 和采用系数相乘且次数相加可得到新超网络边 际度分布。将两个超网络 Khatri-Rao 积运算边际度 分布看成初始超网络边际节点度分布的非线性组 合，同理，可将两个超网络 Khatri-Rao 和运算结果 边际度分布看成初始超网络边际节点度分布的线性 组合。随机选取的初始超网络，其边际度分布服从 高斯分布，鉴于有限个高斯分布的线性组合同样是 高斯分布，通过多个初始超网络 Khatri-Rao 和运算 所得到超网络的边际度分布同样服从高斯分布。 与此类似，对超网络联合度分布进行分析也可 得到与边际度分布相近的结论。 { S (1),S (2),··· ,S (i) ,···} S (i) S (n) 初始超网络集合 中，对顺次 选取 且通过 Khatri-Rao 和运算生成超网络 来 表 1 自相似超网络与门格海绵对比表 Table 1 Comparison between self-similarity supernetwork and Menger sponge 维数 门格海绵 自相似超网络 1 lim n→∞ Tn → 0 lim i→∞ Density(S (i) ) → 0 lim n→∞ Ln → ∞ lim n→∞ Nn → ∞ lim j→∞ V(i) (j) → ∞ lim j→∞ E(i) (j) → ∞ 2 lim n→∞ S n → ∞ lim n→∞ D(G(i) (n) ) ⩽ 2D(G(i)) 分形维数 log2 20 log2 3 1+ ∏n j=1 log2 2 E(i) j log2 V(i) j 1 n 3 lim n→∞ Vn → 0 lim n→∞ D(S (i) ) ⩽ 2 ∑n i=1 D(G(i)) ·362· 智 能 系 统 学 报 第 13 卷
第3期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·363· 说，其各层网络节点数目、边数目及密度可根据边 表29类超网络统计表 际度分布多项式的分析研究得到： Table 2 Statistics of9 supernetworks Ivol=I=ΠPoly(G 编号 数量 运算 类型 Khatri-.Rao积运算 自相似超网络 .(s. 2 Khatri--Rao和运算 2 Eo Khatri-Rao积运算 Density(S()= IVI(V-1) Khatri-Rao和运算 (16) Khatri--Rao积运算 Sm可简记为 Khatri--Rao和运算 随机超网络 Sm=又Sa (17) Khatri--Rao积运算 2.3不同组合超网络模型 6 Khatri--Rao和运算 拓展上文中超网络生成方法，可得出一般情形 Khatri-Rao积运算 下基于矩阵运算超网络生成方法。通过一个、有限 Khatri-Rao和运算 多个，乃至无限多个超网络Khatri--Rao积运算和/ 尚不明确 或Khatri-Rao和运算，可得到9类超网络模型，如 Khatri--Rao积运算 表2所示，9类超网络相互之间的关系如图1所示。 Khatri-Rao和运算 1个超网路 r个超网络 0个超网络 Khatri-Rao积运算 Khatri-Rao积运算 Khatri-Rao积运算 1个超网络 个超网络 o0个超网络 Khatri-Rao和运算 Khatri-Rao和运算 Khatri-.Rao和运算 1个超网络 n个超网络 D个超网络 Khatri-Rao积运算 Khatri-Rao积运算 Khatri-Rao积运算 Khatri-.Rao和运算 Khatri--Rao和运算 Khatri-Rao和运算 图19类超网络关系图 Fig.1 Diagram of9 supernetworks 3基于矩阵运算超网络模型理论分析 的关联与耦合等特征，对联合度分布欠缺必要的应 对策略。对联合度分布相同超网络数量及边际度分 3.1基于矩阵运算超网络数量 布与联合度分布都相同超网络数量的分析有待进一 边际度分布多项式与联合度分布多项式均无法 步深人研究。 反映超网络拓扑结构等特性，相同边际度分布多项 式与联合度分布多项式可能对应不同超网络。 3.2基于矩阵运算超网络敏感性 定理5边际度分布相同超网络数量为各边际 超网络敏感性分析主要对初始超网络波动对基 度分布对应网络数量的乘积，即 于矩阵运算生成超网络的干扰进行研究。本文主要 分析对超网络直径、分形维数和度分布的影响。 Num(Poly(5))=Num(Poly(S)).(i=1.2...n) 定理6增添一个节点与至少一条边到构成自 (18) 相似超网络的任意一个初始图后，自相似超网络直 证明层超网络中，仅分析边际度分布，各层 径增加量不超过2。 网络度分布相互独立，层超网络数量等于各层相互 证明增添一个节点与至少一条边到构成自相 独立网络数量之乘积。定理5得证。 似超网络任一初始图，初始图节点间最短距离不 定理5仅研究边际度分布相同超网络数量，不 变，而初始图原节点到新增节点距离不超过原始图 涉及联合度分布。因联合度分布涉及各层网络之间 直径加1，故超网络直径增量不超过2。定理6得证
说，其各层网络节点数目、边数目及密度可根据边 际度分布多项式的分析研究得到： V(i) (n) = ∏n j=1 V(j)i = ∏n i=1 Poly(G(i)) x=1 E(i) (n) = 1 2 Poly′ M(i) (S (n) ) x=0 = ∑n j=1 E(j)i ∏k=n k=1, k,j V(k)i Density(S (i) (n) ) = 2 E(i) (n) |V(n) |( V(i) (n) −1) (16) S (n) 可简记为 S (n) = n ∇ i=1 S (i) (17) 2.3 不同组合超网络模型 拓展上文中超网络生成方法，可得出一般情形 下基于矩阵运算超网络生成方法。通过一个、有限 多个，乃至无限多个超网络 Khatri-Rao 积运算和/ 或 Khatri-Rao 和运算，可得到 9 类超网络模型，如 表 2 所示，9 类超网络相互之间的关系如图 1 所示。 3 基于矩阵运算超网络模型理论分析 3.1 基于矩阵运算超网络数量 边际度分布多项式与联合度分布多项式均无法 反映超网络拓扑结构等特性，相同边际度分布多项 式与联合度分布多项式可能对应不同超网络。 定理 5 边际度分布相同超网络数量为各边际 度分布对应网络数量的乘积，即 Num( PolyM(i) (S ) ) = ∏n j=1 Num( PolyM(j) (S ) ) ,(i = 1,2,··· ,n) (18) n n 证明 层超网络中，仅分析边际度分布，各层 网络度分布相互独立， 层超网络数量等于各层相互 独立网络数量之乘积。定理 5 得证。 定理 5 仅研究边际度分布相同超网络数量，不 涉及联合度分布。因联合度分布涉及各层网络之间 的关联与耦合等特征，对联合度分布欠缺必要的应 对策略。对联合度分布相同超网络数量及边际度分 布与联合度分布都相同超网络数量的分析有待进一 步深入研究。 3.2 基于矩阵运算超网络敏感性 超网络敏感性分析主要对初始超网络波动对基 于矩阵运算生成超网络的干扰进行研究。本文主要 分析对超网络直径、分形维数和度分布的影响。 定理 6 增添一个节点与至少一条边到构成自 相似超网络的任意一个初始图后，自相似超网络直 径增加量不超过 2。 证明 增添一个节点与至少一条边到构成自相 似超网络任一初始图，初始图节点间最短距离不 变，而初始图原节点到新增节点距离不超过原始图 直径加 1，故超网络直径增量不超过 2。定理 6 得证。 表 2 9 类超网络统计表 Table 2 Statistics of 9 supernetworks 编号 数量 运算 类型 1 1 Khatri-Rao 积运算 自相似超网络 2 Khatri-Rao 和运算 — 3 Khatri-Rao 积运算 — Khatri-Rao 和运算 4 n Khatri-Rao 积运算 — 5 Khatri-Rao 和运算 随机超网络 6 Khatri-Rao 积运算 — Khatri-Rao 和运算 7 ∞ Khatri-Rao 积运算 尚不明确 8 Khatri-Rao 和运算 9 Khatri-Rao 积运算 Khatri-Rao 和运算 1个超网络 Khatri-Rao积运算 n个超网络 Khatri-Rao积运算 ∞个超网络 Khatri-Rao积运算 1个超网络 Khatri-Rao和运算 n个超网络 Khatri-Rao和运算 ∞个超网络 Khatri-Rao和运算 1个超网络 Khatri-Rao积运算 Khatri-Rao和运算 n个超网络 Khatri-Rao积运算 Khatri-Rao和运算 ∞个超网络 Khatri-Rao积运算 Khatri-Rao和运算 图 1 9 类超网络关系图 Fig. 1 Diagram of 9 supernetworks 第 3 期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·363·
·364· 智能系统学报 第13卷 定理7增添一条边到构成自相似超网络任意 从式(22)中可以看出，增添或去掉一个节点或 一个初始图后，自相似超网络直径减少量不超过该 条边后，可用微分公式来增量式更新，即可微，也 初始图直径。 即不敏感。所以初始情形下，尽管选取不同图但生 证明增添一条边到构成自相似超网络任一初 成随机超网络度分布形态近似相同，均呈钟形高斯分 始图，因增添边连接的节点为原图中不邻接的两节 布。分析随机超网络联合度分布，可得出相似结论。 点，致使原图会增多至少一个回路，而此回路上任 引入微积分等理论与技术，在超网络敏感性分 意一对节点间隔不超过回路长度的半数，所以此图 析方面有一些量化结论，但对超网络敏感性根源仍 直径为超网络直径减少量的上限。定理7得证。 未完全透彻了解，后续研究中，重点在于继续使用 式(9)为基于初始超网络生成自相似超网络分 微分方程等工具，对超网络敏感性进行深人研究。 形维数，分析增添或去掉生成超网络初始图一个节 点与一条边对超网络分形维数的影响就是对其分形 4结束语 维数一阶导数进行分析。不失一般性，对G及G生 成的2层超网络S分形维数的一阶导数进行分析： 本文主要对自相似超网络与随机超网络等通过 矩阵运算生成超网络进行分析，通过超网络的邻接 dFD(S)-(FD(G.FD(G 矩阵迭代Khatri-.Rao积运算可生成自相似超网络， FD(G)dFD(G +FD(G)dFD(G.) (19) 自相似特性在于其邻接矩阵为分形矩阵，连通且非 dx dy 二分图序列构成自相似超网络同时有小世界特性， 任一图G中，文献[9]中有如下结论： 在与门格海绵的对比中，阐明了自相似超网络的各 dFD(G)l1= Poly"(G)IVllog2 IVI-4EP'log2 2IEl 项性质。多个超网络邻接矩阵Khatri--Rao和运算可 2 VllogVⅥ 生成随机超网络，随机特性在于有限个高斯分布的 (20) 式(20)中，分形维数和度分布多项式二阶导数 线性组合。通过边际度分布多项式及联合度分布多 联系紧密。这说明，在增添或去掉节点或者边时， 项式可计算出基于矩阵运算生成的超网络边际度分 可对度分布多项式进行计算，进而得到分形维数的 布与联合度分布等特性。此外，对超网络数量及敏 波动情况。此研究可拓展到任意层次超网络。 感性等进行一定程度的量化分析。 分析自相似超网络边际度分布敏感性，具体方 参考文献： 面，是对边际度分布多项式采用系数相乘，次数也 相乘的操作。式(19)中，对边际度分布多项式进行 [1]ERDOS P,RENYI A.On random graphs I.[J].Publica- 分析，可得到： tiones mathematicae,1959,6:290-297. dPolya(Sab) [2]WATTS D J.STROGATZ S H.Collective dynamics of 1 small-world'networks[J].Nature,1998,393(6684): 1=0 Vaol IVool 21) 440-442 (da）×d(vbt)！ x(xd(v I(dva)xdvb)-0!士 [3]NEWMAN M E J,WATTS D J.Renormalization group analysis of the small-world network model[J].Physics let- 通过式(21)可以发现，增添或去掉一个节点或 ters A.1999.293(4/5/6:341-346. 一条边后，不能用微分公式来增量式更新，即不可 [4]BARABASI A L,ALBERT R.Emergence of scaling in ran- 微，也即敏感。所以，初始情形下，增添或去掉一个 dom networks[J].Science,1999,286(5439):509-512 节点或一条边的微弱差异将伴随迭代次数的增加而 [5]BARABASI A L,RAVASZ E,VICSEK T.Deterministic 因为连锁反应无限放大。分析自相似超网络联合度 scale-free networks[J].Physica A:statistical mechanics and 分布，可得出相似结论。 its applications,2001,299(3/4):559-564. 继续分析随机超网络敏感性，具体而言，是分 [6]COMELLAS F,SAMPELS M.Deterministic small-world 析随机超网络边际度分布敏感性。随机超网络中， networks[J].Physica A:statistical mechanics and its applic- 是将边际节点度分布多项式进行系数相乘且次数相 ations,2002,309(1/2):231-235 加。式(19)中，对边际度分布多项式进行分析，可得 [7]SONG Chaoming,HAVLIN S,MAKSE H A.Self-similar- d'Poly(Sab) ity of complex networks[J].Nature,2005,433(7024): 分 392-395. 22 [8]张嗣瀛.复杂系统、复杂网络自相似结构的涌现规律叮 (dva）+dvbt)！ 复杂系统与复杂性科学，2006,3(4)：41-51. (dva+dvbt)-0台日 ZHANG Siying.The law of emergence of self-similar struc-
定理 7 增添一条边到构成自相似超网络任意 一个初始图后，自相似超网络直径减少量不超过该 初始图直径。 证明 增添一条边到构成自相似超网络任一初 始图，因增添边连接的节点为原图中不邻接的两节 点，致使原图会增多至少一个回路，而此回路上任 意一对节点间隔不超过回路长度的半数，所以此图 直径为超网络直径减少量的上限。定理 7 得证。 Ga Gb S ab 式 (9) 为基于初始超网络生成自相似超网络分 形维数，分析增添或去掉生成超网络初始图一个节 点与一条边对超网络分形维数的影响就是对其分形 维数一阶导数进行分析。不失一般性，对 及 生 成的 2 层超网络 分形维数的一阶导数进行分析： dFD(S ab) = 1 n (FD(Ga)FD(Gb)) 1 n −1 . ( FD(Gb) dFD(Ga) dx +FD(Ga) dFD(Gb) dy ) (19) 任一图 G 中，文献[9]中有如下结论： dFD(G)| x=1 = Poly′′(G) x=1 |V|log2 |V|−4|E| 2 log2 2|E| 2|E| |V|log2 2 |V| (20) 式 (20) 中，分形维数和度分布多项式二阶导数 联系紧密。这说明，在增添或去掉节点或者边时， 可对度分布多项式进行计算，进而得到分形维数的 波动情况。此研究可拓展到任意层次超网络。 分析自相似超网络边际度分布敏感性，具体方 面，是对边际度分布多项式采用系数相乘，次数也 相乘的操作。式 (19) 中，对边际度分布多项式进行 分析，可得到： d lPolyM(i) (S ab) l! x=0 = ( d(v(a)j)×d(v(b)k) ) ! l! ( d(v(a)j)×d(v(b)k)−l ) ! | ∑Va(i)| j=1 | ∑Vb(i)| k=1 x d(v(a)j)×d(v(b)k ) x=0 (21) 通过式 (21) 可以发现，增添或去掉一个节点或 一条边后，不能用微分公式来增量式更新，即不可 微，也即敏感。所以，初始情形下，增添或去掉一个 节点或一条边的微弱差异将伴随迭代次数的增加而 因为连锁反应无限放大。分析自相似超网络联合度 分布，可得出相似结论。 继续分析随机超网络敏感性，具体而言，是分 析随机超网络边际度分布敏感性。随机超网络中， 是将边际节点度分布多项式进行系数相乘且次数相 加。式 (19) 中，对边际度分布多项式进行分析，可得 d lPolyM(i) (S ab) l! x=0 = ( d(v(a)j)+d(v(b)k) ) ! l! ( d(v(a)j)+d(v(b)k)−l ) ! | ∑Va(i)| j=1 | ∑Vb(i)| k=1 x d(v(a)j)+d(v(b)k ) x=0 (22) 从式 (22) 中可以看出，增添或去掉一个节点或 一条边后，可用微分公式来增量式更新，即可微，也 即不敏感。所以初始情形下，尽管选取不同图但生 成随机超网络度分布形态近似相同，均呈钟形高斯分 布。分析随机超网络联合度分布，可得出相似结论。 引入微积分等理论与技术，在超网络敏感性分 析方面有一些量化结论，但对超网络敏感性根源仍 未完全透彻了解，后续研究中，重点在于继续使用 微分方程等工具，对超网络敏感性进行深入研究。 4 结束语 本文主要对自相似超网络与随机超网络等通过 矩阵运算生成超网络进行分析，通过超网络的邻接 矩阵迭代 Khatri-Rao 积运算可生成自相似超网络， 自相似特性在于其邻接矩阵为分形矩阵，连通且非 二分图序列构成自相似超网络同时有小世界特性， 在与门格海绵的对比中，阐明了自相似超网络的各 项性质。多个超网络邻接矩阵 Khatri-Rao 和运算可 生成随机超网络，随机特性在于有限个高斯分布的 线性组合。通过边际度分布多项式及联合度分布多 项式可计算出基于矩阵运算生成的超网络边际度分 布与联合度分布等特性。此外，对超网络数量及敏 感性等进行一定程度的量化分析。 参考文献： ERDŐS P, RÉNYI A. On random graphs I.[J]. Publicationes mathematicae, 1959, 6: 290–297. [1] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. [2] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world network model[J]. Physics letters A, 1999, 293(4/5/6): 341–346. [3] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509–512. [4] BARABÁSI A L, RAVASZ E, VICSEK T. Deterministic scale-free networks[J]. Physica A: statistical mechanics and its applications, 2001, 299(3/4): 559–564. [5] COMELLAS F, SAMPELS M. Deterministic small-world networks[J]. Physica A: statistical mechanics and its applications, 2002, 309(1/2): 231–235. [6] SONG Chaoming, HAVLIN S, MAKSE H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392–395. [7] 张嗣瀛. 复杂系统、复杂网络自相似结构的涌现规律[J]. 复杂系统与复杂性科学, 2006, 3(4): 41–51. ZHANG Siying. The law of emergence of self-similar struc- [8] ·364· 智 能 系 统 学 报 第 13 卷
第3期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·365· tures in complex systems and complex networks[J].Com- equations and their applications to characterization of prob- plex systems and complexity science,2006,3(4):41-51. ability distributions[J].Sankhya:the Indian journal of stat- [9]GALICEANU M,REIS A S,DOLGUSHEV M.Dynamics istics,series A,1968,30(2):167-180. of semiflexible scale-free polymer networks[].The journal [17]TRACY D S,SINGH R P.A new matrix product and its of chemical physics,2014,141(14):144902. applications in partitioned matrix differentiation[J].Statist- [10]刘胜久，李天瑞，洪西进，等.基于矩阵运算的复杂网络 ica neerlandica.1972.26(4):143-157. 构建方法).中国科学：信息科学，2016,46(5)：610-626. [18]LIU Shuangzhe.Matrix results on the Khatri-Rao and LIU Shengjiu,LI Tianrui,HORNG Shijinn,et al.Complex tracy-singh products[J].Linear algebra and its applications, network construction based on matrix operation[J].Scien- 1999,2891/2/3):267-277. tia sinica informationis,2016,46(5):610-626 [19]SREENIVASAN K R,MENEVEAU C.The fractal facets [1]徐明明，陆君安，周进.两层星形网络的特征值谱及同步 of turbulence[J].Journal of fluid mechanics,1986,173: 能力[).物理学报，2016,65(2)：028902. 357-386. XU Mingming,LU Jun'an,ZHOU Jin.Synchronizability [20]MASSOPUST P R.Fractal functions,fractal surfaces,and and eigenvalues of two-layer star networks[J].Acta phys- wavelets[M].San Diego:Academic Press,1994:135-355. ica sinica,2016,65(2):028902. 作者简介： [12]刘胜久，李天瑞，洪西进，等.超网络模型构建及特性分 刘胜久，男，1988年生，博士，主 析).计算机科学与探索，2017,11(2)：194-211 要研究方向为复杂网络、自然语言处 LIU Shengjiu,LI Tianrui,HORNG Shijinn,et al.Hyper- 理、云计算。发表学术论文10余篇。 network model and its properties[J].Journal of frontiers of computer science and technology,2017,11(2):194-211. [13]BARBE A M.On a class of fractal matrices (I)Excess- Matrices and their self-similar properties[J].International journal of bifurcation and chaos,1992.2(4):841-860. 李天瑞，男，1969年生，教授，博 士生导师，主要研究方向为数据挖掘 [14]BARBE A M.Artistic design with fractal matrices[J].The 与知识发现、粒计算与粗糙集、云计算 visual computer,1993,9(5):233-238. 与大数据。发表学术论文240余篇， [15]SHALLIT J,STOLFI J.Two methods for generating 主持科技项目20余项，其中国家级项 fractals[J].Computers&graphics,1989,13(2):185-191. 目6项。 [16]KHATRI C G,RAO C R.Solutions to some functional
tures in complex systems and complex networks[J]. Complex systems and complexity science, 2006, 3(4): 41–51. GALICEANU M, REIS A S, DOLGUSHEV M. Dynamics of semiflexible scale-free polymer networks[J]. The journal of chemical physics, 2014, 141(14): 144902. [9] 刘胜久, 李天瑞, 洪西进, 等. 基于矩阵运算的复杂网络 构建方法[J]. 中国科学: 信息科学, 2016, 46(5): 610–626. LIU Shengjiu, LI Tianrui, HORNG Shijinn, et al. Complex network construction based on matrix operation[J]. Scientia sinica informationis, 2016, 46(5): 610–626. [10] 徐明明, 陆君安, 周进. 两层星形网络的特征值谱及同步 能力[J]. 物理学报, 2016, 65(2): 028902. XU Mingming, LU Jun’an, ZHOU Jin. Synchronizability and eigenvalues of two-layer star networks[J]. Acta physica sinica, 2016, 65(2): 028902. [11] 刘胜久, 李天瑞, 洪西进, 等. 超网络模型构建及特性分 析[J]. 计算机科学与探索, 2017, 11(2): 194–211. LIU Shengjiu, LI Tianrui, HORNG Shijinn, et al. Hypernetwork model and its properties[J]. Journal of frontiers of computer science and technology, 2017, 11(2): 194–211. [12] BARBÉ A M. On a class of fractal matrices (I) ExcessMatrices and their self-similar properties[J]. International journal of bifurcation and chaos, 1992, 2(4): 841–860. [13] BARBÉ A M. Artistic design with fractal matrices[J]. The visual computer, 1993, 9(5): 233–238. [14] SHALLIT J, STOLFI J. Two methods for generating fractals[J]. Computers & graphics, 1989, 13(2): 185–191. [15] [16] KHATRI C G, RAO C R. Solutions to some functional equations and their applications to characterization of probability distributions[J]. Sankhyā: the Indian journal of statistics, series A, 1968, 30(2): 167–180. TRACY D S, SINGH R P. A new matrix product and its applications in partitioned matrix differentiation[J]. Statistica neerlandica, 1972, 26(4): 143–157. [17] LIU Shuangzhe. Matrix results on the Khatri-Rao and tracy-singh products[J]. Linear algebra and its applications, 1999, 289(1/2/3): 267–277. [18] SREENIVASAN K R, MENEVEAU C. The fractal facets of turbulence[J]. Journal of fluid mechanics, 1986, 173: 357–386. [19] MASSOPUST P R. Fractal functions, fractal surfaces, and wavelets[M]. San Diego: Academic Press, 1994: 135–355. [20] 作者简介： 刘胜久，男，1988 年生，博士，主 要研究方向为复杂网络、自然语言处 理、云计算。发表学术论文 10 余篇。 李天瑞，男，1969 年生，教授，博 士生导师，主要研究方向为数据挖掘 与知识发现、粒计算与粗糙集、云计算 与大数据。发表学术论文 240 余篇， 主持科技项目 20 余项，其中国家级项 目 6 项。 第 3 期 刘胜久，等：基于矩阵运算的超网络构建方法研究及特性分析 ·365·