·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 卷