摘 要：超網絡是較通常意義上的復雜網絡更為復雜的網絡，該網絡的每一條超邊能連接任意多個節點的特性使其比復雜網絡能更好地描述真實世界中的復雜系統。針對現有超網絡研究中對超網絡度量方法的缺陷與不足，提出了一種超網絡度量方法——超網絡維數(HD)，即為所有超邊包含的節點權重之和與對應超邊權重乘積和的對數值和節點權重之和與超邊權重之和乘積對數值的比值的兩倍。超網絡維數可以應用于節點權重與超邊權重為正實數、負實數、純虛數，乃至復數等多種不同數值類型的帶權超網絡中。最后給出了超網絡維數的若干性質。

　　關鍵詞：復雜網絡;超圖;超網絡;分形維數;網絡維數;超網絡維數

　　《信息安全研究》(月刊)創刊于1998年，由國家信息中心主辦中文學術期刊，主要刊登信息安全研究領域的原創性研究成果，其內容覆蓋信息安全領域的各個學科。

　　0 引言

　　圖論是復雜網絡研究的基礎。自18世紀歐拉對哥尼斯堡七橋問題的研究而開創圖論以來，圖論已在很多領域得到極為廣泛的應用。現代意義上復雜網絡的研究發軔于20世紀中葉兩位匈牙利數學家提出的ER(ErdosRenyi)隨機網絡模型[1]，隨后，WS(WattsStrogatz)/NW(NewmanWatts)小世界網絡模型[2-3]及BA(BarabasiAlbert)無標度網絡模型[4]等多種其他類型的復雜網絡模型相繼出現，復雜網絡逐漸成為一個獨立的學科而日益受到人們極大的關注，由此導致復雜性科學的產生。

　　復雜網絡起源于圖。在通常意義上的復雜網絡中，一條邊能且只能連接2個節點，但在對現實生活中的復雜系統進行研究中人們發現，通常意義上的復雜網絡并不能很好地刻畫一條邊連接多個節點的特殊網絡，如作者合著網絡等。在作者合著網絡中，一個作者著有多篇作品，同時一篇作品由多個作者合作完成。這類特殊網絡比通常意義上的復雜網絡更為復雜，于是需要用比復雜網絡更為復雜的網絡來對其進行研究，這就是超網絡[5-6]。

　　現階段對超網絡主要有兩種不同的觀點：一種觀點認為凡是可以用超圖描述的網絡均可以視為超網絡，也就是Hypernetwork型超網絡[7];另一種觀點認為由多層網絡構成的網絡可以視為超網絡，也就是Supernetwork型超網絡[8]。Hypernetwork型超網絡突破了通常意義上的復雜網絡一條邊只能連接2個節點的局限;而Supernetwork型超網絡超越了通常意義上的復雜網絡不能刻畫多層網絡的局限，分別對復雜網絡在不同的維度上進行了拓展。本文只對超圖類型的超網絡進行研究。

　　由于圖及超圖均可以通過鄰接矩陣及關聯矩陣進行描述，通過鄰接矩陣及關聯矩陣構建復雜網絡及超網絡是一種可行的方法。通過圖的鄰接矩陣及超圖的關聯矩陣構建不同類型的復雜網絡及超網絡是分析研究復雜網絡及超網絡的可行方法[9-10]。對于復雜網絡而言，度量復雜網絡的方法主要有網絡階數、網絡直徑、網絡平均路徑長度、網絡聚集系數等多種不同的方法，但這些度量方法大多針對的是無權網絡，對帶權網絡而言，很多度量方法并不適用。對帶權網絡而言，節點及邊均可以賦予權重，而且權重類型可以包括正實數、負實數、純虛數及復數等多種不同的類型。在這些度量中，網絡維數是一種便捷可行的度量方法[11]。

　　由于超圖比圖更為復雜，超網絡也比復雜網絡更為復雜。類似于圖中的節點與邊，超圖中也有與之對應的節點與超邊。對超網絡的度量方法而言，一般情況下是直接沿用復雜網絡的度量方法。采用這些方法在繼承復雜網絡度量方法優點的同時也留存了一些固有的缺陷與不足，如效率過低、普適性弱等，而且難以移植并應用于帶權超網絡等。與帶權圖類似，帶權超圖中，節點及超邊也可以賦予不同類型的權重，包括正實數、負實數、純虛數及復數等; 于是可以將度量復雜網絡的網絡維數進行拓展并應用到超網絡中，從而得到超網絡的度量方法，也就是超網絡維數。超網絡維數可以度量超網絡中節點與超邊的權重分別為正實數、負實數、純虛數及復數等多種不同類型的帶權超網絡。

　　1 預備知識

　　1.1 超圖與超網絡

　　假設集合V=(v1，v2，…，vn)是一個非空有限集，其中，若有ei≠(i=1， 2， …， |E|)，且有∪|E|i=1ei=V，則稱二元關系H=(V， E)為一個超圖。在超圖H中，V={v1， v2， …， vi， …}(1≤i≤|V|)是超圖H中所有節點的集合，E={e1， e2， …， ej， …}(1≤j≤|E|)是超圖H中所有超邊的集合。|V|表示超圖H中所有節點的數量，稱為H的階，|E|表示超圖H中所有超邊的數量，且有EP(V)\，其中P(V)表示V的冪集。若超圖H中兩個節點同屬于一條超邊，則稱這兩個節點鄰接;若兩條超邊的交集非空，則稱這兩條超邊鄰接。一般情況下研究的超圖均是無向超圖，盡管目前已有多種不同的有向超圖理論[12-14]被提出，但對有向超圖的研究并不是很多，相關的理論并不成熟，在理論與應用等方面仍存在很多需要進一步完善的地方。本文只對無向超圖進行研究。

　　超圖脫胎于圖，超圖中的超邊有別于圖中的邊，圖及超圖均可以用鄰接矩陣或關聯矩陣進行刻畫。下面分別論述超圖的鄰接矩陣及關聯矩陣。

　　定義1[15]對超圖H=(V， E)而言，其鄰接矩陣A(H)是一個|V|×|V|階的方陣，其中A(i， j)的值為在超圖的關聯二部圖中，從節點i到節點j的2長路的數目。

　　定義2[16]對超圖H=(V， E)而言，其關聯矩陣C(H)是一個|V|×|E|階的矩陣，其中，若節點vi包含在超邊ej中，則有Cij=1，否則，Cij=0。

　　超圖的鄰接矩陣及關聯矩陣的區別主要在于，鄰接矩陣一定是對稱矩陣，但關聯矩陣不一定是對稱矩陣;關聯矩陣是01矩陣，但鄰接矩陣不一定是01矩陣。若超圖中每條邊只關聯兩個節點，則超圖H就退化為普通意義上的圖，此時超圖的鄰接矩陣就是圖的鄰接矩陣。超圖與其關聯矩陣是一一對應的，一個超圖只對應一個關聯矩陣，反之也成立。但超圖與其鄰接矩陣并不一定是一一對應的，可能存在同一個鄰接矩陣對應多個超圖的情形。在超網絡的研究中，往往通過與超圖一一對應的關聯矩陣對其進行分析研究。

　　1.2 超網絡參數

　　對于圖及通常意義上的復雜網絡來說，由于一條邊只能連接2個節點，度是描述網絡的重要參數。在超網絡中，由于一條超邊可以連接任意數量的節點，描述超網絡的參數有節點度、節點超度及超邊度等，下面分別進行論述。

　　定義3[17]超圖H中超邊ei的節點度為超邊ei連接的節點個數，記為dHd(ei)。

　　定義4[17]超圖H中節點vi的節點超度為包含節點vi的超邊個數，記為dHhd(vi)。

　　定義5[10]超圖H中超邊ei的超邊度是指與超邊ei鄰接的其他超邊個數，記為dHed(ei)。

　　在超圖H的關聯矩陣C(H)中，節點度即為對應的列中非零元素的數目，表述為：

　　dHd(ei)=∑Vj=1Cij (1)

　　節點超度即為對應的行中非零元素的數目，表述為：

　　dHhd(vi)=∑Ej=1Cji (2)

　　超邊度即為與對應的列相乘結果非零的列的數目，表述為：

　　dHed(ei)=∑Vj=1Sgn(∑Vk=1CijCkj) (3)

　　通過初始超圖的迭代TracySingh積運算可以得到自相似超網絡，對自相似超網絡而言，可以通過分形維數(Fractal Dimension， FD)對其進行分析。

　　定義6[10]超圖的分形維數為其超邊包含的節點數之和的對數值和節點數與超邊數乘積對數值的比值的2倍，即：

　　FD(H)=2log∑i∈V∑j∈ECijlogVE (4)

　　定義7[10]超圖的密度是指超圖H的所有超邊包含的節點數目之和與超圖最多可包含的節點數目之和的比值，記為Density(H)，即：

　　Density(H)=∑i∈V∑j∈ECijVE (5)

　　由于非空超圖至少包含有一條非空超邊，則有1≤∑i∈V∑j∈ECij≤VE，故一般情況下，0

　　由于超圖中一條超邊可以連接任意數目的節點，即其節點度可以取任意數值。但在對超圖的研究中更多的是關注節點度相同的超圖，即k均勻超圖。在這種情況下，超圖中的每個超邊均連接有k個節點。因此，2均勻超圖就是通常意義上的圖。顯然，圖是超圖的特例，而超圖是廣義上的圖。這從另一方面論證了圖是超圖的子集，而超圖是圖的超集。