劉勝久，李天瑞+，洪西進,3，王紅軍，珠 杰,4

1.西南交通大學 信息科學與技術學院，成都 611756

2.四川省云計算與智能技術高校重點實驗室，成都 611756

3.臺灣科技大學 資訊工程系，臺北 10607

4.西藏大學 計算機系，拉薩 850000

超網絡模型構建及特性分析*

劉勝久1,2，李天瑞1,2+，洪西進1,2,3，王紅軍1,2，珠 杰1,2,4

1.西南交通大學 信息科學與技術學院，成都 611756

2.四川省云計算與智能技術高校重點實驗室，成都 611756

3.臺灣科技大學 資訊工程系，臺北 10607

4.西藏大學 計算機系，拉薩 850000

關聯矩陣是超網絡的一種表述形式，節(jié)點度、節(jié)點超度和超邊度是度量超網絡的一種方法。從關聯矩陣出發(fā)對超網絡進行研究，重點研究了自相似超網絡及隨機超網絡，并給出了基于矩陣運算的超網絡構建方法的若干性質。自相似超網絡可通過對一個簡單初始超圖的關聯矩陣進行迭代的Tracy-Singh積運算得到，而隨機超網絡可通過對多個簡單初始超圖的關聯矩陣進行順次的Tracy-Singh和運算得到。自相似超網絡的分形維數不超過2，且當初始超圖是連通的且非二分超圖時，自相似超網絡的直徑不超過初始超圖直徑的兩倍，即同時具有小世界特性。隨機超網絡的節(jié)點度、節(jié)點超度和超邊度均呈正態(tài)分布。仿真實驗證實了所構建的超網絡的各項特性。

超網絡；矩陣運算；自相似超網絡；分形維數；隨機超網絡

1 引言

作為復雜系統的抽象表述，復雜網絡一直受到人們極大的關注。20世紀中葉，Erdos和Renyi提出的ER隨機網絡模型[1]首開復雜網絡的系統性研究，并奠定了后續(xù)近半個世紀對復雜網絡研究的基礎。隨后，WS小世界網絡模型[2]、NW小世界網絡模型[3]和BA無標度網絡模型[4]等一些重要的網絡模型相繼問世。

有別于ER網絡模型泊松分布形態(tài)的度分布，WS網絡模型與NW網絡模型的度分布均呈指數分布，揭示了復雜網絡的小世界特性；而BA網絡模型的度分布呈冪律分布，揭示了復雜網絡的無標度特性。小世界特性及無標度特性的提出開辟了復雜網絡研究的新紀元，掀開了復雜網絡研究的新局面，并被譽為復雜網絡的兩大特性。近年來，復雜網絡的自相似特性受到人們極大的重視[5]，被譽為復雜網絡繼小世界特性和無標度特性之后的第三大特性。當前復雜網絡的研究主要包括經典的小世界網絡、無標度網絡及自相似網絡等網絡模型的研究與改進。Rudolph等人研究了有向WS小世界網絡模型，提出了一種可精確描述WS小世界網絡非對稱性指數及聚集系數的新分析框架，包括表述其鄰接矩陣的代數表達式[6]。Emmerich等人討論了嵌入式無標度網絡的結構和功能特性，同時將其與非嵌入式無標度網絡的異同進行了對比分析[7]。張嗣瀛給出一個樹狀生長模型，并指出生長過程及自相似結構的涌現可集中由簡單的冪律體現，冪律也是層層相似的自相似結構的成因。此外，這種模型的分形維數或相應的指數是系統功能的度量[8]。除此之外，矩陣等其他理論成果也逐步引入到復雜網絡的研究中[9-10]。

在現實生活中，一般的網絡或圖并不能完全刻畫真實世界網絡的各項特性，普通圖的每一條邊只能連接兩個節(jié)點的缺陷使其在描述真實網絡時存在諸多不便。1970年，Berge提出了超圖的概念[11-12]，建立了無向超圖理論，并應用擬陣來研究超圖理論在運籌學中的應用。Feng等人提出了超圖鄰接矩陣的構建方法[13]。圖的鄰接矩陣是0-1矩陣，而超圖的鄰接矩陣卻不一定是0-1矩陣。區(qū)別于普通圖中兩個節(jié)點之間的連接（邊）只能表示一對節(jié)點之間的關系，超圖中的超邊可以包含任意多個節(jié)點，并用來表示多個節(jié)點之間的關系。Ernesto等人[14]認為凡是可用超圖表示的網絡就是超網絡。

目前超網絡的研究主要集中在基于現實世界的超網絡各項特性的研究。Ernesto等人[15]研究了復雜超網絡的子圖中心度和聚集系數；Ghoshal等人[16]討論了隨機三部超圖及它們的應用；Zlatic等人[17]定義和分析了基于三部超圖模型的統計特性；Neubauer等人[18]利用超圖理論給出了一種在標簽網絡中尋找最大連通子圖的方法。在超網絡模型構建方面，Zhang等人[19]建立了一種基于用戶背景知識和對象，標簽雙重優(yōu)先連接機制的超圖增長模型；裴偉東等人[20]研究了基于一類三角形結構的動態(tài)網絡演化模型，并利用平均場方法得到了這一類網絡結構的理論解，證明了該類演化模型具有很多真實網絡相似的無標度[4]和小世界現象[2-3]；Wang等人[21]給出了一種基于超圖的超網絡動態(tài)演化模型，采用增長和優(yōu)先連接機制逐步生成超網絡，每次將新增加的若干個節(jié)點和超網絡中已有的一個節(jié)點結合生成超邊。胡楓等人[22]構建了一種超網絡動態(tài)演化模型，并通過節(jié)點度、節(jié)點超度及超邊度分析了該模型的基本拓撲性質，仿真實驗發(fā)現，隨著網絡規(guī)模的增大，該動態(tài)演化模型的超度分布遵循無標度的特性。Yang等人[23]提出了一種局域世界超網絡演化模型。此外，矩陣等其他工具已逐步應用到超網絡模型的構建中[24]，對超網絡的研究也在持續(xù)深入[25]。

由于超網絡在描述真實網絡方面比通常的網絡更具優(yōu)勢，在數據挖掘等領域也有著較為廣闊的應用前景，引入新的研究方法與策略來刻畫超網絡是超網絡研究的一大趨勢。鑒于超網絡的關聯矩陣對應于超網絡的拓撲結構，本文擬從關聯矩陣的視角對超網絡進行研究。主要是通過矩陣運算實現超網絡的構建，即對一個簡單初始超圖的關聯矩陣進行迭代Tracy-Singh積運算以構建自相似超網絡，并對多個簡單初始超圖的關聯矩陣進行Tracy-Singh和運算以構建隨機超網絡。同時給出了自相似超網絡及隨機超網絡的若干性質，以期通過對超網絡的研究洞悉真實復雜網絡及復雜系統的特性。

2 預備知識

2.1 超圖

設V=(v1,v2,…,vn)是一個有限集。若ei≠?(i= 1,2,…,|E|)，且，則稱二元關系H=(V,E)為超圖。其中V={v1,v2,…,vi,…}(1≤i≤|V|)是超圖中所有節(jié)點的集合；E={e1,e2,…,ej,…}(1≤j≤|E|)是超圖中所有超邊的集合；|V|表示超圖H中節(jié)點的數目，稱為H的階；|E|表示超圖H中超邊的數目。若兩個節(jié)點屬于同一條超邊，則稱這兩個節(jié)點鄰接；若兩條超邊的交集非空，則稱這兩條超邊鄰接。

定義1[11]（關聯矩陣，correlation matrix）超圖H=(V,E)的關聯矩陣C(H)是|V|×|E|的矩陣，若節(jié)點vi包含在超邊ej中，則Cij=1，否則，Cij=0。

定義2[22]（節(jié)點度，node degrees）超圖H=(V,E)的節(jié)點度為該超邊連接的節(jié)點數目，記為dHd(ei)。在超圖的關聯矩陣C(H)中，節(jié)點度即是對應的列中非零元素的數目，即：

定義3[22]（節(jié)點超度，node hyperdegrees）超圖H=(V,E)的節(jié)點超度為包含該節(jié)點的超邊數目，記為dHhd(vi)。在超圖的關聯矩陣C(H)中，節(jié)點超度即是對應的行中非零元素的數目，即：

定義4（超邊度，hyperedge degrees）超圖H=(V,E)的超邊度為超邊所鄰接的其他超邊的數目，即與該超邊至少存在1個公共節(jié)點的超邊數，記為dHed(ei)。在超圖的關聯矩陣C(H)中，超邊度即是與對應的列非正交的列數目，即：

胡楓等人在文獻[22]中將超邊度定義為除去該超邊所對應的列外與此列非正交的列的數目。本文將超邊度定義為超圖的關聯矩陣中所有的列與該超邊所對應的列非正交的列的數目。由于非零列與自身一定非正交，本文中的超邊度相當于在文獻[22]的基礎上增加了1。

基于節(jié)點度、節(jié)點超度和超邊度的定義，可分別得到節(jié)點度分布、節(jié)點超度分布和超邊度分布的定義。

定義5（節(jié)點度分布，node degrees distribution）超圖H=(V,E)的節(jié)點度分布是指超圖H中節(jié)點度的概率分布或頻率分布。

定義6（節(jié)點超度分布，node hyperdegrees distribution）超圖H=(V,E)的節(jié)點超度分布是指超圖H中節(jié)點超度的概率分布或頻率分布。

定義7（超邊度分布，hyperedge degrees distribution）超圖H=(V,E)的超邊度分布是指超圖H中超邊度的概率分布或頻率分布。

文獻[10]提出用圖的節(jié)點度分布多項式描述圖的節(jié)點度分布。這里將圖的度分布多項式應用到超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布中，分別得到超圖的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式。

定義8（節(jié)點度分布多項式，node degrees distribution polynomial）超圖H=(V,E)的節(jié)點度分布多項式是指以超圖H中節(jié)點度的頻數為系數，以節(jié)點度為次數的單項式組成的多項式。

定義9（節(jié)點超度分布多項式，node hyperdegrees distribution polynomial）超圖H=(V,E)的節(jié)點超度分布多項式是指以超圖H中節(jié)點超度的頻數為系數，以節(jié)點超度為次數的單項式組成的多項式。

定義10（超邊度分布多項式，hyperedge degrees distribution polynomial）超圖H=(V,E)的超邊度分布多項式是指以超圖H中超邊度的頻數為系數，以超邊度為次數的單項式組成的多項式。

基于式（1）、式（2）和式（3），對超圖H=(V,E)而言，其節(jié)點度分布多項式PolyHd(H)、節(jié)點超度分布多項式PolyHhd(H)和超邊度分布多項式PolyHed(H)表述如下：

對式（4）中的節(jié)點度分布多項式PolyHd(H)進行分析，則可以得到如下結論：

對式（4）中的節(jié)點超度分布多項式PolyHhd(H)進行分析，則可以得到如下結論：

對式（4）中的超邊度分布多項式PolyHed(H)進行分析，則可以得到如下結論：

更進一步地分析，可以得到如下結論：

定義11[12]（一致超圖，uniform hypergraph）若超圖H=(V,E)中所有的超邊均包含相同數目的節(jié)點，則H稱為一致超圖，也稱為均勻超圖。若H所有的超邊均包含n個節(jié)點，則稱為n-均勻超圖。

顯然，2-均勻超圖就是通常意義上的圖。對2-均勻超圖而言，其節(jié)點度就是通常意義上圖的度。

定義12（超圖密度，hypergraph gensity）超圖H= (V,E)的密度是指超圖H中所有超邊包含的節(jié)點數目之和與最多可包含的節(jié)點數目總和的比值，表述為Gensity(H)。

由于一般情況下，超圖H至少含有1條非空超邊，故通常情況下，0〈Gensity(H)≤1。

2.2 分形理論

分形幾何學是分形理論的數學基礎，分形信息、分形設計和分形藝術等均由分形幾何衍生而出[26]。分形理論最基本特點是用分數維度的視角和數學方法對客觀事物進行分析研究，Cantor集、Koch雪花和Menger海綿等是常見的分形圖形。

定義13[27]分形矩陣是通過對初始矩陣進行迭代相加運算而生成的一系列具有分形特性的矩陣。

最初將分形矩陣應用于圖案生成中[28]。對一個給定的矩陣Am×n而言，分別用A的每一個元素aij(1≤i≤m,1≤j≤n)加上A的每一個元素所得到的矩陣去置換元素aij，得到一個局部與整體相似的新的矩陣，其整體結構具備與A相同的特性。令上述變換持續(xù)進行下去，可以得到一系列自相似的矩陣,…，其中是由的每一個元素與A相加后置換而成。上述迭代操作得到的一系列矩陣,…就是分形矩陣。文獻[29]指出，迭代Kronecker積運算生成的矩陣也是分形矩陣。文獻[10]提出分形矩陣形式的鄰接矩陣對應的網絡也是分形的，并指出對一個簡單初始網絡鄰接矩陣進行迭代Kronecker積運算，可得到一個分形維數不超過2的自相似網絡；對多個簡單初始網絡鄰接矩陣進行順次Kronecker和運算，可得到一個度分布呈正態(tài)分布的隨機網絡。這里將矩陣運算應用于超圖的關聯矩陣中。

2.3 矩陣理論

由于超圖的關聯矩陣中每一列代表一條超邊，通常情況下可將超圖的關聯矩陣視為分塊矩陣，其每一個分塊矩陣均代表一條超邊的列矩陣。類似于基于圖的鄰接矩陣的矩陣運算有Kronecker積運算及Kronecker和運算。對分塊矩陣形式的超圖的關聯矩陣而言，基于Kronecker積運算還有另外兩種積運算與對應的和運算，分別是Tracy-Singh積運算與Khatri-Rao積運算及Tracy-Singh和運算與Khatri-Rao和運算。Tracy-Singh積運算與Khatri-Rao積運算及Tracy-Singh和運算與Khatri-Rao和運算分別是Kronecker積運算及Kronecker和運算的變種。

矩陣A與B的Tracy-Singh積運算[30]表述為：

矩陣A與B的Tracy-Singh和運算[30]表述為：

矩陣A與B的Khatri-Rao積運算[31]表述為：

矩陣A與B的Khatri-Rao和運算[31]表述為：

Tracy-Singh積運算與Tracy-Singh和運算是將一個分塊矩陣中的每一個分塊與另一個分塊矩陣中的每一分塊進行運算，得到的新的分塊矩陣的分塊數目是兩個分塊矩陣分塊數目的乘積。Khatri-Rao積運算與Khatri-Rao和運算只是將一個分塊矩陣中的一個分塊與另一分塊矩陣中對應的分塊進行運算，得到的新的分塊矩陣的分塊數目與參與運算的兩個分塊矩陣的分塊數目相同。本文只考慮基于超圖關聯矩陣的Tracy-Singh積運算與Tracy-Singh和運算的超網絡構建方法，至于基于超圖關聯矩陣的Khatri-Rao積運算與Khatri-Rao和運算的超網絡構建方法將另文撰述。

3 基于矩陣運算的超網絡模型構建

3.1 基于矩陣運算的自相似超網絡模型構建

本文將分塊矩陣的Tracy-Singh積運算應用于超圖的關聯矩陣中，得到一種基于矩陣運算的自相似超網絡構建方法。

給定一個簡單超圖H=(V,E)，其對應的關聯矩陣為Cm×n，分別用C的每一列cj(1≤j≤n)乘以C的每一列所得到的矩陣去置換元素cj，得到一個局部與整體相似的自相似矩陣。令此變換過程不斷進行下去，得到一系列自相似矩陣（對應于C的迭代Tracy-Singh積運算）。將這些自相似矩陣視為關聯矩陣，其對應的超圖就是H的迭代Tracy-Singh積超圖。該超圖具有自相似特性，即是自相似超網絡。

Liu在文獻[32]中論證了矩陣Tracy-Singh積運算與Khatri-Rao積運算的部分性質。在將超圖的關聯矩陣視為列矩陣組成的分塊矩陣時，其Tracy-Singh積運算的結果等效于Kronecker積運算的結果。可以采用類似于文獻[10]中圖的鄰接矩陣的Kronecker積運算的分析方法對超圖關聯矩陣的Tracy-Singh積運算進行分析。

對超圖H=(V,E)及其對應的關聯矩陣C而言，經過一次Tracy-Singh積運算后可以得到新的超圖H(1)=(V(1),E(1))及其對應的關聯矩陣C(1)。由于超圖關聯矩陣的行數代表超圖的節(jié)點數目，而列數代表超圖的超邊數目，非零元素的數目與所有元素的數目之比代表超圖的密度，于是有|V(1)|=|V|×|V|=|V|2，|E(1)|=|E|×|E|=(|E|)2，對超圖密度而言，則有Gensity(H(1))=Gensity(H)×Gensity(H)。依此類推，可以得到：

H(i)可簡記為如下形式：

對式（13）進行分析，隨著迭代次數i的增大，在i→∞時，得到的超網絡節(jié)點數目、超邊數目和密度為：

式（15）說明一個超圖的迭代Tracy-Singh積超圖在迭代次數趨近于無窮時，其節(jié)點數和超邊數均趨近于無窮，而其密度取決于初始超圖的密度。

超圖的節(jié)點度分布多項式中單項式的次數代表超圖的節(jié)點度，節(jié)點度分布多項式同時表述了初始超圖的節(jié)點度分布及超圖迭代Tracy-Singh積超圖的節(jié)點度分布?？梢酝ㄟ^對初始超圖節(jié)點度分布多項式的運算得到超圖迭代Tracy-Singh積超圖的節(jié)點度分布多項式。對節(jié)點超度分布多項式及超邊度分布多項式的分析類似，于是可以得到如下定理。

定理1一個超圖的迭代Tracy-Singh積超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布可分別通過其節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式的系數相乘次數相乘的運算得到。

證明由于Tracy-Singh積運算是將一個分塊矩陣的每一個分塊與另一個分塊矩陣的每一個分塊分別進行Kronecker積運算，對于全部由列矩陣組成的分塊矩陣而言，其Tracy-Singh積運算的結果等效于Kronecker積運算的結果。所得到的Tracy-Singh積運算的結果中每一列非零元素的數目就是超邊對應的節(jié)點度，每一行中非零元素的數目就是節(jié)點對應的節(jié)點超度，與每一列非正交的列的數目就是超邊對應的超邊度。以節(jié)點度為例，若將矩陣每一列中非零元素的數目視為單項式的次數，在采用節(jié)點度分布多項式表述超圖的節(jié)點度分布時，關聯矩陣中列與列相乘反映到節(jié)點度分布多項式中就是次數與次數相乘，也即新得到的Tracy-Singh積超圖的節(jié)點度分布多項式可視為初始超圖節(jié)點度分布多項式系數相乘次數相乘的運算。對節(jié)點超度分布及超邊度分布的分析與之類似。定理1得證。 □

根據定理1，若超度H的節(jié)點度分布、節(jié)點超度分布和超邊度分布表述如式（4）所示，則對超圖H(1)而言，其節(jié)點度分布、節(jié)點超度分布和超邊度分布表述如下：

在通過Tracy-Singh積運算構建自相似超網絡時，采用式（16），可以從理論上嚴格計算出新生成的自相似超網絡的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式，得到其節(jié)點度分布、節(jié)點超度分布和超邊度分布?？蓪⒍ɡ?進行推廣并應用到不同超圖的Tracy-Singh積運算中。

在分形理論中，分形維數是對分形圖形進行度量的重要參數。由于關聯矩陣與超網絡的一一對應關系，對自相似超網絡及其關聯矩陣而言，它們的分形維數是相等的?？梢詫ΤW絡關聯矩陣的分形維數進行分析以間接得到超網絡的分形維數。下文基于分形維數的定義，對此類自相似超網絡的分形維數進行分析。

對于m×n的矩陣Am×n而言，基于A得到規(guī)模是其k倍的(mk)×(nk)矩陣需要k2個A進行簡單的拼接。對于“拼接”這種操作（運算）而言，其分形維數表述如下：

于是，基于分形維數的計算方法，可以得出如下定理。

定理2一個超圖的迭代Tracy-Singh積超圖的分形維數為其超邊包含的節(jié)點數之和的對數值和節(jié)點數與超邊數乘積對數值的比值的兩倍，即：

證明將Tracy-Singh積運算應用于超圖H=(V,E)的關聯矩陣C|V|×|E|時，以H(1)為例，其對應的關聯矩陣為，從統計意義上可以認為其規(guī)模是C|V|×|E|的倍。但在運算過程中，只有在C(i,j)=1時才需要用C|V|×|E|替換C(i,j)，共需要個C|V|×|E|進行選擇性的“拼接”。定理2得證。 □

定理3一個超圖的迭代Tracy-Singh積超圖的分形維數不超過2。

證明對于超圖H=(V,E)而言，即有，根據式（18），則有：

定理3得證。 □

一般情況下，對于超圖H=(V,E)而言，ei≠?(i= 1,2,…,|E|)。于是，基于定理3可以得出如下的引理。

引理1一個非空超圖的迭代Tracy-Singh積超圖的分形維數介于0到2之間。

證明對于非空超圖H=(V,E)而言，有，根據式（18），則有：

結合式（19），即有0〈FD(H)≤2。引理1得證。□

超圖是圖的超集，文獻[10]基于圖的鄰接矩陣的迭代Kronecker積圖形式的自相似網絡的分形維數介于1到2之間，此處基于超圖的關聯矩陣的迭代Tracy-Singh積超圖形式的自相似超網絡的分形維數介于0到2之間。可以發(fā)現，自相似超網絡的分形維數涵蓋了自相似網絡的分形維數，這從一個側面詮釋了超圖是圖的超集，圖是超圖的特例。

另外，一個分塊矩陣的迭代Tracy-Singh積運算的結果也是分塊矩陣，對基于超圖關聯矩陣的迭代Tracy-Singh積運算得到的分塊矩陣進行分析，則可以得出如下定理。

定理4一個連通且非二分超圖的迭代Tracy-Singh積超圖的直徑不超過初始超圖直徑的兩倍。

證明設超圖H=(V,E)的直徑為d，則通過其任一節(jié)點均可在不超過d步內到達另一節(jié)點。在經過一次Tracy-Singh積運算得到的H(1)中，其對應的關聯矩陣C(H(1))中分塊矩陣內部的每一個節(jié)點也可在不超過d步內到達此分塊矩陣內部的另一節(jié)點，而且一個分塊矩陣也可在不超過d步內到達另一個分塊矩陣，也即H(1)的直徑不超過2d。由于應用Tracy-Singh積運算得到的超圖H(i)(i≥1)對應的關聯矩陣均是分塊矩陣，則上述分析對任意的i(i≥1)均成立，即基于一個超圖的關聯矩陣的迭代Tracy-Singh積運算得到的Tracy-Singh積超圖的直徑均不超過2d。定理4得證。 □

注1定理4表明一個連通且非二分超圖的迭代Tracy-Singh積超圖的直徑均相等，于是在具體的計算中只需要對H(1)的直徑進行計算就可以得出所有此類自相似超網絡的直徑。

注2定理4只對連通且非二分超圖成立，對非連通超圖或二分超圖不成立，因為二分超圖的迭代Tracy-Singh積超圖是非連通超圖，而非連通超圖的直徑是無窮大。

更深入地分析，可以得到如下定理。

定理5一個n階n-均勻超圖的迭代Tracy-Singh積超圖的直徑恒為1，密度也恒為1。

證明n階n-均勻超圖的關聯矩陣為全1矩陣，故其密度為1。從該超圖的任一節(jié)點出發(fā)，可經1步到達其他任一節(jié)點，故其直徑也為1。其迭代Tracy-Singh積超圖的關聯矩陣為全1矩陣，其密度也為1。從該全1矩陣對應的超網絡的任一節(jié)點出發(fā)，均可經1步到達其他任一節(jié)點，故其直徑也為1。定理5得證。 □

為更直觀地刻畫自相似超網絡在不同維度下的度量情況，將一個連通且非二分超圖的迭代Tracy-Singh積超圖對應的自相似超網絡與文獻[10]中的自相似網絡進行對比，對比結果如表1所示。

Table 1 Comparison between self-similarity hypernetwork and self-similarity network表1 自相似超網絡與自相似網絡對比表

從表1中可以看出，在維度為1時，自相似超網絡的節(jié)點數和超邊數與自相似網絡的節(jié)點數和邊數均趨近于無窮；在維度為2時，自相似超網絡和自相似網絡的直徑均不超過初始超圖或初始圖直徑的兩倍。本文所構建的自相似超網絡具有與自相似網絡類似的特性。

從定理2可知，自相似超網絡的分形維數只與初始超圖的節(jié)點數、超邊數和超邊包含的節(jié)點數之和有關，可能存在多個拓撲結構不同的超圖卻擁有相同的節(jié)點數和超邊數，且超邊包含的節(jié)點數之和相等，也可能存在多個拓撲結構不同且節(jié)點數與超邊數及超邊包含的節(jié)點數之和也不同但分形維數卻相同的超圖，給出下述定義。

定義14（準自相似超網絡，quasi self-similarity hypernetwork）準自相似超網絡是指由多個節(jié)點數和超邊數相等且超邊包含的節(jié)點數之和也相等的初始超圖對應的關聯矩陣，通過Tracy-Singh積運算而得到的Tracy-Singh積超圖。

定義15（泛自相似超網絡，pan self-similarity hypernetwork）泛自相似超網絡是指由多個超邊包含的節(jié)點數之和的對數值及節(jié)點數與超邊數乘積對數值的比值的兩倍相等的初始超圖所對應的關聯矩陣，通過Tracy-Singh積運算而得到的Tracy-Singh積超圖。

對準自相似超網絡和泛自相似超網絡進行分析，可以得到下述結論。

定理6準自相似超網絡的分形維數等于對應的自相似超網絡的分形維數。

證明根據定理2及式（10），自相似超網絡的分形維數只與初始超圖的節(jié)點數、超邊數和超邊包含的節(jié)點數之和有關。又根據定理1及式（16），準自相似超網絡的節(jié)點數、超邊數和超邊包含的節(jié)點數之和與對應的自相似超網絡的節(jié)點數、超邊數和超邊包含的節(jié)點數之和均相等。因此，準自相似超網絡的分形維數與對應的自相似超網絡的分形維數也相等。定理6得證。 □

引理2泛自相似超網絡的分形維數等于對應的準自相似超網絡的分形維數。

證明與定理6證明類似。 □

將超網絡記為全集U，自相似超網絡記為USS，準自相似超網絡記為UQSS，泛自相似超網絡記為UPSS，則可以得到如下定理。

定理7USS是UQSS的子集，UQSS是UPSS的子集，UPSS是U的子集，用公式表述為：

證明易證其成立。 □

3.2 基于矩陣運算的隨機超網絡模型構建

基于矩陣運算的隨機超網絡模型構建方法如下所示：對于一系列隨機選擇的初始超圖H(1),H(2),…,,…來說，將Tracy-Singh和運算順次應用于上述超圖對應的關聯矩陣可以得到一個新的矩陣，該矩陣對應的超網絡是上述超圖的Tracy-Singh和超圖，即為隨機超網絡。

對于隨機選擇的初始超圖H=(V,E)來說，可以認為其節(jié)點度分布、節(jié)點超度分布和超邊度分布均是隨機的，即均服從正態(tài)分布。而節(jié)點度、節(jié)點超度和超邊度在其對應的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式中即是對應的單項式次數，故反映在節(jié)點度分布多項式PolyHd(H)、節(jié)點超度分布多項式PolyHhd(H)和超邊度分布多項式PolyHed(H)中，則是各個單項式的次數服從正態(tài)分布。

對兩個超圖Ha=(Va,Ea)、Hb=(Vb,Eb)及對應的節(jié)點度分布多項式PolyHd(Ha)與PolyHd(Hb)、節(jié)點超度分布多項式PolyHhd(Ha)與PolyHhd(Hb)、超邊度分布多項式PolyHed(Ha)與PolyHed(Hb)來說，將Tracy-Singh積運算應用于Ha與Hb對應的關聯矩陣所得到的Tracy-Singh積超圖Hab的節(jié)點度分布、節(jié)點超度分布和超邊度分布可分別通過PolyHd(Ha)與PolyHd(Hb)、PolyHhd(Ha)與PolyHhd(Hb)及PolyHed(Ha)與PolyHed(Hb)的 Tracy-Singh積運算得到，即有：

超圖Hab的節(jié)點度分布、節(jié)點超度分布和超邊度分布在其節(jié)點度分布多項式PolyHd(Hab)、超度分布多項式PolyHhd(Hab)和超邊度分布多項式PolyHed(Hab)中也是其對應的單項式次數。從式（22）可以看出，兩個相同或不同超圖的Tracy-Singh積超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布均可以視為初始超圖節(jié)點度分布、節(jié)點超度分布和超邊度分布的非線性組合。對于將Tracy-Singh和運算應用于兩個超圖的關聯矩陣所得到的新矩陣可以視為一個矩陣的每一列加上另一個矩陣的每一列，類似于Tracy-Singh積運算對超圖的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式的處理，將Tracy-Singh和運算應用于Ha與Hb對應的關聯矩陣所得到的Tracy-Singh和超圖Hab′的節(jié)點度分布、節(jié)點超度分布和超邊度分布可以通過下式得到：

式（23）中節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式的運算即是通常的多項式乘法?？梢钥闯觯愃朴趯racy-Singh積運算采用系數相乘次數相乘的運算，對Tracy-Singh和運算采用系數相乘次數相加的運算也可以得到所生成的超網絡的節(jié)點度分布、節(jié)點超度分布和超邊度分布?？梢詫蓚€相同或不同超圖的Tracy-Singh積超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布視為初始超圖節(jié)點度分布、節(jié)點超度分布和超邊度分布的非線性組合，并將兩個相同或不同超圖的Tracy-Singh和超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布視為初始超圖節(jié)點度分布、節(jié)點超度分布和超邊度分布的線性組合。對于隨機選擇的初始超圖來說，其節(jié)點度分布、節(jié)點超度分布和超邊度分布可以視為均服從正態(tài)分布。由于有限個正態(tài)分布的線性組合也是正態(tài)分布，基于多個初始超圖的Tracy-Singh和超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布也服從正態(tài)分布。

在初始超圖集合{H1,H2,…,Hi,…}中，對于順次選擇的H(1),H(2),…,H(i),…,H(n)并進行Tracy-Singh和運算得到的Tracy-Singh和超圖H(n)來說，其節(jié)點數、超邊數和密度可通過度分布多項式得到：

H(n)可簡記為如下形式：

3.3 不同組合的超網絡模型

前面分析了基于一個簡單初始超圖的迭代Tracy-Singh積運算可以得到自相似超網絡，基于多個簡單初始超圖的Tracy-Singh和運算可以得到隨機超網絡。其實也可以基于一個初始超圖進行迭代Tracy-Singh和運算或多個初始超圖進行Tracy-Singh積運算。當然，也可以同時應用Tracy-Singh積運算及Tracy-Singh和運算。將上述超網絡構建方法進行推廣，可以得到一般情況下基于矩陣運算的超網絡構建方法。基于一個、有限多個，乃至無窮多個初始超圖的Tracy-Singh積運算和/或Tracy-Singh和運算共有9種組合，如表2所示。9種組合之間的關系如圖1所示。

Table 2 Statistics of 9 combinations of hypernetwork based on matrix operation表2 基于矩陣運算的9種組合超網絡統計表

4 基于矩陣運算的超網絡理論分析

4.1 基于矩陣運算的超網絡數量分析

在基于矩陣運算的超網絡構建中，可以對初始超圖節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式進行計算以得到Tracy-Singh積超圖及Tracy-Singh和超圖的節(jié)點度分布多項式、節(jié)點超度分布多項式及超邊度分布多項式，隨之得到其節(jié)點度分布、節(jié)點超度分布和超邊度分布。由于超圖的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式無法反映超圖的拓撲結構，一個相同的節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式組合可能對應多個拓撲結構不同的超圖。

化學中描述化合物時需要分子式，但由于同分異構現象的存在，在描述化合物時，還需要結構式。一個相同的分子式可能對應多個不同的結構式，通過度分布多項式組合描述超網絡與之類似。分子式對應于超網絡的度分布多項式組合，而結構式對應于超網絡的拓撲結構。與分子式對于結構式存在數量規(guī)律類似，節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式組合對于超網絡的拓撲結構也存在數量規(guī)律。本文對基于矩陣運算的超網絡數量進行研究，得到如下結論。

Fig.1 Relation of 9 combinations of hypernetwork圖1 超網絡9種組合關系圖

定理8超網絡的數量不超過其節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式對應的復雜網絡數量的乘積，即：證明對于超圖H=(V,E)而言，其節(jié)點度分布、節(jié)點超度分布和超邊度分布并不完全獨立，三者之間存在一定的耦合關系，故超圖的數量不超過其節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式對應的復雜網絡數量的乘積。定理8得證。 □

注3定理8說明在難以直接計算一類節(jié)點度分布、節(jié)點超度分布和超邊度分布組合已知的超網絡數量時，可以通過計算其節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式對應的復雜網絡的數量而間接得到該類超網絡數量的上界，但仍未從根本上解決超網絡的數量問題。對此類超網絡的數量規(guī)律進行深入分析是后續(xù)研究的重要內容。

4.2 基于矩陣運算的超網絡擾動與穩(wěn)定分析

超網絡擾動與穩(wěn)定分析主要分析初始超圖的波動對基于矩陣運算得到的超網絡的影響，尤其是在增加或刪除一個節(jié)點或一條超邊及超邊包含的節(jié)點變動時對超網絡總體特性的影響。下面先分析其對自相似超網絡的影響，包括分形維數、網絡直徑和度分布三方面的影響。

式（18）給出了基于初始超圖H=(V,E)生成的自相似超網絡分形維數，對增加或刪除一個節(jié)點或一條超邊及超邊包含的節(jié)點變動對其分形維數的影響分析可以轉化為對其分形維數的一階導數進行分析。將式（5）及式（6）代入式（18），得到分形維數的一階導數如下：

對于一個給定的超圖H=(V,E)而言，其節(jié)點數|V|及超邊數|E|是確定的。PolyHhd′(H)|x=1等于關聯矩陣中非零元素的數目，是一個常數。分形維數的一階導數dFD(H)|x=1取決于PolyHhd′(H)|x=1的取值，故分形維數與節(jié)點超度分布多項式的二階導數密切相關。于是，在增加或刪除一個節(jié)點或一條超邊及超邊包含的節(jié)點變動時，可以通過對節(jié)點超度分布多項式的計算近似得到分形維數的變化情況。

對自相似超網絡直徑的影響而言，由于直徑尚無類似于分形維數的顯式函數可以表述，故無法通過類似于分形維數的分析方法進行論述。但由于自相似超網絡的直徑不超過初始超圖直徑的兩倍，而且初始超圖中超邊包含的節(jié)點變動對初始超圖的直徑沒有顯著的影響，可通過添加或刪除一個節(jié)點或一條超邊時對初始超圖直徑的影響來進行間接的分析。由于添加與刪除是相對的，這里只分析添加即可，于是可得到如下結論。

定理9向初始超圖添加一個節(jié)點后，自相似超網絡直徑的增加量不超過2。

證明向初始超圖添加一個節(jié)點后，初始超圖中節(jié)點之間的最短距離不受影響，但初始超圖中任一節(jié)點與新增節(jié)點的距離不超過初始超圖的直徑加1，故自相似超網絡直徑的增加量不超過2。定理9得證。 □

定理10向初始超圖添加一條超邊后，自相似超網絡直徑的減少量不超過一半。

證明向初始超圖添加一條超邊后，初始超圖中鄰接的節(jié)點距離不發(fā)生變化，初始超圖中不鄰接的節(jié)點在添加超邊后會導致初始超圖中至少增加一個回路，回路中任意兩個節(jié)點間的距離不超過節(jié)點數目的一半，故初始超圖直徑的減少量不超過一半，自相似超網絡直徑的減少量也不超過一半。定理10得證。 □

由于添加或刪除一個節(jié)點或一條超邊時對初始超圖直徑的影響存在確定的上限，故對最終生成的自相似超網絡直徑的影響也存在確定的上限。

對自相似超網絡節(jié)點度分布、節(jié)點超度分布和超邊度分布的影響而言，在具體的計算中是將節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式進行類似多項式乘法的系數相乘次數相乘的運算，將式（22）代入式（5）、式（6）和式（7）得到：

從式（28）可以看出，在添加或刪除一個節(jié)點或一條超邊時無法使用微分公式進行增量式的更新，即其不可微。故初始狀況下添加或刪除一個節(jié)點或一條超邊時的細微差異會在以后隨著迭代次數的增長而由于連鎖反應會無限放大。

下面對隨機超網絡的影響進行分析，主要是對隨機超網絡節(jié)點度分布、節(jié)點超度分布和超邊度分布的影響。對隨機超網絡而言，在具體的計算中是將節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式進行通常多項式乘法的系數相乘次數相加的運算。將式（23）代入式（5）、式（6）和式（7）得到：

從式（29）可以看出，在添加或刪除一個節(jié)點或一條超邊時可以使用微分公式進行增量式的更新，即其可微。故初始狀況雖然選用不同類型的超圖，但最終生成的隨機超網絡節(jié)點度分布、節(jié)點超度分布和超邊度分布的形態(tài)相同，均呈鐘形的正態(tài)分布。

通過將微積分的工具與方法應用于超網絡模型擾動與穩(wěn)定的分析中，得到了一些定量的結論，但對超網絡模型擾動與穩(wěn)定的機理仍未透徹了解。后續(xù)工作的重點是繼續(xù)深入利用微分方程和李雅普諾夫穩(wěn)定性理論等對此進行深入的研究。

5 基于矩陣運算的超網絡仿真實驗

Fig.2 6 different initial hypernetworks圖2 6個不同初始超圖

本文選取6個簡單的初始超圖，如圖2所示；其對應的信息及其生成的自相似超網絡分形維數及網絡直徑如表3所示；其迭代20次后得到的自相似超網絡節(jié)點度分布、節(jié)點超度分布和超邊度分布分別如圖3、圖4和圖5所示。

從圖3、圖4和圖5中可以看出，基于一個簡單初始超圖的迭代Tracy-Singh積超圖的節(jié)點度分布、節(jié)點超度分布和超邊度分布不同于經典的ER隨機網絡的泊松分布、WS小世界網絡的指數分布和BA無標度網絡的冪律分布，這體現了其自相似超網絡的特性。在圖2中，Ha、Hb、Hc、Hd、He、Hf這6個初始超圖之間只存在一個節(jié)點或一條超邊的微小差異，但在圖3、圖4、圖5中迭代20次后得到的自相似超網絡的節(jié)點度分布、節(jié)點超度分布和超邊度分布卻差異巨大，其中Hb與Hc之間只存在一個節(jié)點及一條超邊的差異，Ha與Hb只存在一條超邊的差異，最終得到的結果卻極為巨大。呈現出典型的“蝴蝶效應”特點。這其實就是超網絡的“變數”。

同時，通過分析表3可以發(fā)現，在增加或刪除一個節(jié)點或一條超邊時，對最終得到的自相似超網絡的分形維數影響不大，而且添加或刪除節(jié)點對添加或刪除超邊對分形維數的影響更大，這可以通過表3中分形維數差別不大體現出來。而且，其對超網絡直徑的影響也是有限的，這可以通過表3中超網絡直徑的差別不超過2體現出來。這其實就是超網絡的“定數”。定數與變數共存是超網絡的特點，也是所有復雜網絡與復雜系統的特點。

Table 3 Statistics of 6 different initial hypergraphs表3 6個不同初始超圖統計表

Fig.3 Node degrees distributions of self-similarity hypernetworks based on 20 times iteration of 6 initial hypergraphs圖3 6個初始超圖迭代20次后得到的自相似超網絡節(jié)點度分布

Fig.4 Node hyperdegrees distributions of self-similarity hypernetworks based on 20 times iteration of 6 initial hypergraphs圖4 6個初始超圖迭代20次后得到的自相似超網絡節(jié)點超度分布

Fig.5 Hyperedge degrees distributions of self-similarity hypernetworks based on 20 times iteration of 6 initial hypergraphs圖5 6個初始超圖迭代20次后得到的自相似超網絡超邊度分布

同樣基于圖2中的6個初始超圖，從中依次選取20個，允許重復選取，共選取6次，分別記為，選擇次序如表4所示，得到的隨機超網絡的節(jié)點度分布、節(jié)點超度分布和超邊度分布分別如圖6、圖7和圖8所示。

從圖6、圖7、圖8中可以看出，對隨機選擇的20個初始超圖對應的關聯矩陣進行Tracy-Singh和運算得到的超網絡的節(jié)點度分布、節(jié)點超度分布和超邊度分布均呈鐘形的正態(tài)分布，這驗證了有限個正態(tài)分布的線性組合仍是正態(tài)分布，也驗證了對多個簡單初始超圖對應的關聯矩陣進行Tracy-Singh和運算可以得到隨機超網絡。

Fig.6 Node degrees distributions of random hypernetworks based on 20 initial hypergraphs selected randomly圖6 隨機選擇20個初始超圖后得到的隨機超網絡節(jié)點度分布

Table 4 6 random hypernetworks and corresponding 20 initial hypergraphs表4 6個隨機超網絡對應的20個初始超圖選擇表

6 結束語

對超網絡的關聯矩陣進行運算以構建超網絡是一種新興方法。本文將Tracy-Singh積運算及Tracy-Singh和運算應用于超網絡的關聯矩陣中，重點研究了兩類超網絡——自相似超網絡與隨機超網絡的構建方法，并借助于節(jié)點度、節(jié)點超度和超邊度對所構建的超網絡進行分析。自相似超網絡的自相似特性源于分形矩陣形式的關聯矩陣，可以通過對一個簡單初始超圖的關聯矩陣進行迭代的Tracy-Singh積運算得到；隨機超網絡的隨機特性源于有限個正態(tài)分布的線性組合，可以通過對多個簡單初始超圖的關聯矩陣進行順次的Tracy-Singh和運算得到。對自相似超網絡而言，其分形維數不超過2，且當初始超圖為連通且非二分超圖時同時具有小世界特性；對隨機超網絡而言，其節(jié)點度分布、節(jié)點超度分布和超邊度分布均呈鐘形的正態(tài)分布?；诰仃囘\算所構建的超網絡的節(jié)點度分布、節(jié)點超度分布和超邊度分布可通過對節(jié)點度分布多項式、節(jié)點超度分布多項式和超邊度分布多項式的運算得到。本文對超網絡的數量及擾動與穩(wěn)定等其他特性進行了一定程度的定量分析。后續(xù)研究的重點在于結合實際超網絡的特點對基于矩陣運算所構建超網絡的各項特性進行深入的分析研究，并探討其在數據挖掘及真實網絡與真實系統中的應用。

Fig.7 Node hyperdegrees distributions of random hypernetworks based on 20 initial hypergraphs selected randomly圖7 隨機選擇20個初始超圖后得到的隨機超網絡節(jié)點超度分布

Fig.8 Hyperedge degrees distributions of random hypernetworks based on 20 Initial hypergraphs selected randomly圖8 隨機選擇20個初始超圖后得到的隨機超網絡超邊度分布

[1]Erdos P,Renyi A.On random graphs I[J].Publicationes Mathematicae,1959,6:290-297.

[2]Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393:440-442.

[3]Newman M E J,Watts D J.Renormalization group analysis of the small-world network model[J].Physics Letter A,1999, 263(4/6):341-346.

[4]Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[5]Song C,Jalvin S,Makse H A.Self-similarity of complex networks[J].Nature,2005,433:392-395.

[6]Rudolph L M,Muller L E.Algebraic approach to small-world network models[J].Physical Review E,2014,89(1):012812.

[7]Emmerich T,Bunde A,Havlin S.Structural and functional properties of spatially embedded scale-free networks[J].Physical Review E,2014,89(6):062806.

[8]Zhang Siying.The law of emergence of self-similar structures in complex systems and complex networks[J].Complex Systems and Complex Science,2006,3(4):41-51.

[9]Jalan S,Bandyopadhyay J N.Random matrix analysis of complex networks[J].Physical Review E,2007,76(4):046107.

[10]Liu Shengjiu,Li Tianrui,Horng Shijinn,et al.Research on complex network construction based on matrix operation[J]. Scientia Sinica Informationis,2016,46(5):610-626.

[11]Berge C.Graphs and hypergraphs[M].2nd ed.New York: Elsevier,1973:389-413.

[12]Berge C.Hypergraphs:combinatorics of finite sets[M].3rd ed.Amsterdam:North-Holl,1989:1-39.

[13]Feng Keqin,Li W C W.Spectra of hypergraphs and applications[J].Journal of Number Theory,1996,60(1):1-22.

[14]Ernesto E,Rodríguez-Velázquez J A.Subgraph centrality in complex networks[J].Physical Review E,2005,71(2):056103.

[15]Ernesto E,Rodríguez-Velázquez J A.Subgraph centrality and clustering in complex hypernetworks[J].Physica A,2006, 364(1):581-594.

[16]Ghoshal G,Zlatic V,Caldarelli G,et al.Random hypergraphs and their applications[J].Physical Review E,2009, 79(6):066118.

[17]Zlatic V,Ghoshal G,Caldarelli G.Hypergraph topological quantities for tagged social networks[J].Physical Review E,2009,80(3):036118.

[18]Neubauer N,Obermayer K.Hyperincident connected components of tagging networks[C]//Proceedings of the 20th ACM Conference on Hypertext and Hypermedia,Torino,Italy,Jun 29-Jul 1,2009.New York:ACM,2009:229-238.

[19]Zhang Zike,Liu Chuang.A hypergraph model of social tagging networks[J].Journal of Statistical Mechanics-theory and Experiment,2010.doi:10.1088/1742-5468/2010/10/ P10005.

[20]Pei Weidong,Xia Wei,Wang Quanlai,et al.Study of a class of dynamic complex network evolving models with a triangular structure[J].Journal of University of Science and Technology of China,2010,40(11):1186-1190.

[21]Wang Jianwei,Rong Lili,Deng Qiuhong,et al.Evolving hypernetwork model[J].European Physical Journal B,2010,77 (4):493-498.

[22]Hu Feng,Zhao Haixing,Ma Xiujuan.An evolving hypernetwork model and its properties[J].Scientia Sinica Physica, Mechanica&Astronomica,2013,43(1):16-22.

[23]Yang Guangyong,Liu Jianguo.A local-world evolving hypernetwork model[J].Chinese Physics B,2014,23(1):018901.

[24]Liu Shengjiu,Li Tianrui.A new hypernetwork model based on matrix operation[C]//Proceedings of the 2015 International Conference on Intelligent Systems and Knowledge Engineering,Taipei,China,Nov 24-27,2015:176-182.

[25]Yang Guangyong,Hu Zhaolong,Liu Jianguo.Knowledge diffusion in the collaboration hypernetwork[J].Physica A, 2015,419:429-436.

[26]Zhu Hua,Ji Cuicui.Fractal theory and its applications[M]. Beijing:Science Press,2011:262-316.

[27]Andre M B.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.

[28]Andre M B.Artistic design with fractal matrices[J].The Visual Computer,1993,9(5):233-238.

[29]Jeffrey S,Jorge S.Two methods for generating fractal[J]. Computers&Graphics,1989,13(2):185-191.

[30]Tracy D S,Singh R P.A new matrix product and its applications in matrix differentiation[J].Statistica Neerlandica, 1972,26(4):143-157.

[31]Khatri C G,Rao C R.Solutions to some functional equations and their applications to characterization of probability distributions[J].Sankhya,1968,30(2):167-180.

[32]Liu Shuangzhe.Matrix result on the Khatri-Rao and Tracy-Singh products[J].Linear Algebra and Its Applications, 1999,289(1/3):267-277.

附中文參考文獻：

[8]張嗣瀛.復雜系統、復雜網絡自相似結構的涌現規(guī)律[J].復雜系統與復雜性科學,2006,3(4):41-51.

[10]劉勝久,李天瑞,洪西進,等.基于矩陣運算的復雜網絡構建方法研究[J].中國科學:信息科學,2016,46(5):610-626.

[20]裴偉東,夏瑋,王全來,等.一類三角形結構動態(tài)復雜網絡演化模型分析[J].中國科學技術大學學報,2010,40(11): 1186-1190.

[22]胡楓,趙海興,馬秀娟.一種超網絡演化模型構建及特性分析[J].中國科學:物理學力學天文學,2013,43(1):16-22.

[26]朱華,姬翠翠.分形理論及其應用[M].北京:科學出版社, 2011:262-316.

LIU Shengjiu was born in 1988.He received the Ph.D.degree in complex network from Southwest Jiaotong University in 2015.Now he is a postdoctoral fellow at School of Information Science and Technology,Southwest Jiaotong University.His research interests include complex network,natural language processing and cloud computing,etc.劉勝久（1988—），男，湖北隨州人，2015年于西南交通大學獲得博士學位，現為西南交通大學信息科學與技術學院博士后，主要研究領域為復雜網絡，自然語言處理，云計算等。

LI Tianrui was born in 1969.He received the Ph.D.degree in data mining from Southwest Jiaotong University in 2002.Now he is a professor and Ph.D.supervisor at Southwest Jiaotong University,IRSS fellow,and the senior member of IEEE,CCF and CAI.His research interests include data mining and knowledge discovery,granular computing and rough sets,cloud computing and big data,etc.

李天瑞（1969—），男，福建莆田人，2002年于西南交通大學獲得博士學位，現為西南交通大學信息科學與技術學院教授、博士生導師，國際粗糙集學會（IRSS）會士，CCF、IEEE和CAI高級會員，主要研究領域為數據挖掘與知識發(fā)現，粒計算與粗糙集，云計算，大數據等。

HORNG Shijinn was born in 1957.He received the Ph.D.degree in computer science from National Tsing Hua University in 1989.Now he is a professor and Ph.D.supervisor at Department of Computer Science and Information Engineering,National Taiwan University of Science and Technology.His research interests include VLSI design,multiprocessing systems and parallel computing,etc.

洪西進（1957—），男，臺灣桃園人，1989年于臺灣清華大學獲得博士學位，現為臺灣科技大學咨訊工程系教授、博士生導師，主要研究領域為VLSI設計，多處理器系統，并行計算等。

WANG Hongjun was born in 1977.He received the Ph.D.degree in computer science from Sichuan University in 2009.Now he is an associate professor and M.S.supervisor at Southwest Jiaotong University,and the member of IEEE,CCF and ACM.His research interests include machine learning,semi-supervised learning and semi-supervised ensemble learning,etc.

王紅軍（1977—），男，四川廣安人，2009年于四川大學獲得博士學位，現為西南交通大學信息科學與技術學院副研究員、碩士生導師，CCF、IEEE和ACM會員，主要研究領域為機器學習，半監(jiān)督學習，半監(jiān)督集成學習等。

ZHU Jie was born in 1973.He is a Ph.D.candidate at Southwest Jiaotong University,and associate professor at Tibetan University.His research interests include data mining and natural language learning,etc.

珠杰（1973—），男，西藏日喀則人，西南交通大學博士研究生，西藏大學副教授，主要研究領域為數據挖掘，自然語言處理等。

Hypernetwork Model and Its Properties*

LIU Shengjiu1,2,LI Tianrui1,2+,HORNG Shijinn1,2,3,WANG Hongjun1,2,ZHU Jie1,2,4
1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China
2.Key Lab of Cloud Computing and Intelligent Technique of Sichuan Province,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
+Corresponding author:E-mail:trli@swjtu.edu.cn

Correlation matrix describes hypernetwork briefly and intuitively.Hypernetwork can be characterized by node degree,node hyperdegree and hyperedge degree.This paper studies hypernetwork especially self-similar hypernetwork and random hypernetwork from the perspective of correlation matrix,and shows several properties of approaches for constructing hypernetwork based on matrix operation.Self-similar hypernetwork can be obtained by Tracy-Singh product on the correlation matrix of a simple initial hypergraph iteratively,and random hypernetwork can be obtained by Tracy-Singh sum on the correlation matrixes of multiple simple initial hypergraphs sequentially.Thefractal dimension of self-similar hypernetworks is no larger than 2.When the initial hypergraph is a connected and nonbipartite hypergraph,the diameter of self-similar hypernetwork does not exceed twice of that of the initial hypergraph, namely,it also shares a small-world property.The distributions of node degrees,node hyperdegrees and hyperedge degrees of random hypernetworks are normal.The results of simulation experiments validate the properties of the constructed hypernetwork.

hypernetwork;matrix operations;self-similar hypernetwork;fractal dimension;random hypernetwork

10.3778/j.issn.1673-9418.1603049

A

：TP393

*The National Natural Science Foundation of China under Grant Nos.61175047,61262058,61152001(國家自然科學基金);the Fund of the State Key Laboratory of Management and Control for Complex Systems,the Institute of Automation,Chinese Academy of Science under Grant No.20110102(中國科學院自動化研究所復雜系統管理與控制重點實驗室開放課題).

Received 2016-02,Accepted 2016-04.

CNKI網絡優(yōu)先出版:2016-04-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160401.1614.010.html

LIU Shengjiu,LI Tianrui,HORNG Shijinn,et al.Hypernetwork model and its properties.Journal of Frontiers of Computer Science and Technology,2017,11(2)：194-211.