超網絡能量研究與應用

劉勝久，李天瑞+，劉 佳，謝 鵬

1.西南交通大學信息科學與技術學院，成都 611756

2.四川省云計算與智能技術高校重點實驗室，成都 611756

傳統意義上的圖及復雜網絡一條邊能且只能連接兩個節點，描述圖或復雜網絡可以用等價的鄰接矩陣或關聯矩陣。但現實生活中往往出現一條邊連接有多個節點的復雜系統，在這種情況下，傳統意義上的圖及復雜網絡對此無能為力，需要用比通常意義上的復雜網絡更為復雜的網絡對其進行描述，這就是超網絡。

超網絡源于超圖，其一條超邊能連接任意多個節點的特性使得其能更好地刻畫分析作品合著網絡等其他形式的復雜系統[1-3]。描述超網絡的常用方法是與超網絡一一對應的關聯矩陣，對超網絡的研究使得超網絡模型[4]、超網絡維數[5]、超網絡多重分形[6]等眾多研究成果相繼出現，帶權超網絡也逐步取代無權超網絡，成為超網絡研究新的熱點。

圖能量是代數圖論及理論化學研究的重要課題，在分析烴類化合物的總π能量中有著重要作用。對圖能量的研究是從對無向圖的能量研究開始的[7]，并漸次推廣到有向圖[8]、混合圖[9]等其他多種類型的圖。無向圖的圖能量定義為其對應的鄰接矩陣的特征值絕對值之和，一些基于類似定義的圖能量的各種變種，如距離能量[10]、擬Laplacian能量[11]、關聯能量[12]、斜能量[8]、Hermitian 能量[9]、匹配能量[13]、Laplacian 能量[14]、無符號Laplacian 能量[15]、Von Neumann 能量[16]、距離Laplacian 能量[17]、距離無符號Laplacian 能量[17]等先后提出，并取得很多重要研究成果。

大多數圖能量及其變種均是基于矩陣特征值計算的，對大規模圖并不適用。從分形維數出發，針對復雜網絡提出了網絡維數[18]，并應用于無向圖及有向圖，得到了對應的網絡能量[19-20]。無向圖及有向圖的網絡能量擺脫了矩陣特征值計算的繁瑣操作，且與無向圖的圖能量、有向圖的斜能量等多種類似能量之間存在著密切的關聯。本文中，結合超網絡的超網絡維數，借助網絡能量，嘗試將超網絡維數應用于超網絡中，提出超網絡的超網絡能量，并分析超網絡能量的若干重要性質。

1 預備知識

1.1 圖能量

圖是由節點及連接節點之間的邊構成的。通常意義上，根據圖中的邊是否帶有方向，可以將圖劃分為無向圖、有向圖、混合圖三類。無向圖的所有邊均沒有方向，有向圖中的所有邊都有方向，混合圖中部分邊有方向，部分邊沒有方向。對于無向圖、有向圖、混合圖均有不同的能量計算方法。

對無向圖G=(V,E)而言，其鄰接矩陣可記為A(G)。其中，若G中節點vi與vj之間存在一條無向邊，則Aij=Aji=1；若節點vi與vj之間不存在邊，則Aij=Aji=0 。G的圖能量E(G)定義為G的鄰接矩陣A(G)的所有特征值絕對值之和，即有[7]：

式中，λ1A(G),λ2A(G),…,λi A(G),…,λn A(G)分別表示A(G)的各個特征值。

對有向圖Gσ而言，可通過對無向圖G的所有邊賦予一個方向而得到，其斜鄰接矩陣可記為S(Gσ)。其中，若Gσ中節點vi與vj之間存在一條有向邊，則Sij=-Sji=1；若節點vi與vj之間不存在邊，則Sij=Sji=0。Gσ的斜能量ε(Gσ)定義為Gσ的斜鄰接矩陣S(Gσ)的所有特征值絕對值之和，即[8]：

式中，λ1S(Gσ),λ2S(Gσ),…,λiS(Gσ),…,λnS(Gσ)分別表示S(Gσ)的各個特征值。

對混合圖M而言，可通過對無向圖G的部分邊賦予一個方向而得到，其Hermitian 鄰接矩陣可記為H(M)。其中，若M中節點vi與vj之間存在一條有向邊，則Hij=-Hji=i；若節點vi與vj之間存在一條無向邊，則Hij=Hji=1；若節點vi與vj之間不存在任何邊，則Hij=Hji=0。M的Hermitian 能量εH(M)定義為M的Hermitian 鄰接矩陣H(M)的所有特征值絕對值之和，即[9]：

式中，λ1H(M),λ2H(M),…,λiH(M),…,λnH(M)分別表示H(M)的各個特征值。

無向圖的圖能量、有向圖的斜能量、混合圖的Hermitian 能量分別是無向圖、有向圖、混合圖能量研究的基礎，這些能量均是基于矩陣特征值計算得到的。一些其他類似的各種變種能量也不時出現，如新近提出的混合圖的Hermitian 關聯能量[21]等。

1.2 超網絡

傳統意義上的圖及復雜網絡一條邊能且只能連接兩個節點，超圖及超網絡的一條邊可以連接任意多個節點。圖是超圖的子集，超圖是圖的超集，超網絡也是傳統意義上復雜網絡的超集。超圖及超網絡能較圖及復雜網絡刻畫更為復雜多樣的復雜系統。

對于圖及復雜網絡來說，鄰接矩陣及關聯矩陣是兩種主要的描述方法，這兩種描述方法是等價的，可以相互轉換，而且與原始的圖及復雜網絡也是一一對應的。超圖及超網絡也可以用類似的鄰接矩陣及關聯矩陣進行刻畫，但超圖的鄰接矩陣與超圖本身并不是一一對應的，一般情況下，對超圖往往用與其一一對應的關聯矩陣進行刻畫。超網絡由節點及超邊組成，由于其一條超邊可以連接任意多個節點，描述超網絡的參數有節點度、節點超度及超邊度等[4]。

定義1[22]對無權超網絡H=(V,E)而言，|V|表示H中所含有的節點的數量，稱為H的階，|E|表示H中所含有的超邊的數量，其關聯矩陣C(H)是一個|V|×|E|階的矩陣，其中，若節點vi包含在超邊ej中，則有Cij=1，否則，Cij=0。

定義2[22]對無權超網絡H=(V,E)而言，其密度是指H的所有超邊包含的節點數目之和與其最多可包含的節點數目之和的比值，記為ρ(H)，即：

從分形維數的視角出發，可以得到無權超網絡及帶權超網絡的超網絡維數。無權超網絡的超網絡維數就是其對應的分形維數。一般情況下，研究的均是無權超網絡。由于超網絡的一條超邊可以連接任意多個節點，即其節點度可以取任意數值，分析起來比較復雜，人們更多關注的是節點度相同的超圖，即k-均勻超圖。k-均勻超圖中的每個超邊均連接有k個節點。顯然，2-均勻超圖就是通常意義上的圖。

定義3[4]對無權超網絡H而言，其超網絡維數HD(H)為其超邊包含的節點數之和的對數值和節點數與超邊數乘積對數值的比值的兩倍，表述為：

結合式（4），式（5）可改寫為：

當H為k-均勻超圖時，此時有：

定義4[5]對帶權超網絡H而言，其超網絡維數HD(H)為其所有超邊包含的節點權重之和與對應超邊權重乘積和的對數值與節點權重之和與超邊權重之和乘積對數值比值的兩倍，表述為：

觀察式（5）及式（8）可以發現，當帶權超網絡的節點權重f(v)及超邊權重f(e)均為1 時，帶權超網絡即相當于無權超網絡，此時式（8）退化為式（5）。

一般情況下，超圖的超邊數目與其節點數目不一定相等，也即超圖的關聯矩陣不一定是方陣，這將導致通過矩陣特征值計算得到圖能量的常用方法不再適用，即通常意義上圖能量的計算方法并不能直接推廣應用到超圖及超網絡中。實際上，迄今為止，尚無針對超圖及超網絡能量的研究。

1.3 網絡能量

網絡能量是基于網絡維數得到的。對無向圖G=(V,E)而言，其中，|V|=n，|E|=m，其網絡維數ND(G)表述為[18]：

于是，可以得到圖G的網絡能量NE(G)，表述如下[19]：

圖G的網絡能量NE(G)計算擺脫了矩陣特征值計算的低效操作，且與圖G的圖能量E(G)之間存在多個共同的上限，與距離能量、擬Laplacian 能量、關聯能量、匹配能量等也存在較為密切的關聯。

可以將無向圖G的網絡能量推廣并應用到有向圖Gσ，得到有向圖Gσ的網絡能量NE(Gσ)，表述如下[20]：

有向圖Gσ的網絡能量NE(Gσ)與有向圖Gσ的斜能量ε(Gσ)及其原始圖G的網絡能量NE(G)之間也存在較為密切的關聯。由于混合圖是介于無向圖與有向圖之間的一類圖，兼具無向圖與有向圖的特點，實際上，也可以將網絡能量應用于混合圖中。

由于無向圖及有向圖的網絡能量均是通過網絡維數而得到的，超網絡也存在與之對應的超網絡維數。下面，本文結合網絡能量及超網絡的超網絡維數提出超網絡的超網絡能量，并對其進行深入的分析研究。

2 超網絡能量研究

2.1 超網絡能量

超網絡的超網絡維數是基于與其一一對應的關聯矩陣定義的，借鑒網絡能量，給出超網絡H的超網絡能量HE(H)，表述如下：

對超網絡密度為ρ(H)的超網絡H而言，其超網絡能量HE(H)可以等價地表述為：

對k-均勻超圖而言，其超網絡能量HE(H)可以等價地表述為：

對式（14）進行分析，可以得到：

當|V|=|E|時，即節點數目與超邊數目相等時，有：

若k=1，此時H一條超邊只包含有1 個節點，即H為各個孤立的節點，此時：

觀察式（17）可以發現，此時超網絡H的超網絡能量即為對2-正則圖，即無向環圖C|V|的每條邊賦予方向所得到的有向圖的網絡能量。

若k=2，此時H一條超邊只包含有2 個節點，即H為通常意義上的圖，此時：

觀察式（18）可以發現，此時超網絡H的超網絡能量即為對2-正則圖，即無向環圖C|V|的網絡能量。

2.2 超網絡能量分析

通過上面的分析可以發現，k-均勻超圖的超網絡能量與正則無向圖及得到的有向圖的網絡能量之間的關聯。于是，得到如下的定理。

定理1對2-均勻超圖H=(V,E)而言，當|V|=|E|，其超網絡能量HE(G)等于其對應的單圈圖G=(V,E)網絡能量NE(G)，即：

證明對單圈圖G而言，其網絡能量為：

結合式（18），即得式（19）。定理1 顯然成立。

定理2對k-均勻超圖H=(V,E) 而言，當|V|=|E|時，H的超網絡能量HE(H)即是含有|V|個節點的k-正則無向圖G的網絡能量NE(G)。

證明根據超網絡的超網絡能量及無向圖的網絡能量的定義，定理2 顯然成立。

定理3對k-均勻超圖H=(V,E) 而言，當|V|=|E|時，H的超網絡能量HE(H)即是對含有|V|個節點的2k-正則無向圖G的每條邊賦予方向所得到的有向圖Gσ的網絡能量NE(Gσ)。

證明根據超網絡的超網絡能量及有向圖的網絡能量的定義，定理3 顯然成立。

至此，將k-均勻超圖、k-正則無向圖及2k-正則無向圖得到的有向圖通過超網絡能量與網絡能量聯系起來。定理1、定理2、定理3 分別從不同的側面論述了圖是超圖的子集，超圖是圖的超集。對無向圖及有向圖的網絡能量的研究同樣可以移植到同階的超網絡的超網絡能量的研究中。下面，本文對超網絡的超網絡能量性質進行深入的分析研究。

3 超網絡能量性質

上文通過對超網絡的超網絡維數及網絡能量的分析研究，提出了超網絡的超網絡能量，下面對超網絡的超網絡能量性質進行分析研究。對于一般的超網絡而言，計算其精確的超網絡能量較為復雜，本文主要對超網絡的超網絡能量的下限及上限進行分析研究。先對超網絡能量的下限進行研究。

定理4對超網絡H=(V,E)而言，其超網絡能量HE(H)的下限為0，即：

證明根據超網絡能量定義，定理4 顯然成立。

式（21）中等號成立的條件是H為零超圖或空超圖，即H不含有節點或超邊。

一般情況下，非空超圖至少含有一條非空超邊，于是得到下面的定理。

定理5對非空超網絡H=(V,E)而言，其超網絡能量HE(H)的下限為1，即：

證明非空超網絡至少含有一條非空超邊，此超邊至少連接有1 個節點。根據超網絡能量定義，定理5 顯然成立。

式（22）中等號成立的條件是H僅含有一條連接有1 個節點的超邊。

下面對超網絡能量的上限進行研究。

定理6對超網絡H=(V,E)而言，其超網絡能量HE(H)的上限滿足下式：

證明對超網絡H的超網絡能量HE(H)進行分析，有：

定理6 顯然成立。

定理7對超網絡H=(V,E)而言，其超網絡能量HE(H)的上限滿足下式：

證明對式（13）進行分析，由于超網絡H的超網絡密度0 ≤ρ(H)≤1，當ρ(H)=1 時，超網絡H的超網絡能量HE(H)取最大值，此時超網絡能量HE(H)為：

定理7 顯然成立。

式（26）中等號成立的條件為超網絡H的超網絡密度ρ(H)為1，此時超網絡H的每一條超邊均連接有|V|個節點，即此時的超網絡H為|V|-均勻超圖。于是，可以得到如下的引理。

引理1k-均勻超圖的超網絡能量HE(H)的上限滿足下式：

證明k-均勻超圖中，k的最大值為k=|V|，代入式（14），即得：

引理1 顯然成立。

當超網絡的節點數目與超邊數目相等時，可以得到如下的引理。

引理2對超網絡H=(V,E)而言，當|V|=|E|時，其超網絡能量HE(H)的上限滿足下式：

證明在式（27）中，令|V|=|E|，即得式（30）。引理2 顯然成立。

其實，式（30）也是|V|階無向圖的網絡能量的上限[19]。即當|V|=|E|時，超網絡H的超網絡能量HE(H)與對應的同階無向圖G的網絡能量NE(G)具有相同的上限。

定理8對于n個超圖H(i)(1 ≤i≤n)的Tracy-Singh積超圖H(n)而言，H(n)的超網絡能量HE(H(n))可以表述如下：

證明對于H(n)而言，其節點數|V(n)|、超邊數|E(n)|、超網絡維數HD(n)分別如下[4-5]：

根據超網絡維數的定義，將式（32）代入式（12），即得式（31）。定理8 顯然成立。

對一個初始超圖的迭代Tracy-Singh 積超圖進行分析，則可以得到如下的引理。

引理3初始超圖H的迭代Tracy-Singh 積超圖H(n)的超網絡能量HE(H(n))是初始超圖H的超網絡能量HE(H)的n次方，即：

證明對于H(n)而言，其超網絡維數HE(H(n))等于H的超網絡維數HD(H)。H(n)的節點數|V(n)|、超邊數|E(n)|、超網絡維數HD(n)分別如下：

根據超網絡維數的定義，將式（34）代入式（12），則有：

引理3 顯然成立。

特別的，當初始超圖H的超網絡密度ρ(H)為1時，可以得到如下的引理。

引理4對于超網絡密度為1 的初始超網絡而言，其迭代Tracy-Singh 積超圖H(n)的超網絡能量HE(H(n))可表述為：

證明超網絡密度ρ(H)為1 的超網絡H具有最大的超網絡能量。初始超網絡H的超網絡能量HE(H)為：

根據引理3，迭代Tracy-Singh 積超圖H(n)的超網絡能量HE(H(n))為：

引理4 顯然成立。

本文對一般情形下的超網絡進行分析，則可以得出如下的結論。

定理9密度為ρ的超網絡H=(V,E)的超網絡能量上限滿足下式：

證明對式（13）進行分析：

定理9 顯然成立。

當超網絡為k-均勻超圖時，可以得到如下的引理。

引理5對密度為ρ的k-均勻超網絡H=(V,E)而言，其超網絡能量HE(H)的上限滿足下式：

證明在密度為ρ的k-均勻超網絡H=(V,E)中，有ρ|V||E|=k|E|，即有：

將式（43）代入式（39），即得式（42）。引理5 顯然成立。

此外，當超網絡的節點數目與超邊數目相等時，可以得到如下的引理。

引理6對密度為ρ的超網絡H=(V,E)而言，當|V|=|E|時，其超網絡能量HE(H)的上限滿足下式：

證明在式（39）中，令|V|=|E|，即得式（44）。引理6 顯然成立。

其實，式（44）也是|V|階無向隨機圖Gn(ρ)的網絡能量的上限[19]。即當|V|=|E|時，密度為ρ的超網絡H的超網絡能量HE(H)與對應的同階且連接概率為ρ的無向隨機圖G的網絡能量NE(G)具有相同的上限。

定理10對超網絡H=(V,E) 而言，當時，其超網絡能量HE(H)的上限滿足下式：

證明根據式（12）所示的超網絡的超網絡能量的表述，欲證定理10，只需證下式即可：

令f(x)=，可以發現，當x≤n時，f(x)為增函數，當x≥n時，f(x)為減函數，即f(x)的一階導數f′(x)在區間(-∞,n)為非負數，在區間(n,+∞)為非正數：

當且僅當x=n時，f(x)的一階導數f′(x)=0。于是，有：

定理10 顯然成立。

將式（4）代入式（45），可以得到如下的引理。

引理7對密度為ρ的超網絡H=(V,E)而言，當時，其超網絡能量HE(H)的上限滿足下式：

證明將式（4）代入式（45），即得式（50）。引理7顯然成立。

進一步，當超網絡的節點數目與超邊數目相等時，可以得到如下的引理。

引理8對密度為ρ的超網絡H=(V,E)而言，當且|V|=|E|時，其超網絡能量HE(H)的上限滿足下式：

證明將|V|=|E|代入式（50），即得式（51）。引理8 顯然成立。

4 結束語

超網絡由節點和超邊組成，其一條超邊能連接任意多個節點的特性使得其比通常意義上的復雜網絡更為復雜，也能對更多的復雜系統進行刻畫。圖能量已在無向圖、有向圖、混合圖等多種不同類型的圖中得到較為成功的應用，在代數圖論及理論化學等領域有著廣泛的應用前景。傳統意義上的圖能量基于矩陣特征值計算，無法很好地推廣應用到大規模圖中。目前尚無對超網絡的能量的研究。先前將網絡能量應用于無向圖及有向圖中，規避了矩陣特征值計算的繁瑣操作，并論述了網絡能量的重要性質及與其他類似能量之間的關聯。本文將網絡能量應用于超網絡中，結合超網絡的超網絡維數，提出了超網絡的超網絡能量，并分析了超網絡能量的若干重要性質，給出了超網絡的超網絡能量的上下限及與圖的網絡能量之間的關聯。后續工作的重點在于對超網絡的超網絡能量進行深入的分析，并嘗試對有向超網絡、混合超網絡及帶權超網絡等其他類型超網絡的超網絡能量進行研究。