«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2018, Vol. 13 Issue (3): 359-365  DOI: 10.11992/tis.201706055
0

引用本文  

刘胜久, 李天瑞, 洪西进, 等. 基于矩阵运算的超网络构建方法研究及特性分析[J]. 智能系统学报, 2018, 13(3), 359-365. DOI: 10.11992/tis.201706055.
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. DOI: 10.11992/tis.201706055.

基金项目

国家自然科学基金项目(61573292,61262058).

通信作者

李天瑞. E-mail:trli@swjtu.edu.cn.

作者简介

刘胜久,男,1988年生,博士,主要研究方向为复杂网络、自然语言处理、云计算。发表学术论文10余篇;
李天瑞,男,1969年生,教授,博士生导师,主要研究方向为数据挖掘与知识发现、粒计算与粗糙集、云计算与大数据。发表学术论文240余篇,主持科技项目20余项,其中国家级项目6项

文章历史

收稿日期:2017-06-14
网络出版日期:2018-04-12
基于矩阵运算的超网络构建方法研究及特性分析
刘胜久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和运算顺次应用于多个初始图序列组成超网络的邻接矩阵,得到一个边际节点度呈一维高斯分布而联合节点度呈高维高斯分布的随机超网络。最后,给出了基于矩阵运算的超网络构建方法的若干性质。
关键词矩阵运算    复杂网络    超网络    模型构建    分形维数    自相似超网络    随机超网络    特性分析    
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.
Key words: matrix operation    complex network    supernetwork    model building    fractal dimension    self-similarity supernetwork    random supernetwork    property analysis    

复杂网络可较好地描述并刻画复杂系统,对其系统性研究起源于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)}}, \cdots ,{G_{(i)}}, \cdots ,{G_{(n)}}$ ,其中 ${G_{(i)}} = $ $({V_{(i)}},{E_{(i)}})(1 \leqslant i \leqslant n)$ 是一个无向无环无权无重边简单图,而且 ${V_{(i)}} \!=\! ({v_{(i)1}},{v_{(i)2}}, \cdots \! ,{v_{(i)j}}, \cdots )(1 \! \leqslant \! j \! \leqslant \! \left| {{V_{(i)}}} \right|)$ ${E_{(i)}} \!=\! ({e_{(i)1}},$ ${e_{(i)2}}, \! \cdots ,{e_{(i)k}}, \cdots )(1 \leqslant k \leqslant \left| {{E_{(i)}}} \right|)$ 分别是 ${G_{(i)}}$ 中的节点集及边集,且 ${E_{(i)}} \subseteq {V_{(i)}} \times {V_{(i)}}$ $n$ 表示图序列长度, $\left| {{V_{(i)}}} \right|$ $\left| {{E_{(i)}}} \right|$ 分别表示 ${G_{(i)}}$ 中节点数目及边数目。

定义1 超网络是指由图序列 ${G_{(1)}},{G_{(2)}}, \cdots ,{G_{(i)}}, \cdots ,$ ${G_{(n)}}$ 构成且对应节点序列 ${v_{(1)j}},{v_{(2)j}}, \cdots ,{v_{(i)j}}, \cdots ,{v_{(n)j}}$ 相互关联的层次形态的网络,记为 $S$ ,表述为

$S = \left\{ {{G_{(1)}},{G_{(2)}}, \cdots ,{G_{(i)}}, \cdots ,{G_{(n)}}} \right\}$ (1)

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

${{A}}(S) = \left[ {A({G_{(1)}}) \,\,\,\, A({G_{(2)}})\,\,\,\, \cdots \,\,\,\, A({G_{(i)}}) \,\,\,\, \cdots \,\,\,\, A({G_{(n)}})} \right]$ (2)

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

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

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

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

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

$\left\{ \begin{array}{l} {\rm Poly}_{M(1)}(S) = \displaystyle\sum\limits_{i = 1}^{\left| {{V_{(1)}}} \right|} {{x^{d({v_{(1)}}_i)}}} \ \\ {\rm Poly}_{M(2)}(S) = \displaystyle\sum\limits_{i = 1}^{\left| {{V_{(2)}}} \right|} {{y^{d({v_{(2)}}_i)}}} \ \\ {\rm Poly}_J(S) = \displaystyle\sum\limits_{i = 1}^{\left| V \right|} {{x^{d({v_{(1)}}_i)}}{y^{d({v_{(2)}}_i)}}} \ \\ \end{array} \right..$ (3)

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

${\rm Density}(S) = \frac{{2\displaystyle\sum\limits_{i = 1}^N {\left| {{E_{(i)}}} \right|} }}{{\displaystyle\sum\limits_{i = 1}^N {\left| {{V_{(i)}}} \right|(\left| {{V_{(i)}}} \right| - 1)} }} = \frac{1}{N}\sum\limits_{i = 1}^N {{\rm Density}({G_{(i)}})} $ (4)
1.2 分形理论

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

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

图案生成是分形矩阵最初应用领域[15]。对于矩阵 ${{{A}}_{m \times n}}$ ,用 ${{A}}$ 的各元素 ${a_{ij}}(1 \leqslant i \leqslant m,1 \leqslant j \leqslant n)$ ${{A}}$ 的各元素进行相加,再用生成的新矩阵更换 ${a_{ij}}$ ,生成局部和整体自相似的一个新矩阵。若一直将上述操作延续下去,则会生成自相似的一簇新矩阵: ${{{A}}^{(1)}}_{{m^2} \times {n^2}}$ ${{{A}}^{(2)}}_{{m^3} \times {n^3}}$ ${{{A}}^{(3)}}_{{m^4} \times {n^4}}$ ,…,其中 ${{{A}}^{(i + 1)}}_{{m^{i + 2}} \times {n^{i + 2}}}$ 都是由 ${{{A}}^{(i)}}_{{m^{i + 1}} \times {n^{i + 1}}}$ 的各元素与 ${{A}}$ 进行相加后更换而生成的。分形矩阵就是上述更换操作生成的一簇新矩阵 ${{{A}}^{(1)}}_{{m^2} \times {n^2}}$ ${{{A}}^{(2)}}_{{m^3} \times {n^3}}$ ${{{A}}^{(3)}}_{{m^4} \times {n^4}}, \cdots$ 文献[16]中,分形矩阵同样可以根据迭代Kronecker积运算而得到。本文在超网络邻接矩阵中引入矩阵运算。

1.3 矩阵理论

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

${{A}}$ ${{B}}$ 的Khatri-Rao积运算[17]可表示为

${{A}} * {{B}} = {\left( {{{{A}}_{ij}} \otimes {{{B}}_{ij}}} \right)_{ij}}$ (5)

${{A}}$ ${{B}}$ 的Khatri-Rao和运算[18]可表示为

${{A}}\nabla {{B}} = {{A}} * {{I}} + {{I}} * {{B}}$ (6)
2 基于矩阵运算超网络模型 2.1 自相似超网络模型

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

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

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

$\left\{ \begin{array}{l} \left| {{V_{(i)}}^{(k)}} \right| = {\left| {{V_{(i)}}} \right|^{k + 1}} \ \\ \left| {{E_{(i)}}^{(k)}} \right| = {2^k}{\left| {{E_{(i)}}} \right|^{k + 1}} \ \\ {\rm Density}({S^{(k)}}) = \displaystyle\frac{1}{N}\sum\limits_{i = 1}^N {{\rm{Density}}({G_{(i)}}^{(k)})} \\ \end{array} \right.$ (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之和,即

${\rm{FD}}(S) = 1 + {\left( {\prod\limits_{i = 1}^n {{\rm{FD}}({G_{(i)}})} } \right)^{\frac{1}{n}}} = 1 + {\left( {\prod\limits_{i = 1}^n {\frac{{{\rm{log}_2}2\left| {{E_{(i)}}} \right|}}{{{\rm{log}_2}\left| {{V_{(i)}}} \right|}}} } \right)^{\frac{1}{n}}}$ (9)

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

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

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

${\left( {\prod\limits_{i = 1}^N {{\text{FD}}({G_{(i)}})} } \right)^{\frac{1}{N}}} < 2$ (10)

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

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

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

证明 对连通且非二分图 ${G_{(i)}}$ 而言,有 $\left| {{E_{(i)}}} \right| \geqslant $ $ \left| {{V_{(i)}}} \right| - 1 \geqslant 2$ ,则有

${\text{FD}}({G_{(i)}}) = \frac{{{\text{lo}}{{\text{g}}_2}2\left| {{E_{(i)}}} \right|}}{{{\text{lo}}{{\text{g}}_2}\left| {{V_{(i)}}} \right|}} \geqslant \frac{{{\text{lo}}{{\text{g}}_2}2\left( {\left| {{V_{(i)}}} \right| - 1} \right)}}{{{\text{lo}}{{\text{g}}_2}\left| {{V_{(i)}}} \right|}} > 1$ (11)

式(9)中有

${\left( {\prod\limits_{i = 1}^N {{\text{FD}}({G_{(i)}})} } \right)^{\frac{1}{N}}} > 1$ (12)

结合定理3,有 $2 < {\text{FD}}(S) < 3$ 。引理2得证。

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

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

证明 文献[9]中,连通且非二分图邻接矩阵迭代Kronecker积运算生成Kronecker积图直径不超过初始图直径两倍。设构成超网络任一图 ${G_{(i)}}$ 直径为 ${d_{(i)}}$ ,于是自相似超网络任意一层网络中的任意一个节点均可在不超过2 $\displaystyle\sum\limits_{i = 1}^N {{d_{(i)}}} $ 步内抵达任意一层网络中的任意一个节点。定理4得证。

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

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

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

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

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

门格海绵中,设初始情况下正方体棱长 ${T_0} = 1$ ,正方体数量 ${N_0} = 1$ ,周长 ${L_0} = 12$ ,表面积 ${S_0} = 6$ ,体积 ${V_0} = 1$ ${T_n}$ ${N_n}$ ${L_n}$ ${S_n}$ ${V_n}$ 分别为第 $n$ 步迭代后生成门格海绵正方体的棱长、数量、周长、表面积及体积,则可以得到:

$\left\{ \begin{array}{l} \mathop {\lim}\limits_{n \to \infty } {T_n} = \mathop {\lim}\limits_{n \to \infty } {\left( {\displaystyle\frac{1}{3}} \right)^n}{T_0} = \mathop {\lim}\limits_{n \to \infty } \displaystyle\frac{1}{{{3^n}}} \to 0 \\[8pt] \mathop {\lim}\limits_{n \to \infty } {N_n} = \mathop {\lim}\limits_{n \to \infty } {20^n}{N_0} = \mathop {\lim}\limits_{n \to \infty } {20^n} \to \infty \\[8pt] \mathop {\lim}\limits_{n \to \infty } {L_n} = \mathop {\lim}\limits_{n \to \infty } 12\left[ {\displaystyle\frac{6}{{17}}{{\left( {\frac{{20}}{3}} \right)}^n} + \frac{{11}}{{17}}} \right] \to \infty \\[8pt] \mathop {\lim}\limits_{n \to \infty } {S_n} = \mathop {\lim}\limits_{n \to \infty } {\left( {\displaystyle\frac{4}{3}} \right)^n}{S_0} = \mathop {\lim}\limits_{n \to \infty } \displaystyle\frac{{{2^{2n + 1}}}}{{{3^{n - 1}}}} \to \infty \\[8pt] \mathop {\lim}\limits_{n \to \infty } {V_n} = \mathop {\lim}\limits_{n \to \infty } {\left( {\displaystyle\frac{{20}}{{27}}} \right)^n}{V_0} \to 0 \end{array} \right.$ (13)

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

表 1 自相似超网络与门格海绵对比表 Tab.1 Comparison between self-similarity supernetwork and Menger sponge
2.2 随机超网络模型

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

超网络 ${S_a}$ ${S_b}$ 对应边际节点度分布多项式 ${\rm Poly}_{M(i)}({S_a})$ ${\rm Poly}_{M(i)}({S_b})$ 中,将Khatri-Rao积运算应用于 ${S_a}$ ${S_b}$ 对应邻接矩阵生成超网络 ${S_{ab}}$ 的边际节点度分布可通过 ${\rm Poly}_{M(i)}({S_a})$ ${\rm Poly}_{M(i)}({S_b})$ 的Khatri-Rao积运算而得到,即

${\rm Poly}_{M(i)}({S_{ab}}) = \sum\limits_{j = 1}^{\left| {{V_{a(i)}}} \right|} {\sum\limits_{k = 1}^{\left| {{V_{b(i)}}} \right|} {{x^{d({v_{(a)j}}) \times d({v_{(b)k}})}}} } $ (14)

类似地,将Khatri-Rao和运算应用于 ${S_a}$ ${S_b}$ 对应邻接矩阵生成超网络 ${S'_{ab}}$ 的边际节点度分布可通过式(15)得到:

${\rm Poly}_{M(i)}({S'_{ab}}) = \sum\limits_{j = 1}^{\left| {{V_{a(i)}}} \right|} {\sum\limits_{k = 1}^{\left| {{V_{b(i)}}} \right|} {{x^{d({v_{(a)j}}) + d({v_{(b)k}})}}} } $ (15)

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

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

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

$\left\{ \begin{array}{l} \left| {{V_{(i)}}^{(n)}} \right| = \displaystyle\prod\limits_{j = 1}^n {\left| {{V_{(j)i}}} \right|} = \displaystyle\prod\limits_{i = 1}^n {{{\left. {{\text{Poly}}({G_{(i)}})} \right|}_{x = 1}}} \ \\ \left| {{E_{(i)}}^{(n)}} \right| = {\left. {\displaystyle\frac{1}{2}{\text{Pol}}{{{\text{y}}}'_{M(i)}}({S^{(n)}})} \right|_{x = 0}} = \displaystyle\sum\limits_{j = 1}^n {\left[ {\left| {{E_{(j)i}}} \right|\displaystyle\prod\limits_{k = 1,\;k \ne j}^{k = n} {\left| {{V_{(k)i}}} \right|} } \right]} \ \\ {\rm Density}({S_{(i)}}^{(n)}) =\displaystyle \frac{{2\left| {{E_{(i)}}^{(n)}} \right|}}{{\left| {{V^{(n)}}} \right|(\left| {{V_{(i)}}^{(n)}} \right| - 1)}} \ \\ \end{array} \right.$ (16)

${S^{(n)}}$ 可简记为

${S^{(n)}} = \mathop \nabla \limits_{i = 1}^n {S_{(i)}}$ (17)
2.3 不同组合超网络模型

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

表 2 9类超网络统计表 Tab.2 Statistics of 9 supernetworks
Download:
图 1 9类超网络关系图 Fig. 1 Diagram of 9 supernetworks
3 基于矩阵运算超网络模型理论分析 3.1 基于矩阵运算超网络数量

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

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

${\rm Num}\left( {{\rm Poly}_{M(i)}(S)} \right) = \prod\limits_{j = 1}^n {{\rm Num}\left( {{\rm Poly}_{M(j)}(S)} \right)} ,\left( {i = 1,2, \cdots ,n} \right)$ (18)

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

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

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

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

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

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

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

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

式(9)为基于初始超网络生成自相似超网络分形维数,分析增添或去掉生成超网络初始图一个节点与一条边对超网络分形维数的影响就是对其分形维数一阶导数进行分析。不失一般性,对 ${G_a}$ ${G_b}$ 生成的2层超网络 ${S_{ab}}$ 分形维数的一阶导数进行分析:

$\begin{array}{c}{\rm{dFD}}({S_{ab}}) = \displaystyle\frac{1}{n}{\left( {{\text{FD}}({G_a}){\text{FD}}({G_b})} \right)^{\frac{1}{n} - 1}}.\left( {{\text{FD}}({G_b})\displaystyle\frac{{{\text{dFD}}({G_a})}}{{{\text{d}}x}} + {\text{FD}}({G_a})\frac{{{\text{dFD}}({G_b})}}{{{\text{d}}y}}} \right)\end{array}$ (19)

任一图 $G$ 中,文献[9]中有如下结论:

${\left. {{\rm{dFD}}(G)} \right|_{x = 1}} = \frac{{{{\left. {\rm Poly}''(G) \right|}_{x = 1}}\left| V \right|\log_2\left| V \right| - 4{{\left| E \right|}^2}\log_22\left| E \right|}}{{2\left| E \right|\left| V \right|\log_2^2\left| V \right|}}$ (20)

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

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

$\begin{array}{c}{\left. {\displaystyle\frac{{{d^l}{\rm Poly}_{M(i)}({S_{ab}})}}{{l!}}} \right|_{x = 0}} =\\ [10pt]\displaystyle\frac{{\left( {d({v_{(a)j}}) \times d({v_{(b)k}})} \right)!}}{{l!\left( {d({v_{(a)j}}) \times d({v_{(b)k}}) - l} \right)!}}{\left. {\displaystyle\sum\limits_{j = 1}^{\left| {{V_{a(i)}}} \right|} {\displaystyle\sum\limits_{k = 1}^{\left| {{V_{b(i)}}} \right|} {{x^{d({v_{(a)j}}) \times d({v_{(b)k}})}}} } } \right|_{x = 0}}\end{array}$ (21)

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

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

$\begin{array}{c}{\left. {\displaystyle\frac{{{d^l}{\rm Poly}_{M(i)}({S_{ab}})}}{{l!}}} \right|_{x = 0}} =\\ [10pt]\displaystyle\frac{{\left( {d({v_{(a)j}}) + d({v_{(b)k}})} \right)!}}{{l!\left( {d({v_{(a)j}}) + d({v_{(b)k}}) - l} \right)!}}{\left. {\displaystyle\sum\limits_{j = 1}^{\left| {{V_{a(i)}}} \right|} {\displaystyle\sum\limits_{k = 1}^{\left| {{V_{b(i)}}} \right|} {{x^{d({v_{(a)j}}) + d({v_{(b)k}})}}} } } \right|_{x = 0}}\end{array}$ (22)

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

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

4 结束语

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

参考文献
[1] ERDŐS P, RÉNYI A. On random graphs I.[J]. Publicationes mathematicae, 1959, 6: 290-297. (0)
[2] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. DOI:10.1038/30918 (0)
[3] 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. (0)
[4] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. DOI:10.1126/science.286.5439.509 (0)
[5] 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. (0)
[6] COMELLAS F, SAMPELS M. Deterministic small-world networks[J]. Physica A: statistical mechanics and its applications, 2002, 309(1/2): 231-235. (0)
[7] SONG Chaoming, HAVLIN S, MAKSE H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395. DOI:10.1038/nature03248 (0)
[8] 张嗣瀛. 复杂系统、复杂网络自相似结构的涌现规律[J]. 复杂系统与复杂性科学, 2006, 3(4): 41-51.
ZHANG Siying. The law of emergence of self-similar structures in complex systems and complex networks[J]. Complex systems and complexity science, 2006, 3(4): 41-51. (0)
[9] GALICEANU M, REIS A S, DOLGUSHEV M. Dynamics of semiflexible scale-free polymer networks[J]. The journal of chemical physics, 2014, 141(14): 144902. DOI:10.1063/1.4897563 (0)
[10] 刘胜久, 李天瑞, 洪西进, 等. 基于矩阵运算的复杂网络构建方法[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. (0)
[11] 徐明明, 陆君安, 周进. 两层星形网络的特征值谱及同步能力[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. (0)
[12] 刘胜久, 李天瑞, 洪西进, 等. 超网络模型构建及特性分析[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. (0)
[13] BARBÉ 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. DOI:10.1142/S0218127492000471 (0)
[14] BARBÉ A M. Artistic design with fractal matrices[J]. The visual computer, 1993, 9(5): 233-238. DOI:10.1007/BF01908446 (0)
[15] SHALLIT J, STOLFI J. Two methods for generating fractals[J]. Computers & graphics, 1989, 13(2): 185-191. (0)
[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. (0)
[17] 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. DOI:10.1111/j.1467-9574.1972.tb00199.x (0)
[18] 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. (0)
[19] SREENIVASAN K R, MENEVEAU C. The fractal facets of turbulence[J]. Journal of fluid mechanics, 1986, 173: 357-386. DOI:10.1017/S0022112086001209 (0)
[20] MASSOPUST P R. Fractal functions, fractal surfaces, and wavelets[M]. San Diego: Academic Press, 1994: 135–355. (0)