董浩然，張 科,2，胡文軍,2

(1.湖州師范學(xué)院信息工程學(xué)院，浙江湖州；2.浙江省現(xiàn)代農(nóng)業(yè)資源智慧管理與應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室，浙江湖州)

引言

復(fù)雜網(wǎng)絡(luò)中常常將現(xiàn)實(shí)世界的事物抽象成網(wǎng)絡(luò)系統(tǒng)中的節(jié)點(diǎn)，而事物之間的聯(lián)系抽象為節(jié)點(diǎn)之間的連邊。在基于普通圖的復(fù)雜網(wǎng)絡(luò)研究中，研究者們研究了許多復(fù)雜網(wǎng)絡(luò)模型以便于揭示網(wǎng)絡(luò)的性質(zhì)。Berge[1]在1989 年首次提出了超圖一詞，并且定義了無向超圖。之后Estrada[2]認(rèn)為凡是可以用超圖表示的網(wǎng)絡(luò)即為超網(wǎng)絡(luò)（Hypernetwork）。超圖為普通圖的推廣為了研究超網(wǎng)絡(luò)的機(jī)制以及性質(zhì)，研究者們構(gòu)建了許多基于超圖的超網(wǎng)絡(luò)模型。近年隨著人們?cè)谘芯可鷳B(tài)食物網(wǎng)、大腸桿菌和釀酒酵母遺傳網(wǎng)絡(luò)、以及執(zhí)行信息處理的網(wǎng)絡(luò)中都發(fā)現(xiàn)了一些相互連接且數(shù)量明顯高于隨機(jī)網(wǎng)絡(luò)的連接模式，且不同網(wǎng)絡(luò)系統(tǒng)中的這種網(wǎng)絡(luò)基序[3]不同，因此提出了網(wǎng)絡(luò)模體[4]的概念。在網(wǎng)絡(luò)模型的研究中確定性模型以及演化模型[5]一直是研究的重點(diǎn)。本文提出了一種由一個(gè)確定性普通網(wǎng)絡(luò)逆向構(gòu)建超網(wǎng)絡(luò)的方法，并在幾個(gè)普通網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)同時(shí)對(duì)于構(gòu)建的超網(wǎng)絡(luò)進(jìn)行了一些拓?fù)涮匦苑治觥?/p>

1 超圖的部分理論

1.1 超圖定義

設(shè)超圖H=（V,E）其中V=（v1,v2,v3…vn），E=（e1,e2,e3…,em）為兩個(gè)有限集，集合V 的一個(gè)元素為超圖的一個(gè)頂點(diǎn)集合E 的一個(gè)元素為超圖H 的一條超邊。當(dāng)與邊關(guān)聯(lián)的頂點(diǎn)數(shù)目大于2 時(shí)，用一個(gè)閉合曲線表示包含這些頂點(diǎn)的一條超邊。圖1 為一個(gè)有兩條超邊四個(gè)頂點(diǎn)的超圖示意圖。

圖1 一個(gè)有三條超邊和6 個(gè)頂點(diǎn)的超圖

1.2超圖的階、秩

超圖H=（V,E）中若兩個(gè)節(jié)點(diǎn)屬于同一條超邊則稱這兩個(gè)節(jié)點(diǎn)鄰接或關(guān)聯(lián)。超圖H 中的節(jié)點(diǎn)個(gè)數(shù)稱為超圖的階。超圖H 中的一條超邊有最多個(gè)頂點(diǎn)鄰接則這條超邊中包含的節(jié)點(diǎn)個(gè)數(shù)稱為該超圖的秩。如果超圖中每條超邊都含有r 個(gè)節(jié)點(diǎn)則稱H 為r 一致超圖。

1.3 關(guān)聯(lián)矩陣

對(duì)于普通圖其數(shù)學(xué)表達(dá)形式就是鄰接矩陣，而在超圖中超圖與其鄰接矩陣并不是一對(duì)一的關(guān)系，而一個(gè)超圖可以由一個(gè)關(guān)聯(lián)矩陣唯一確定，因此我們使用關(guān)聯(lián)矩陣來描述超圖。設(shè)超圖H=（V,E）其關(guān)聯(lián)矩陣B（H）定義為：

1.4節(jié)點(diǎn)超度

超圖H 中如果節(jié)點(diǎn)vi∈ej那么稱節(jié)點(diǎn)vi與超邊ej關(guān)聯(lián)，節(jié)點(diǎn)vi的超度定義為所有與vi關(guān)聯(lián)的超邊的數(shù)目，記為dH（vi）。超圖H的度分布定義為：超圖H中任取一個(gè)節(jié)點(diǎn)超度為dH的概率，記為p（dH）。

2 模體超網(wǎng)絡(luò)構(gòu)建

2.1 網(wǎng)絡(luò)模體

許多領(lǐng)域的研究者們都在研究復(fù)雜網(wǎng)絡(luò)。研究人員們發(fā)現(xiàn)不同的網(wǎng)絡(luò)中都會(huì)出現(xiàn)一些連接模式相同的子結(jié)構(gòu)，進(jìn)而有了網(wǎng)絡(luò)模體這一概念。而模體[6]這一詞源于生物學(xué)，在生物學(xué)中也叫模序，表示蛋白質(zhì)中具有特定空間構(gòu)象和特定功能的結(jié)構(gòu)部分。

自然界中許多復(fù)雜網(wǎng)絡(luò)都被證明具有小世界和無標(biāo)度。的特性。要超越這些全局特征，我們需要了解每一類網(wǎng)絡(luò)特有的基本元素結(jié)構(gòu)。因此模體反復(fù)出現(xiàn)、互連的模式可以推廣到網(wǎng)絡(luò)模型的構(gòu)建以及研究上。網(wǎng)絡(luò)中的模體代表了廣泛的自然現(xiàn)象。復(fù)雜網(wǎng)絡(luò)系統(tǒng)中的交互作用的重要性也不言而喻，超圖作為高階建模[7]的數(shù)學(xué)工具也被廣泛應(yīng)用。不同網(wǎng)絡(luò)的結(jié)構(gòu)的功能性的區(qū)別，常體現(xiàn)在局部偏好連接的不同，這時(shí)便可以用網(wǎng)絡(luò)的模體來進(jìn)行量化。值得說明的是模體的數(shù)目是隨著模體的階數(shù)呈上升的。以本文研究的無向超網(wǎng)絡(luò)為例，圖2 展示了三階模體以及四階模體。

圖2 三階、四階模體

2.2 超網(wǎng)絡(luò)構(gòu)建方法

本文提出了一種由一個(gè)確定的普通網(wǎng)絡(luò)逆向構(gòu)建的只存在三階模體的超網(wǎng)絡(luò)。對(duì)于構(gòu)建完畢的超網(wǎng)絡(luò)，其網(wǎng)絡(luò)中的每一條超邊都只有三個(gè)節(jié)點(diǎn)。這類超網(wǎng)絡(luò)也被稱為三一致。具體的構(gòu)造方法是：首先找到一個(gè)連通的普通網(wǎng)絡(luò)將網(wǎng)絡(luò)的所有節(jié)點(diǎn)和邊進(jìn)行標(biāo)記并將節(jié)點(diǎn)進(jìn)行編號(hào)且將網(wǎng)絡(luò)中所有的連邊放在一個(gè)邊集中。遍歷一遍網(wǎng)絡(luò)，統(tǒng)計(jì)圖中所有節(jié)點(diǎn)的度，找到所有度大于等于2 的節(jié)點(diǎn)。之所以要找出所有度大于等于2 的節(jié)點(diǎn)其原因在于三階模體只有“v”字形和“三角形”兩種連接模式，假設(shè)一個(gè)節(jié)點(diǎn)的度等于2 那么意味著在網(wǎng)絡(luò)中該節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)與之關(guān)聯(lián)，即存在兩個(gè)節(jié)點(diǎn)與之相連，這時(shí)候可以運(yùn)用復(fù)雜網(wǎng)絡(luò)中聚類系數(shù)的概念通過計(jì)算該節(jié)點(diǎn)的聚類系數(shù)則可以判斷出與該節(jié)點(diǎn)關(guān)聯(lián)的兩個(gè)節(jié)點(diǎn)之間是否存在關(guān)聯(lián)。聚類系數(shù)的算法表達(dá)式如下：

其中,i 為節(jié)點(diǎn),ei為i 鄰節(jié)點(diǎn)的關(guān)系數(shù)，ki為節(jié)點(diǎn)的度。這種算法也叫三角形計(jì)數(shù)法。通過Ci的值可以求出該節(jié)點(diǎn)所有三角形的個(gè)數(shù)。假設(shè)Ci等于0，即不存在三角形，由于三階模體只有兩種，那么意味著該節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)為v 字形。如若等于1 那么該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間有一條連邊，即就是一個(gè)三角形。因此在構(gòu)造超網(wǎng)絡(luò)時(shí)第一遍要對(duì)網(wǎng)絡(luò)中所有度大于等于2的節(jié)點(diǎn)去進(jìn)行構(gòu)造。對(duì)于度大于2 的節(jié)點(diǎn)，意味著有多個(gè)節(jié)點(diǎn)與之存在連邊，此時(shí)該節(jié)點(diǎn)的聚類系數(shù)若不為0 意味著存在1 個(gè)或多個(gè)三角形，三角形個(gè)數(shù)可以通過聚類系數(shù)算法推出。本文提出的算法是優(yōu)先考慮三角形的情況，即若該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間有關(guān)聯(lián)邊數(shù)m 就存在m 個(gè)三角形，將形成該三角形的三個(gè)節(jié)點(diǎn)以及三條邊構(gòu)造成一條包含三個(gè)節(jié)點(diǎn)的超邊，并從邊集中將這三條邊標(biāo)記。之所以要標(biāo)記用過的連邊是為了避免出現(xiàn)重邊的情況。在找出所有三角形以后，那么就只剩向該節(jié)點(diǎn)添加v 字形，節(jié)點(diǎn)的v 字形的數(shù)目等于該節(jié)點(diǎn)的度取2 的組合數(shù)再減去三角形的個(gè)數(shù)，此時(shí)任取兩個(gè)該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)并將這三個(gè)節(jié)點(diǎn)構(gòu)造成一條包含這三個(gè)節(jié)點(diǎn)的超邊。需要特別說明的是在構(gòu)建超網(wǎng)絡(luò)模型的過程中會(huì)出現(xiàn)一個(gè)節(jié)點(diǎn)的邊被標(biāo)記的只剩1 條邊的情形這時(shí)候就跳過這個(gè)節(jié)點(diǎn)到它的下一個(gè)鄰居節(jié)點(diǎn)直至遍歷完所有節(jié)點(diǎn)為止。在這里需要用到r- 一致超圖的超邊數(shù)目上下界理論：

其中，n 為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，i 為節(jié)點(diǎn)度大于等于2 的節(jié)點(diǎn)編號(hào)，ki為節(jié)點(diǎn)度，? 為網(wǎng)絡(luò)中度等于1 且在第一次構(gòu)造中沒有用到的節(jié)點(diǎn)個(gè)數(shù)。

在第一次遍歷完所有節(jié)點(diǎn)以后此時(shí)的超網(wǎng)絡(luò)可能是連通的也可能是不連通的，如果此時(shí)超網(wǎng)絡(luò)已經(jīng)連通那么即構(gòu)建完畢。如果不連通，是因?yàn)榇藭r(shí)網(wǎng)絡(luò)中還有度為1 且在第一遍構(gòu)造中沒有包含在超邊中的節(jié)點(diǎn)。對(duì)于這些節(jié)點(diǎn)，它的鄰居節(jié)點(diǎn)的度是大于等于2 的那么只需要從鄰居節(jié)點(diǎn)的所有連邊中任取一條邊組成一條v 字形并加入一條超邊包含即可。需要補(bǔ)充說明的是在處理這些度為1 節(jié)點(diǎn)的時(shí)候并不考慮鄰居節(jié)點(diǎn)的邊是否被標(biāo)記的情形即都當(dāng)作未標(biāo)記來處理。最后再判斷此時(shí)超網(wǎng)絡(luò)是否連通，如若連通那么超網(wǎng)絡(luò)模型構(gòu)造完畢，如若不連通則繼續(xù)向網(wǎng)絡(luò)中添加超邊直至該超網(wǎng)絡(luò)連通[8]為止。這里給出超網(wǎng)絡(luò)的連通算法：

其中，X 為超圖的鄰接矩陣。圖3 展示了構(gòu)造超網(wǎng)絡(luò)的過程。

圖3 超網(wǎng)絡(luò)構(gòu)造過程

2.3 實(shí)驗(yàn)分析

為了測試算法的普適性，本文找到了一些具有無標(biāo)度特性的普通網(wǎng)絡(luò)數(shù)據(jù)集依據(jù)本文提供的方法對(duì)其中的二個(gè)網(wǎng)絡(luò)進(jìn)行了實(shí)驗(yàn)。每個(gè)網(wǎng)絡(luò)仍做十次隨機(jī)實(shí)驗(yàn)，同時(shí)統(tǒng)計(jì)普通網(wǎng)絡(luò)的度分布以及生成的超網(wǎng)絡(luò)的超度分布進(jìn)行對(duì)照。

用Zachary 數(shù)據(jù)集構(gòu)建Zachary 網(wǎng)絡(luò)，該網(wǎng)絡(luò)有34 個(gè)節(jié)點(diǎn)以及78 條邊。網(wǎng)絡(luò)中最大的節(jié)點(diǎn)度為17，最小的節(jié)點(diǎn)度為1。根據(jù)我們的算法逆向構(gòu)建為三階模體超網(wǎng)絡(luò)后統(tǒng)計(jì)10 次隨機(jī)生成的超網(wǎng)絡(luò)的所有超度的數(shù)值，其中超度最大值為27，超度最小值為1。從數(shù)據(jù)統(tǒng)計(jì)中我們可以看出，依據(jù)普通網(wǎng)絡(luò)逆向構(gòu)建的超網(wǎng)絡(luò)比普通網(wǎng)絡(luò)擁有更多的度值類型，這不單單是因?yàn)?0 次實(shí)驗(yàn)中每次實(shí)驗(yàn)的超度會(huì)有不同數(shù)值的原因也與我們提出的算法是密切相關(guān)的，同時(shí)聯(lián)系實(shí)際也符合超網(wǎng)絡(luò)作為一個(gè)描述高階交互系統(tǒng)的工具的特性。同時(shí)逆向構(gòu)建的超網(wǎng)絡(luò)也保持了原普通網(wǎng)絡(luò)的一些特性，構(gòu)建的超網(wǎng)絡(luò)仍然具有無標(biāo)度的特性。

其10 次實(shí)驗(yàn)生成的超網(wǎng)絡(luò)取平均的超度分布與普通網(wǎng)絡(luò)度分布如圖4 所示。

圖4 度分布擬合圖

結(jié)束語

對(duì)于超網(wǎng)絡(luò)模型的研究，往往都是將超網(wǎng)絡(luò)間接轉(zhuǎn)化為普通網(wǎng)絡(luò)去進(jìn)行參照對(duì)比，本文通過抓住普通網(wǎng)絡(luò)中普遍出現(xiàn)的子結(jié)構(gòu)從而將普通網(wǎng)絡(luò)轉(zhuǎn)化為模體超網(wǎng)絡(luò)去進(jìn)行分析對(duì)比，進(jìn)而發(fā)現(xiàn)了一些模體超網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果，而未來四階模體等更高階的模體超網(wǎng)絡(luò)還值得研究者們繼續(xù)去研究。