一种随机超网络构建方法

摘要

本发明公开了一种基于多个简单超图邻接矩阵的Tracy-Singh和运算的随机超网络构建方法，其主要步骤包括确定生成超网络集合、计算生成超网络邻接矩阵集合、计算生成超网络节点度分布多项式集合、计算生成超网络节点超度分布多项式集合、计算生成超网络超边度分布多项式集合、计算超网络的邻接矩阵、计算随机超网络节点度分布多项式、计算随机超网络节点超度分布多项式、计算随机超网络超边度分布多项式等。采用本发明构建的随机超网络节点度分布、节点超度分布及超边度分布呈正态分布，具备随机超网络的特点，其实质在于生成超网络正态分布形式的节点度分布、节点超度分布、超边度分布的线性组合。

主权项

一种随机超网络构建方法，其特征在于：包括如下步骤：(1)确定生成超网络集合U_H＝{H₁，H₂，H₃，…，H_i，…}；(2)计算生成超网络集合U_H中所有超网络H_i的邻接矩阵A(H_i)，得到生成超网络集合U_H的邻接矩阵集合U_A(H)＝{A(H₁)，A(H₂)，A(H₃)，…，A(H_i)，…}：在生成超网络集合U_H中，对于任一具有n个顶点、m条超边的生成超网络H，其邻接矩阵是n×m的矩阵A(H)_n×m，其中对于矩阵中的每一个数据，若顶点i在超边j中，则有A(H)(i,j)＝1，否则，A(H)(i,j)＝0；由于A(H)_n×m的每一列代表一条超边，可以将A(H)_n×m视为m个n×1的分块矩阵A(H)_n×1的组合，即有：A(H)_n×m＝[A(H)₁₁A(H)₁₂A(H)₁₃…A(H)_1i…A(H)_1(m－1)A(H)_1m]；(3)计算生成超网络集合U_H中所有超网络H_i的节点度分布多项式，得到生成超网络集合U_H的节点度分布多项式集合U_PolyDD(Hd)＝{PolyDD(Hd₁)，PolyDD(Hd₂)，PolyDD(Hd₃)，…，PolyDD(Hd_i)，…}：在生成超网络集合U_H中，任一超网络H的节点度分布多项式PolyDD(Hd)计算方法为：$\mathrm{PolyDD}\left(\mathrm{Hd}\right)=\underset{i=1}{\overset{n}{\Sigma }}{x}^{{\mathrm{Hd}}_i}=\underset{j=1}{\overset{\infty }{\Sigma }}{N}_j{x}^j;$其中，n为超网络H的超边数目，Hd_i表示第i条超边包含的顶点数目，即超边i的度，N_j表示度为j的节点的数目；(4)计算生成超网络集合U_H中所有超网络H_i的节点超度分布多项式，得到生成超网络集合U_H的节点超度分布多项式集合U_PolyDD(Hhd)＝{PolyDD(Hhd₁)，PolyDD(Hhd₂)，PolyDD(Hhd₃)，…，PolyDD(Hhd_i)，…}：在生成超网络集合U_H中，任一超网络H的节点超度分布多项式PolyDD(Hhd)计算方法为：$\mathrm{PolyDD}\left(\mathrm{Hhd}\right)=\underset{i=1}{\overset{n}{\Sigma }}{x}^{{\mathrm{Hhd}}_i}=\underset{j=1}{\overset{\infty }{\Sigma }}{N}_j{x}^j;$其中，n为超网络H的顶点数目，Hd_i表示包含第i个顶点的超边数目，即顶点i的超度，N_j表示超度为j的顶点的数目；(5)计算生成超网络集合U_H中所有超网络H_i的超边度分布多项式，得到生成超网络集合U_H的超边度分布多项式集合U_PolyDD(Hed)＝{PolyDD(Hed₁)，PolyDD(Hed₂)，PolyDD(Hed₃)，…，PolyDD(Hed_i)，…}：在生成超网络集合U_H中，任一超网络H的超边度分布多项式PolyDD(Hed)计算方法为：$\mathrm{PolyDD}\left(\mathrm{Hed}\right)=\underset{i=1}{\overset{n}{\Sigma }}{x}^{{\mathrm{Hed}}_i+1}=\underset{j=1}{\overset{\infty }{\Sigma }}{N}_j{x}^j;$其中，n为超网络H的超边数目，Hed_i表示与第i条超边邻接的超边数目，即超边i的超边度，N_j表示超边度为j－1的超边的数目；(6)从生成超网络集合中顺次选取k个生成超网络H₍₁₎、H₍₂₎、H₍₃₎、…、H_(k－1)、H_(k)，记为H₍₁₎H₍₂₎H₍₃₎…H_(k－1)H_(k)，允许重复选取，对每个生成超网络H_(i)对应的邻接矩阵A(H_(i))按如下方法计算所构建的随机超网络的邻接矩阵A^(l)(H^(l))，其中，l代表运算的次数，A^(l)(H^(l))代表l个生成超网络对应的邻接矩阵顺次进行运算后得到的一个随机超网络的邻接矩阵：根据Tracy‑Singh和的规则A^(k+1)(H^(k+1))＝A^(k)(H^(k))▽A(H)进行计算，得到所构建的随机超网络的邻接矩阵，其中，矩阵A(a_ij)_m×n及矩阵B(b_ij)_p×q的Tracy‑Singh和A_m×n▽B_p×q定义如下：A_m×n▽B_p×q＝A_m×nοI_n×n+I_n×nοB_p×q；其中I_n×n表示n×n单位矩阵，ο表示Tracy‑Singh积运算；将A^(k)(H^(k))及A(H)视为分块的列矩阵进行Tracy‑Singh积运算；对于m×n的矩阵A及p×q的矩阵B，可先将其分别划分为m_i×n_j的分块矩阵A_ij及p_k×q_j分块矩阵B_kl，再进行Tracy‑Singh积运算；矩阵A及矩阵B的Tracy‑Singh积AοB定义如下：其中，表示Kronecker积运算；设A_ij为矩阵A_m×n的第i行第j列m_i×n_j阶分块矩阵，B_kl为矩阵B_p×q的第k行第l列p_k×q_l阶分块矩阵，且有：$\left\{\begin{array}{c}\underset{i}{\Sigma }{m}_i=m\\ \underset{j}{\Sigma }{n}_j=n\\ \underset{k}{\Sigma }{p}_k=p\\ \underset{l}{\Sigma }{q_l}_{}=q\end{array}\right.;$将所有的邻接矩阵视为1行的分块矩阵，每个分块矩阵均是n×1的普通矩阵，即有：$\left\{\begin{array}{c}{n}_j=1\\ q_l=1\end{array}\right.;$矩阵A(a_ij)_m×n及矩阵B(b_ij)_p×q的Tracy‑Singh积需要用到Kronecker积；Kronecker积运算的具体方法为：对任意矩阵Am×n与矩阵Bp×q而言，其Kronecker积Am×n Bp×q定义如下采用步骤(6)顺次选取k个生成超网络H₍₁₎、H₍₂₎、H₍₃₎、…、H_(k－1)、H_(k)进行Tracy‑Singh和而得到的随机超网络H^(k)可以记为如下形式：H^(k)＝▽H₍₁₎H₍₂₎H₍₃₎…H_(k－1)H_(k)；(7)按照如下方法计算所构建的随机超网络H^(k)的节点度分布多项式PolyDD(Hd^(l))，其中，l代表Tracy‑Singh积运算的次数，PolyDD(Hd^(l))代表l个生成超网络对应的邻接矩阵顺次进行Tracy‑Singh积运算后得到的随机超网络节点度分布多项式：$\begin{array}{c}\mathrm{PolyDD}\left({\mathrm{Hd}}^{(k+1)}\right)=\mathrm{KronPro}(\mathrm{PolyDD}\left({\mathrm{Hd}}^{\left(k\right)}\right),\mathrm{PolyDD}\left({\mathrm{Hd}}_{(k+1)}\right)\\ =\mathrm{KronPro}(\underset{i=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{x}^i,\underset{j=1}{\overset{\infty }{\Sigma }}{N}_{(k+1)j}{x}^j)\\ =\underset{i=1}{\overset{\infty }{\Sigma }}\underset{j=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{N}_{(k+1)j^{x^{i+j}}}(i,j=\mathrm{1,2,3},...)\end{array};$(8)按照如下方法计算所构建的随机超网络H^(k)的节点超度分布多项式PolyDD(Hhd^(l))，其中，l代表Tracy‑Singh和运算的次数，PolyDD(Hhd^(l))代表l个生成超网络对应的邻接矩阵顺次进行Tracy‑Singh和运算后得到的随机超网络节点超度分布多项式：$\begin{array}{c}\mathrm{PolyDD}\left({\mathrm{Hhd}}^{(k+1)}\right)=\mathrm{KronPro}(\mathrm{PolyDD}\left({\mathrm{Hhd}}^{\left(k\right)}\right),\mathrm{PolyDD}\left({\mathrm{Hhd}}_{(k+1)}\right)\\ =\mathrm{KronPro}(\underset{i=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{x}^i,\underset{j=1}{\overset{\infty }{\Sigma }}{N}_{(k+1)j}{x}^j)\\ =\underset{i=1}{\overset{\infty }{\Sigma }}\underset{j=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{N}_{(k+1)j^{x^{i+j}}}(i,j=\mathrm{1,2,3},...)\end{array};$(9)按照如下方法计算所构建的随机超网络的超边度分布多项式PolyDD(Hed^(l))，其中，l代表Tracy‑Singh和运算的次数，PolyDD(Hed^(l))代表l个生成超网络对应的邻接矩阵顺次进行Tracy‑Singh和运算后得到的随机超网络超边度分布多项式：$\begin{array}{c}\mathrm{PolyDD}\left({\mathrm{Hed}}^{(k+1)}\right)=\mathrm{KronPro}(\mathrm{PolyDD}\left({\mathrm{Hed}}^{\left(k\right)}\right),\mathrm{PolyDD}\left({\mathrm{Hed}}_{(k+1)}\right)\\ =\mathrm{KronPro}(\underset{i=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{x}^i,\underset{j=1}{\overset{\infty }{\Sigma }}{N}_{(k+1)j}{x}^j)\\ =\underset{i=1}{\overset{\infty }{\Sigma }}\underset{j=1}{\overset{\infty }{\Sigma }}{N}_i^{\left(k\right)}{N}_{(k+1)j^{x^{i+j}}}(i,j=\mathrm{1,2,3},...)\end{array};$(10)重复步骤(6)至步骤(9)，得到指定顶点数目、指定节点数目或指定超网络数目的随机超网络时，终止操作。