模體超網(wǎng)絡的構建方法及其特性分析

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

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

引言

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

1 超圖的部分理論

1.1 超圖定義

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

圖1 一個有三條超邊和6 個頂點的超圖

1.2超圖的階、秩

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

1.3 關聯(lián)矩陣

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

1.4節(jié)點超度

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

2 模體超網(wǎng)絡構建

2.1 網(wǎng)絡模體

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

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

圖2 三階、四階模體

2.2 超網(wǎng)絡構建方法

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

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

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

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

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

圖3 超網(wǎng)絡構造過程

2.3 實驗分析

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

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

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

圖4 度分布擬合圖

結束語

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