劉勝久，李天瑞+，洪西進(jìn),3，王紅軍，珠 杰,4

1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756

2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756

3.臺(tái)灣科技大學(xué) 資訊工程系，臺(tái)北 10607

4.西藏大學(xué) 計(jì)算機(jī)系，拉薩 850000

超網(wǎng)絡(luò)模型構(gòu)建及特性分析*

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

1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756

2.四川省云計(jì)算與智能技術(shù)高校重點(diǎn)實(shí)驗(yàn)室，成都 611756

3.臺(tái)灣科技大學(xué) 資訊工程系，臺(tái)北 10607

4.西藏大學(xué) 計(jì)算機(jī)系，拉薩 850000

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

超網(wǎng)絡(luò)；矩陣運(yùn)算；自相似超網(wǎng)絡(luò)；分形維數(shù)；隨機(jī)超網(wǎng)絡(luò)

1 引言

作為復(fù)雜系統(tǒng)的抽象表述，復(fù)雜網(wǎng)絡(luò)一直受到人們極大的關(guān)注。20世紀(jì)中葉，Erdos和Renyi提出的ER隨機(jī)網(wǎng)絡(luò)模型[1]首開(kāi)復(fù)雜網(wǎng)絡(luò)的系統(tǒng)性研究，并奠定了后續(xù)近半個(gè)世紀(jì)對(duì)復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)。隨后，WS小世界網(wǎng)絡(luò)模型[2]、NW小世界網(wǎng)絡(luò)模型[3]和BA無(wú)標(biāo)度網(wǎng)絡(luò)模型[4]等一些重要的網(wǎng)絡(luò)模型相繼問(wèn)世。

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

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

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

由于超網(wǎng)絡(luò)在描述真實(shí)網(wǎng)絡(luò)方面比通常的網(wǎng)絡(luò)更具優(yōu)勢(shì)，在數(shù)據(jù)挖掘等領(lǐng)域也有著較為廣闊的應(yīng)用前景，引入新的研究方法與策略來(lái)刻畫超網(wǎng)絡(luò)是超網(wǎng)絡(luò)研究的一大趨勢(shì)。鑒于超網(wǎng)絡(luò)的關(guān)聯(lián)矩陣對(duì)應(yīng)于超網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，本文擬從關(guān)聯(lián)矩陣的視角對(duì)超網(wǎng)絡(luò)進(jìn)行研究。主要是通過(guò)矩陣運(yùn)算實(shí)現(xiàn)超網(wǎng)絡(luò)的構(gòu)建，即對(duì)一個(gè)簡(jiǎn)單初始超圖的關(guān)聯(lián)矩陣進(jìn)行迭代Tracy-Singh積運(yùn)算以構(gòu)建自相似超網(wǎng)絡(luò)，并對(duì)多個(gè)簡(jiǎn)單初始超圖的關(guān)聯(lián)矩陣進(jìn)行Tracy-Singh和運(yùn)算以構(gòu)建隨機(jī)超網(wǎng)絡(luò)。同時(shí)給出了自相似超網(wǎng)絡(luò)及隨機(jī)超網(wǎng)絡(luò)的若干性質(zhì)，以期通過(guò)對(duì)超網(wǎng)絡(luò)的研究洞悉真實(shí)復(fù)雜網(wǎng)絡(luò)及復(fù)雜系統(tǒng)的特性。

2 預(yù)備知識(shí)

2.1 超圖

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

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

定義2[22]（節(jié)點(diǎn)度，node degrees）超圖H=(V,E)的節(jié)點(diǎn)度為該超邊連接的節(jié)點(diǎn)數(shù)目，記為dHd(ei)。在超圖的關(guān)聯(lián)矩陣C(H)中，節(jié)點(diǎn)度即是對(duì)應(yīng)的列中非零元素的數(shù)目，即：

定義3[22]（節(jié)點(diǎn)超度，node hyperdegrees）超圖H=(V,E)的節(jié)點(diǎn)超度為包含該節(jié)點(diǎn)的超邊數(shù)目，記為dHhd(vi)。在超圖的關(guān)聯(lián)矩陣C(H)中，節(jié)點(diǎn)超度即是對(duì)應(yīng)的行中非零元素的數(shù)目，即：

定義4（超邊度，hyperedge degrees）超圖H=(V,E)的超邊度為超邊所鄰接的其他超邊的數(shù)目，即與該超邊至少存在1個(gè)公共節(jié)點(diǎn)的超邊數(shù)，記為dHed(ei)。在超圖的關(guān)聯(lián)矩陣C(H)中，超邊度即是與對(duì)應(yīng)的列非正交的列數(shù)目，即：

胡楓等人在文獻(xiàn)[22]中將超邊度定義為除去該超邊所對(duì)應(yīng)的列外與此列非正交的列的數(shù)目。本文將超邊度定義為超圖的關(guān)聯(lián)矩陣中所有的列與該超邊所對(duì)應(yīng)的列非正交的列的數(shù)目。由于非零列與自身一定非正交，本文中的超邊度相當(dāng)于在文獻(xiàn)[22]的基礎(chǔ)上增加了1。

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

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

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

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

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

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

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

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

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

對(duì)式（4）中的節(jié)點(diǎn)度分布多項(xiàng)式PolyHd(H)進(jìn)行分析，則可以得到如下結(jié)論：

對(duì)式（4）中的節(jié)點(diǎn)超度分布多項(xiàng)式PolyHhd(H)進(jìn)行分析，則可以得到如下結(jié)論：

對(duì)式（4）中的超邊度分布多項(xiàng)式PolyHed(H)進(jìn)行分析，則可以得到如下結(jié)論：

更進(jìn)一步地分析，可以得到如下結(jié)論：

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

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

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

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

2.2 分形理論

分形幾何學(xué)是分形理論的數(shù)學(xué)基礎(chǔ)，分形信息、分形設(shè)計(jì)和分形藝術(shù)等均由分形幾何衍生而出[26]。分形理論最基本特點(diǎn)是用分?jǐn)?shù)維度的視角和數(shù)學(xué)方法對(duì)客觀事物進(jìn)行分析研究，Cantor集、Koch雪花和Menger海綿等是常見(jiàn)的分形圖形。

定義13[27]分形矩陣是通過(guò)對(duì)初始矩陣進(jìn)行迭代相加運(yùn)算而生成的一系列具有分形特性的矩陣。

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

2.3 矩陣?yán)碚?/p>

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

矩陣A與B的Tracy-Singh積運(yùn)算[30]表述為：

矩陣A與B的Tracy-Singh和運(yùn)算[30]表述為：

矩陣A與B的Khatri-Rao積運(yùn)算[31]表述為：

矩陣A與B的Khatri-Rao和運(yùn)算[31]表述為：

Tracy-Singh積運(yùn)算與Tracy-Singh和運(yùn)算是將一個(gè)分塊矩陣中的每一個(gè)分塊與另一個(gè)分塊矩陣中的每一分塊進(jìn)行運(yùn)算，得到的新的分塊矩陣的分塊數(shù)目是兩個(gè)分塊矩陣分塊數(shù)目的乘積。Khatri-Rao積運(yùn)算與Khatri-Rao和運(yùn)算只是將一個(gè)分塊矩陣中的一個(gè)分塊與另一分塊矩陣中對(duì)應(yīng)的分塊進(jìn)行運(yùn)算，得到的新的分塊矩陣的分塊數(shù)目與參與運(yùn)算的兩個(gè)分塊矩陣的分塊數(shù)目相同。本文只考慮基于超圖關(guān)聯(lián)矩陣的Tracy-Singh積運(yùn)算與Tracy-Singh和運(yùn)算的超網(wǎng)絡(luò)構(gòu)建方法，至于基于超圖關(guān)聯(lián)矩陣的Khatri-Rao積運(yùn)算與Khatri-Rao和運(yùn)算的超網(wǎng)絡(luò)構(gòu)建方法將另文撰述。

3 基于矩陣運(yùn)算的超網(wǎng)絡(luò)模型構(gòu)建

3.1 基于矩陣運(yùn)算的自相似超網(wǎng)絡(luò)模型構(gòu)建

本文將分塊矩陣的Tracy-Singh積運(yùn)算應(yīng)用于超圖的關(guān)聯(lián)矩陣中，得到一種基于矩陣運(yùn)算的自相似超網(wǎng)絡(luò)構(gòu)建方法。

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

Liu在文獻(xiàn)[32]中論證了矩陣Tracy-Singh積運(yùn)算與Khatri-Rao積運(yùn)算的部分性質(zhì)。在將超圖的關(guān)聯(lián)矩陣視為列矩陣組成的分塊矩陣時(shí)，其Tracy-Singh積運(yùn)算的結(jié)果等效于Kronecker積運(yùn)算的結(jié)果。可以采用類似于文獻(xiàn)[10]中圖的鄰接矩陣的Kronecker積運(yùn)算的分析方法對(duì)超圖關(guān)聯(lián)矩陣的Tracy-Singh積運(yùn)算進(jìn)行分析。

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

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

對(duì)式（13）進(jìn)行分析，隨著迭代次數(shù)i的增大，在i→∞時(shí)，得到的超網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目、超邊數(shù)目和密度為：

式（15）說(shuō)明一個(gè)超圖的迭代Tracy-Singh積超圖在迭代次數(shù)趨近于無(wú)窮時(shí)，其節(jié)點(diǎn)數(shù)和超邊數(shù)均趨近于無(wú)窮，而其密度取決于初始超圖的密度。

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

定理1一個(gè)超圖的迭代Tracy-Singh積超圖的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布可分別通過(guò)其節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式的系數(shù)相乘次數(shù)相乘的運(yùn)算得到。

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

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

在通過(guò)Tracy-Singh積運(yùn)算構(gòu)建自相似超網(wǎng)絡(luò)時(shí)，采用式（16），可以從理論上嚴(yán)格計(jì)算出新生成的自相似超網(wǎng)絡(luò)的節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式，得到其節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布?？蓪⒍ɡ?進(jìn)行推廣并應(yīng)用到不同超圖的Tracy-Singh積運(yùn)算中。

在分形理論中，分形維數(shù)是對(duì)分形圖形進(jìn)行度量的重要參數(shù)。由于關(guān)聯(lián)矩陣與超網(wǎng)絡(luò)的一一對(duì)應(yīng)關(guān)系，對(duì)自相似超網(wǎng)絡(luò)及其關(guān)聯(lián)矩陣而言，它們的分形維數(shù)是相等的?？梢詫?duì)超網(wǎng)絡(luò)關(guān)聯(lián)矩陣的分形維數(shù)進(jìn)行分析以間接得到超網(wǎng)絡(luò)的分形維數(shù)。下文基于分形維數(shù)的定義，對(duì)此類自相似超網(wǎng)絡(luò)的分形維數(shù)進(jìn)行分析。

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

于是，基于分形維數(shù)的計(jì)算方法，可以得出如下定理。

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

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

定理3一個(gè)超圖的迭代Tracy-Singh積超圖的分形維數(shù)不超過(guò)2。

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

定理3得證。 □

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

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

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

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

超圖是圖的超集，文獻(xiàn)[10]基于圖的鄰接矩陣的迭代Kronecker積圖形式的自相似網(wǎng)絡(luò)的分形維數(shù)介于1到2之間，此處基于超圖的關(guān)聯(lián)矩陣的迭代Tracy-Singh積超圖形式的自相似超網(wǎng)絡(luò)的分形維數(shù)介于0到2之間?？梢园l(fā)現(xiàn)，自相似超網(wǎng)絡(luò)的分形維數(shù)涵蓋了自相似網(wǎng)絡(luò)的分形維數(shù)，這從一個(gè)側(cè)面詮釋了超圖是圖的超集，圖是超圖的特例。

另外，一個(gè)分塊矩陣的迭代Tracy-Singh積運(yùn)算的結(jié)果也是分塊矩陣，對(duì)基于超圖關(guān)聯(lián)矩陣的迭代Tracy-Singh積運(yùn)算得到的分塊矩陣進(jìn)行分析，則可以得出如下定理。

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

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

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

注2定理4只對(duì)連通且非二分超圖成立，對(duì)非連通超圖或二分超圖不成立，因?yàn)槎殖瑘D的迭代Tracy-Singh積超圖是非連通超圖，而非連通超圖的直徑是無(wú)窮大。

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

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

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

為更直觀地刻畫自相似超網(wǎng)絡(luò)在不同維度下的度量情況，將一個(gè)連通且非二分超圖的迭代Tracy-Singh積超圖對(duì)應(yīng)的自相似超網(wǎng)絡(luò)與文獻(xiàn)[10]中的自相似網(wǎng)絡(luò)進(jìn)行對(duì)比，對(duì)比結(jié)果如表1所示。

Table 1 Comparison between self-similarity hypernetwork and self-similarity network表1 自相似超網(wǎng)絡(luò)與自相似網(wǎng)絡(luò)對(duì)比表

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

從定理2可知，自相似超網(wǎng)絡(luò)的分形維數(shù)只與初始超圖的節(jié)點(diǎn)數(shù)、超邊數(shù)和超邊包含的節(jié)點(diǎn)數(shù)之和有關(guān)，可能存在多個(gè)拓?fù)浣Y(jié)構(gòu)不同的超圖卻擁有相同的節(jié)點(diǎn)數(shù)和超邊數(shù)，且超邊包含的節(jié)點(diǎn)數(shù)之和相等，也可能存在多個(gè)拓?fù)浣Y(jié)構(gòu)不同且節(jié)點(diǎn)數(shù)與超邊數(shù)及超邊包含的節(jié)點(diǎn)數(shù)之和也不同但分形維數(shù)卻相同的超圖，給出下述定義。

定義14（準(zhǔn)自相似超網(wǎng)絡(luò)，quasi self-similarity hypernetwork）準(zhǔn)自相似超網(wǎng)絡(luò)是指由多個(gè)節(jié)點(diǎn)數(shù)和超邊數(shù)相等且超邊包含的節(jié)點(diǎn)數(shù)之和也相等的初始超圖對(duì)應(yīng)的關(guān)聯(lián)矩陣，通過(guò)Tracy-Singh積運(yùn)算而得到的Tracy-Singh積超圖。

定義15（泛自相似超網(wǎng)絡(luò)，pan self-similarity hypernetwork）泛自相似超網(wǎng)絡(luò)是指由多個(gè)超邊包含的節(jié)點(diǎn)數(shù)之和的對(duì)數(shù)值及節(jié)點(diǎn)數(shù)與超邊數(shù)乘積對(duì)數(shù)值的比值的兩倍相等的初始超圖所對(duì)應(yīng)的關(guān)聯(lián)矩陣，通過(guò)Tracy-Singh積運(yùn)算而得到的Tracy-Singh積超圖。

對(duì)準(zhǔn)自相似超網(wǎng)絡(luò)和泛自相似超網(wǎng)絡(luò)進(jìn)行分析，可以得到下述結(jié)論。

定理6準(zhǔn)自相似超網(wǎng)絡(luò)的分形維數(shù)等于對(duì)應(yīng)的自相似超網(wǎng)絡(luò)的分形維數(shù)。

證明根據(jù)定理2及式（10），自相似超網(wǎng)絡(luò)的分形維數(shù)只與初始超圖的節(jié)點(diǎn)數(shù)、超邊數(shù)和超邊包含的節(jié)點(diǎn)數(shù)之和有關(guān)。又根據(jù)定理1及式（16），準(zhǔn)自相似超網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、超邊數(shù)和超邊包含的節(jié)點(diǎn)數(shù)之和與對(duì)應(yīng)的自相似超網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、超邊數(shù)和超邊包含的節(jié)點(diǎn)數(shù)之和均相等。因此，準(zhǔn)自相似超網(wǎng)絡(luò)的分形維數(shù)與對(duì)應(yīng)的自相似超網(wǎng)絡(luò)的分形維數(shù)也相等。定理6得證。 □

引理2泛自相似超網(wǎng)絡(luò)的分形維數(shù)等于對(duì)應(yīng)的準(zhǔn)自相似超網(wǎng)絡(luò)的分形維數(shù)。

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

將超網(wǎng)絡(luò)記為全集U，自相似超網(wǎng)絡(luò)記為USS，準(zhǔn)自相似超網(wǎng)絡(luò)記為UQSS，泛自相似超網(wǎng)絡(luò)記為UPSS，則可以得到如下定理。

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

證明易證其成立。 □

3.2 基于矩陣運(yùn)算的隨機(jī)超網(wǎng)絡(luò)模型構(gòu)建

基于矩陣運(yùn)算的隨機(jī)超網(wǎng)絡(luò)模型構(gòu)建方法如下所示：對(duì)于一系列隨機(jī)選擇的初始超圖H(1),H(2),…,,…來(lái)說(shuō)，將Tracy-Singh和運(yùn)算順次應(yīng)用于上述超圖對(duì)應(yīng)的關(guān)聯(lián)矩陣可以得到一個(gè)新的矩陣，該矩陣對(duì)應(yīng)的超網(wǎng)絡(luò)是上述超圖的Tracy-Singh和超圖，即為隨機(jī)超網(wǎng)絡(luò)。

對(duì)于隨機(jī)選擇的初始超圖H=(V,E)來(lái)說(shuō)，可以認(rèn)為其節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布均是隨機(jī)的，即均服從正態(tài)分布。而節(jié)點(diǎn)度、節(jié)點(diǎn)超度和超邊度在其對(duì)應(yīng)的節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式中即是對(duì)應(yīng)的單項(xiàng)式次數(shù)，故反映在節(jié)點(diǎn)度分布多項(xiàng)式PolyHd(H)、節(jié)點(diǎn)超度分布多項(xiàng)式PolyHhd(H)和超邊度分布多項(xiàng)式PolyHed(H)中，則是各個(gè)單項(xiàng)式的次數(shù)服從正態(tài)分布。

對(duì)兩個(gè)超圖Ha=(Va,Ea)、Hb=(Vb,Eb)及對(duì)應(yīng)的節(jié)點(diǎn)度分布多項(xiàng)式PolyHd(Ha)與PolyHd(Hb)、節(jié)點(diǎn)超度分布多項(xiàng)式PolyHhd(Ha)與PolyHhd(Hb)、超邊度分布多項(xiàng)式PolyHed(Ha)與PolyHed(Hb)來(lái)說(shuō)，將Tracy-Singh積運(yùn)算應(yīng)用于Ha與Hb對(duì)應(yīng)的關(guān)聯(lián)矩陣所得到的Tracy-Singh積超圖Hab的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布可分別通過(guò)PolyHd(Ha)與PolyHd(Hb)、PolyHhd(Ha)與PolyHhd(Hb)及PolyHed(Ha)與PolyHed(Hb)的 Tracy-Singh積運(yùn)算得到，即有：

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

式（23）中節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式的運(yùn)算即是通常的多項(xiàng)式乘法?？梢钥闯?，類似于對(duì)Tracy-Singh積運(yùn)算采用系數(shù)相乘次數(shù)相乘的運(yùn)算，對(duì)Tracy-Singh和運(yùn)算采用系數(shù)相乘次數(shù)相加的運(yùn)算也可以得到所生成的超網(wǎng)絡(luò)的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布?？梢詫蓚€(gè)相同或不同超圖的Tracy-Singh積超圖的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布視為初始超圖節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布的非線性組合，并將兩個(gè)相同或不同超圖的Tracy-Singh和超圖的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布視為初始超圖節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布的線性組合。對(duì)于隨機(jī)選擇的初始超圖來(lái)說(shuō)，其節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布可以視為均服從正態(tài)分布。由于有限個(gè)正態(tài)分布的線性組合也是正態(tài)分布，基于多個(gè)初始超圖的Tracy-Singh和超圖的節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布也服從正態(tài)分布。

在初始超圖集合{H1,H2,…,Hi,…}中，對(duì)于順次選擇的H(1),H(2),…,H(i),…,H(n)并進(jìn)行Tracy-Singh和運(yùn)算得到的Tracy-Singh和超圖H(n)來(lái)說(shuō)，其節(jié)點(diǎn)數(shù)、超邊數(shù)和密度可通過(guò)度分布多項(xiàng)式得到：

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

3.3 不同組合的超網(wǎng)絡(luò)模型

前面分析了基于一個(gè)簡(jiǎn)單初始超圖的迭代Tracy-Singh積運(yùn)算可以得到自相似超網(wǎng)絡(luò)，基于多個(gè)簡(jiǎn)單初始超圖的Tracy-Singh和運(yùn)算可以得到隨機(jī)超網(wǎng)絡(luò)。其實(shí)也可以基于一個(gè)初始超圖進(jìn)行迭代Tracy-Singh和運(yùn)算或多個(gè)初始超圖進(jìn)行Tracy-Singh積運(yùn)算。當(dāng)然，也可以同時(shí)應(yīng)用Tracy-Singh積運(yùn)算及Tracy-Singh和運(yùn)算。將上述超網(wǎng)絡(luò)構(gòu)建方法進(jìn)行推廣，可以得到一般情況下基于矩陣運(yùn)算的超網(wǎng)絡(luò)構(gòu)建方法?；谝粋€(gè)、有限多個(gè)，乃至無(wú)窮多個(gè)初始超圖的Tracy-Singh積運(yùn)算和/或Tracy-Singh和運(yùn)算共有9種組合，如表2所示。9種組合之間的關(guān)系如圖1所示。

Table 2 Statistics of 9 combinations of hypernetwork based on matrix operation表2 基于矩陣運(yùn)算的9種組合超網(wǎng)絡(luò)統(tǒng)計(jì)表

4 基于矩陣運(yùn)算的超網(wǎng)絡(luò)理論分析

4.1 基于矩陣運(yùn)算的超網(wǎng)絡(luò)數(shù)量分析

在基于矩陣運(yùn)算的超網(wǎng)絡(luò)構(gòu)建中，可以對(duì)初始超圖節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式進(jìn)行計(jì)算以得到Tracy-Singh積超圖及Tracy-Singh和超圖的節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式及超邊度分布多項(xiàng)式，隨之得到其節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布。由于超圖的節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式無(wú)法反映超圖的拓?fù)浣Y(jié)構(gòu)，一個(gè)相同的節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式組合可能對(duì)應(yīng)多個(gè)拓?fù)浣Y(jié)構(gòu)不同的超圖。

化學(xué)中描述化合物時(shí)需要分子式，但由于同分異構(gòu)現(xiàn)象的存在，在描述化合物時(shí)，還需要結(jié)構(gòu)式。一個(gè)相同的分子式可能對(duì)應(yīng)多個(gè)不同的結(jié)構(gòu)式，通過(guò)度分布多項(xiàng)式組合描述超網(wǎng)絡(luò)與之類似。分子式對(duì)應(yīng)于超網(wǎng)絡(luò)的度分布多項(xiàng)式組合，而結(jié)構(gòu)式對(duì)應(yīng)于超網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。與分子式對(duì)于結(jié)構(gòu)式存在數(shù)量規(guī)律類似，節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式組合對(duì)于超網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也存在數(shù)量規(guī)律。本文對(duì)基于矩陣運(yùn)算的超網(wǎng)絡(luò)數(shù)量進(jìn)行研究，得到如下結(jié)論。

Fig.1 Relation of 9 combinations of hypernetwork圖1 超網(wǎng)絡(luò)9種組合關(guān)系圖

定理8超網(wǎng)絡(luò)的數(shù)量不超過(guò)其節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式對(duì)應(yīng)的復(fù)雜網(wǎng)絡(luò)數(shù)量的乘積，即：證明對(duì)于超圖H=(V,E)而言，其節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布并不完全獨(dú)立，三者之間存在一定的耦合關(guān)系，故超圖的數(shù)量不超過(guò)其節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式對(duì)應(yīng)的復(fù)雜網(wǎng)絡(luò)數(shù)量的乘積。定理8得證。 □

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

4.2 基于矩陣運(yùn)算的超網(wǎng)絡(luò)擾動(dòng)與穩(wěn)定分析

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

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

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

對(duì)自相似超網(wǎng)絡(luò)直徑的影響而言，由于直徑尚無(wú)類似于分形維數(shù)的顯式函數(shù)可以表述，故無(wú)法通過(guò)類似于分形維數(shù)的分析方法進(jìn)行論述。但由于自相似超網(wǎng)絡(luò)的直徑不超過(guò)初始超圖直徑的兩倍，而且初始超圖中超邊包含的節(jié)點(diǎn)變動(dòng)對(duì)初始超圖的直徑?jīng)]有顯著的影響，可通過(guò)添加或刪除一個(gè)節(jié)點(diǎn)或一條超邊時(shí)對(duì)初始超圖直徑的影響來(lái)進(jìn)行間接的分析。由于添加與刪除是相對(duì)的，這里只分析添加即可，于是可得到如下結(jié)論。

定理9向初始超圖添加一個(gè)節(jié)點(diǎn)后，自相似超網(wǎng)絡(luò)直徑的增加量不超過(guò)2。

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

定理10向初始超圖添加一條超邊后，自相似超網(wǎng)絡(luò)直徑的減少量不超過(guò)一半。

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

由于添加或刪除一個(gè)節(jié)點(diǎn)或一條超邊時(shí)對(duì)初始超圖直徑的影響存在確定的上限，故對(duì)最終生成的自相似超網(wǎng)絡(luò)直徑的影響也存在確定的上限。

對(duì)自相似超網(wǎng)絡(luò)節(jié)點(diǎn)度分布、節(jié)點(diǎn)超度分布和超邊度分布的影響而言，在具體的計(jì)算中是將節(jié)點(diǎn)度分布多項(xiàng)式、節(jié)點(diǎn)超度分布多項(xiàng)式和超邊度分布多項(xiàng)式進(jìn)行類似多項(xiàng)式乘法的系數(shù)相乘次數(shù)相乘的運(yùn)算，將式（22）代入式（5）、式（6）和式（7）得到：

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

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

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

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

5 基于矩陣運(yùn)算的超網(wǎng)絡(luò)仿真實(shí)驗(yàn)

Fig.2 6 different initial hypernetworks圖2 6個(gè)不同初始超圖

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

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

同時(shí)，通過(guò)分析表3可以發(fā)現(xiàn)，在增加或刪除一個(gè)節(jié)點(diǎn)或一條超邊時(shí)，對(duì)最終得到的自相似超網(wǎng)絡(luò)的分形維數(shù)影響不大，而且添加或刪除節(jié)點(diǎn)對(duì)添加或刪除超邊對(duì)分形維數(shù)的影響更大，這可以通過(guò)表3中分形維數(shù)差別不大體現(xiàn)出來(lái)。而且，其對(duì)超網(wǎng)絡(luò)直徑的影響也是有限的，這可以通過(guò)表3中超網(wǎng)絡(luò)直徑的差別不超過(guò)2體現(xiàn)出來(lái)。這其實(shí)就是超網(wǎng)絡(luò)的“定數(shù)”。定數(shù)與變數(shù)共存是超網(wǎng)絡(luò)的特點(diǎn)，也是所有復(fù)雜網(wǎng)絡(luò)與復(fù)雜系統(tǒng)的特點(diǎn)。

Table 3 Statistics of 6 different initial hypergraphs表3 6個(gè)不同初始超圖統(tǒng)計(jì)表

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

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

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

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

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

Fig.6 Node degrees distributions of random hypernetworks based on 20 initial hypergraphs selected randomly圖6 隨機(jī)選擇20個(gè)初始超圖后得到的隨機(jī)超網(wǎng)絡(luò)節(jié)點(diǎn)度分布

Table 4 6 random hypernetworks and corresponding 20 initial hypergraphs表4 6個(gè)隨機(jī)超網(wǎng)絡(luò)對(duì)應(yīng)的20個(gè)初始超圖選擇表

6 結(jié)束語(yǔ)

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

Fig.7 Node hyperdegrees distributions of random hypernetworks based on 20 initial hypergraphs selected randomly圖7 隨機(jī)選擇20個(gè)初始超圖后得到的隨機(jī)超網(wǎng)絡(luò)節(jié)點(diǎn)超度分布

Fig.8 Hyperedge degrees distributions of random hypernetworks based on 20 Initial hypergraphs selected randomly圖8 隨機(jī)選擇20個(gè)初始超圖后得到的隨機(jī)超網(wǎng)絡(luò)超邊度分布

[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.

附中文參考文獻(xiàn)：

[8]張嗣瀛.復(fù)雜系統(tǒng)、復(fù)雜網(wǎng)絡(luò)自相似結(jié)構(gòu)的涌現(xiàn)規(guī)律[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2006,3(4):41-51.

[10]劉勝久,李天瑞,洪西進(jìn),等.基于矩陣運(yùn)算的復(fù)雜網(wǎng)絡(luò)構(gòu)建方法研究[J].中國(guó)科學(xué):信息科學(xué),2016,46(5):610-626.

[20]裴偉東,夏瑋,王全來(lái),等.一類三角形結(jié)構(gòu)動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)演化模型分析[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2010,40(11): 1186-1190.

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

[26]朱華,姬翠翠.分形理論及其應(yīng)用[M].北京:科學(xué)出版社, 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年于西南交通大學(xué)獲得博士學(xué)位，現(xiàn)為西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院博士后，主要研究領(lǐng)域?yàn)閺?fù)雜網(wǎng)絡(luò)，自然語(yǔ)言處理，云計(jì)算等。

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年于西南交通大學(xué)獲得博士學(xué)位，現(xiàn)為西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師，國(guó)際粗糙集學(xué)會(huì)（IRSS）會(huì)士，CCF、IEEE和CAI高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)，粒計(jì)算與粗糙集，云計(jì)算，大數(shù)據(jù)等。

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.

洪西進(jìn)（1957—），男，臺(tái)灣桃園人，1989年于臺(tái)灣清華大學(xué)獲得博士學(xué)位，現(xiàn)為臺(tái)灣科技大學(xué)咨訊工程系教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)閂LSI設(shè)計(jì)，多處理器系統(tǒng)，并行計(jì)算等。

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年于四川大學(xué)獲得博士學(xué)位，現(xiàn)為西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院副研究員、碩士生導(dǎo)師，CCF、IEEE和ACM會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，半監(jiān)督學(xué)習(xí)，半監(jiān)督集成學(xué)習(xí)等。

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—），男，西藏日喀則人，西南交通大學(xué)博士研究生，西藏大學(xué)副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，自然語(yǔ)言處理等。

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(國(guó)家自然科學(xué)基金);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(中國(guó)科學(xué)院自動(dòng)化研究所復(fù)雜系統(tǒng)管理與控制重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(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.