·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]. Publica￾tiones 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 let￾ters A, 1999, 293(4/5/6): 341–346. [3] BARABÁSI A L, ALBERT R. Emergence of scaling in ran￾dom 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 applic￾ations, 2002, 309(1/2): 231–235. [6] SONG Chaoming, HAVLIN S, MAKSE H A. Self-similar￾ity 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 卷