模體超網絡的構建方法及其特性分析

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

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

引言

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

1 超圖的部分理論

1.1 超圖定義

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

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

1.2超圖的階、秩

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

1.3 關聯矩陣

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

1.4節點超度

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

2 模體超網絡構建

2.1 網絡模體

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

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

圖2 三階、四階模體

2.2 超網絡構建方法

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

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

其中，n 為網絡節點個數，i 為節點度大于等于2 的節點編號，ki為節點度，? 為網絡中度等于1 且在第一次構造中沒有用到的節點個數。

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

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

圖3 超網絡構造過程

2.3 實驗分析

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

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

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

圖4 度分布擬合圖

結束語

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