帶權(quán)超網(wǎng)絡(luò)的度量方法及其性質(zhì)

劉勝久 李天瑞 楊宗霖 珠杰

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

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);超圖;超網(wǎng)絡(luò);分形維數(shù);網(wǎng)絡(luò)維數(shù);超網(wǎng)絡(luò)維數(shù)

中圖分類號： TP393

文獻(xiàn)標(biāo)志碼：A

Measure method and properties of weighted hypernetwork

LIU Shengjiu1，2， LI Tianrui1，2*， YANG Zonglin1，2， ZHU Jie3

1.School of Information Science and Technology， Southwest Jiaotong University， Chengdu Sichuan 611756， China;

2.Sichuan Key Laboratory of Cloud Computing and Intelligent Technique， Chengdu Sichuan 611756， China;

3. School of Information Science and Technology， Tibet University， Lhasa Tibet 850000， China

Abstract：

Hypernetwork is a kind of networks which is more complex than the ordinary complex network. Hypernetwork can describe complex system existing in the real world more appropriately than complex network since every hyperedge of it can connect any number of nodes. A new method to measure hypernetwork — Hypernetwork Dimension （HD） was proposed aiming to the shortcomings and deficiencies of existing measure method of hypernetwork. Hypernetwork dimension was expressed as twice as much as the ratio of the logarithm of the sum of all nodes weights and product of corresponding hyperedges weight in all hyperedges to the logarithm of the product of sum of hyperedges weights and sum of nodes weights. The hypernetwork dimension was able to be applied to the weighted hyperworks with many different numerical types of both nodes weights and hyperedges weights， such as positive real numbers， negative real numbers， pure imaginary numbers， and even complex numbers. Finally， several important properties of the proposed hypernetwork dimension were discussed.

Key words：

complex network; hypergraph; hypernetwork; Fractal Dimension （FD）; Network Dimension （ND）; hypernetwork dimension

0?引言

圖論是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)。自18世紀(jì)歐拉對哥尼斯堡七橋問題的研究而開創(chuàng)圖論以來，圖論已在很多領(lǐng)域得到極為廣泛的應(yīng)用?，F(xiàn)代意義上復(fù)雜網(wǎng)絡(luò)的研究發(fā)軔于20世紀(jì)中葉兩位匈牙利數(shù)學(xué)家提出的ER（ErdosRenyi）隨機(jī)網(wǎng)絡(luò)模型[1]，隨后，WS（WattsStrogatz）/NW（NewmanWatts）小世界網(wǎng)絡(luò)模型[2-3]及BA（BarabasiAlbert）無標(biāo)度網(wǎng)絡(luò)模型[4]等多種其他類型的復(fù)雜網(wǎng)絡(luò)模型相繼出現(xiàn)，復(fù)雜網(wǎng)絡(luò)逐漸成為一個(gè)獨(dú)立的學(xué)科而日益受到人們極大的關(guān)注，由此導(dǎo)致復(fù)雜性科學(xué)的產(chǎn)生。

復(fù)雜網(wǎng)絡(luò)起源于圖。在通常意義上的復(fù)雜網(wǎng)絡(luò)中，一條邊能且只能連接2個(gè)節(jié)點(diǎn)，但在對現(xiàn)實(shí)生活中的復(fù)雜系統(tǒng)進(jìn)行研究中人們發(fā)現(xiàn)，通常意義上的復(fù)雜網(wǎng)絡(luò)并不能很好地刻畫一條邊連接多個(gè)節(jié)點(diǎn)的特殊網(wǎng)絡(luò)，如作者合著網(wǎng)絡(luò)等。在作者合著網(wǎng)絡(luò)中，一個(gè)作者著有多篇作品，同時(shí)一篇作品由多個(gè)作者合作完成。這類特殊網(wǎng)絡(luò)比通常意義上的復(fù)雜網(wǎng)絡(luò)更為復(fù)雜，于是需要用比復(fù)雜網(wǎng)絡(luò)更為復(fù)雜的網(wǎng)絡(luò)來對其進(jìn)行研究，這就是超網(wǎng)絡(luò)[5-6]。

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

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

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

1?預(yù)備知識

1.1?超圖與超網(wǎng)絡(luò)

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

超圖脫胎于圖，超圖中的超邊有別于圖中的邊，圖及超圖均可以用鄰接矩陣或關(guān)聯(lián)矩陣進(jìn)行刻畫。下面分別論述超圖的鄰接矩陣及關(guān)聯(lián)矩陣。

定義1[15]對超圖H=（V， E）而言，其鄰接矩陣A（H）是一個(gè)|V|×|V|階的方陣，其中A（i， j）的值為在超圖的關(guān)聯(lián)二部圖中，從節(jié)點(diǎn)i到節(jié)點(diǎn)j的2長路的數(shù)目。

定義2[16]對超圖H=（V， E）而言，其關(guān)聯(lián)矩陣C（H）是一個(gè)|V|×|E|階的矩陣，其中，若節(jié)點(diǎn)vi包含在超邊ej中，則有Cij=1，否則，Cij=0。

超圖的鄰接矩陣及關(guān)聯(lián)矩陣的區(qū)別主要在于，鄰接矩陣一定是對稱矩陣，但關(guān)聯(lián)矩陣不一定是對稱矩陣;關(guān)聯(lián)矩陣是01矩陣，但鄰接矩陣不一定是01矩陣。若超圖中每條邊只關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)，則超圖H就退化為普通意義上的圖，此時(shí)超圖的鄰接矩陣就是圖的鄰接矩陣。超圖與其關(guān)聯(lián)矩陣是一一對應(yīng)的，一個(gè)超圖只對應(yīng)一個(gè)關(guān)聯(lián)矩陣，反之也成立。但超圖與其鄰接矩陣并不一定是一一對應(yīng)的，可能存在同一個(gè)鄰接矩陣對應(yīng)多個(gè)超圖的情形。在超網(wǎng)絡(luò)的研究中，往往通過與超圖一一對應(yīng)的關(guān)聯(lián)矩陣對其進(jìn)行分析研究。

1.2?超網(wǎng)絡(luò)參數(shù)

對于圖及通常意義上的復(fù)雜網(wǎng)絡(luò)來說，由于一條邊只能連接2個(gè)節(jié)點(diǎn)，度是描述網(wǎng)絡(luò)的重要參數(shù)。在超網(wǎng)絡(luò)中，由于一條超邊可以連接任意數(shù)量的節(jié)點(diǎn)，描述超網(wǎng)絡(luò)的參數(shù)有節(jié)點(diǎn)度、節(jié)點(diǎn)超度及超邊度等，下面分別進(jìn)行論述。

定義3[17]超圖H中超邊ei的節(jié)點(diǎn)度為超邊ei連接的節(jié)點(diǎn)個(gè)數(shù)，記為dHd（ei）。

定義4[17]超圖H中節(jié)點(diǎn)vi的節(jié)點(diǎn)超度為包含節(jié)點(diǎn)vi的超邊個(gè)數(shù)，記為dHhd（vi）。

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

在超圖H的關(guān)聯(lián)矩陣C（H）中，節(jié)點(diǎn)度即為對應(yīng)的列中非零元素的數(shù)目，表述為：

dHd（ei）=∑Vj=1Cij （1）

節(jié)點(diǎn)超度即為對應(yīng)的行中非零元素的數(shù)目，表述為：

dHhd（vi）=∑Ej=1Cji （2）

超邊度即為與對應(yīng)的列相乘結(jié)果非零的列的數(shù)目，表述為：

dHed（ei）=∑Vj=1Sgn（∑Vk=1CijCkj） （3）

通過初始超圖的迭代TracySingh積運(yùn)算可以得到自相似超網(wǎng)絡(luò)，對自相似超網(wǎng)絡(luò)而言，可以通過分形維數(shù)（Fractal Dimension， FD）對其進(jìn)行分析。

定義6[10]超圖的分形維數(shù)為其超邊包含的節(jié)點(diǎn)數(shù)之和的對數(shù)值和節(jié)點(diǎn)數(shù)與超邊數(shù)乘積對數(shù)值的比值的2倍，即：

FD（H）=2log∑i∈V∑j∈ECijlogVE （4）

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

Density（H）=∑i∈V∑j∈ECijVE （5）

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

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

1.3?網(wǎng)絡(luò)維數(shù)

對基于矩陣運(yùn)算得到的自相似復(fù)雜網(wǎng)絡(luò)進(jìn)行分析，對節(jié)點(diǎn)權(quán)重及邊權(quán)重為01形式的無權(quán)自相似復(fù)雜網(wǎng)絡(luò)的分形維數(shù)進(jìn)行拓展，可以得到適用于帶權(quán)復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)維數(shù)[11]。

定義8[11]復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)維數(shù)（Network Dimension， ND）為其邊權(quán)重和的對數(shù)值與其節(jié)點(diǎn)權(quán)重和的對數(shù)值的比值，即：

ND（G）=log∑e∈Ef（e）log∑v∈Vf（v） （6）

式（6）中：f（e）為復(fù)雜網(wǎng)絡(luò)G的邊權(quán)重， f（v）為復(fù)雜網(wǎng)絡(luò)G的節(jié)點(diǎn)權(quán)重。

借助歐拉公式，可以將網(wǎng)絡(luò)維數(shù)由節(jié)點(diǎn)權(quán)重及邊權(quán)重均為正實(shí)數(shù)的帶權(quán)圖推廣到節(jié)點(diǎn)權(quán)重及邊權(quán)重為負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)等多種不同權(quán)重類型的帶權(quán)圖。歐拉公式表述為：

eix=cosx+i sinx （7）

由于正弦函數(shù)及余弦函數(shù)均為周期函數(shù)，式（7）其實(shí)是一個(gè)多值周期函數(shù)，一般情況下，只在一個(gè)周期內(nèi)對其進(jìn)行分析即可。

2?超網(wǎng)絡(luò)度量方法

本文將超網(wǎng)絡(luò)的度量方法由節(jié)點(diǎn)權(quán)重及超邊權(quán)重均為01形式的無權(quán)超網(wǎng)絡(luò)逐步推廣到節(jié)點(diǎn)權(quán)重及超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)等多種不同權(quán)重類型的帶權(quán)超網(wǎng)絡(luò)，先對無權(quán)超網(wǎng)絡(luò)進(jìn)行分析。

對節(jié)點(diǎn)權(quán)重及超邊權(quán)重為01形式的無權(quán)超網(wǎng)絡(luò)而言，其超網(wǎng)絡(luò)維數(shù)即是其分形維數(shù)，即為式（4）所示。

結(jié)合式（4）及式（6），對帶權(quán)圖的網(wǎng)絡(luò)維數(shù)進(jìn)行拓展，可以得到帶權(quán)超網(wǎng)絡(luò)的超網(wǎng)絡(luò)維數(shù)（Hypernetwork Dimension， HD），即為所有超邊包含的節(jié)點(diǎn)權(quán)重之和與對應(yīng)超邊權(quán)重乘積和的對數(shù)值與節(jié)點(diǎn)權(quán)重之和與超邊權(quán)重之和乘積對數(shù)值比值的兩倍，表述為：

HD（H）=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （8）

很顯然，對節(jié)點(diǎn)權(quán)重f（v）及超邊權(quán)重f（e）均為正實(shí)數(shù)的帶權(quán)超網(wǎng)絡(luò)而言，可以直接應(yīng)用式（8）進(jìn)行計(jì)算。對于節(jié)點(diǎn)權(quán)重及超邊權(quán)重為負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)的帶權(quán)超網(wǎng)絡(luò)而言，需要借助式（7）中歐拉公式進(jìn)行計(jì)算。

初始狀況下，假設(shè)f（v）及f（e）均為正實(shí)數(shù)，即有：f（v）∈R+，且f（e）∈R+。利用式（7）中的歐拉公式，可以分析節(jié)點(diǎn)權(quán)重及超邊權(quán)重為負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)的其他情形。

對負(fù)實(shí)數(shù)形式的節(jié)點(diǎn)權(quán)重-f（v）及超邊權(quán)重-f（e）而言，有：

log（-f（v））=logeiπf（v）

log（-f（e））=logeiπf（e）（9）

對純虛數(shù)形式的節(jié)點(diǎn)權(quán)重if（v）及超邊權(quán)重if（e）而言，有：

logif（v）=logeiπ2f（v）

logif（e）=logeiπ2f（e）（10）

對復(fù)數(shù)形式的節(jié)點(diǎn)權(quán)重（a+bi）f（v）及超邊權(quán)重（a+bi）f（e）而言，有：

log（a+bi）f（v）=loga2+b2eitan-1baf（v）

log（a+bi）f（e）=loga2+b2eitan-1baf（e）（11）

由于超網(wǎng)絡(luò)的節(jié)點(diǎn)權(quán)重及超邊權(quán)重的值均可以取正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)，本文分別對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)情形下的不同權(quán)重組合進(jìn)行分析，每一種情形下各有四種不同的權(quán)重組合。接下來分別對此進(jìn)行分析，首先是節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)的情形。

2.1?節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)的超網(wǎng)絡(luò)

對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)，超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)、復(fù)數(shù)等四種不同的權(quán)重組合進(jìn)行分析，共有四種不同的權(quán)重組合，下面分別進(jìn)行討論。

對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)、超邊權(quán)重為正實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDPP=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （12）

對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)、超邊權(quán)重為負(fù)實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDPN=2log∑e∈E（-f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈E-f（e）=

2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e）

（13）

對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)、超邊權(quán)重為純虛數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDPI=2log∑e∈E（if（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Eif（e）=

2logi∑e∈E（f（e）∑v∈ef（v））logi∑v∈Vf（v）∑e∈Ef（e）=

2logeiπ2∑e∈E（f（e）∑v∈ef（v））logeiπ2∑v∈Vf（v）∑e∈Ef（e） （14）

對節(jié)點(diǎn)權(quán)重為正實(shí)數(shù)、超邊權(quán)重為復(fù)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDPC=2log∑e∈E（a+bi）f（e）∑v∈ef（v）log∑v∈Vf（v）∑e∈E（a+bi）f（e）=2log（a+bi）∑e∈E（f（e）∑v∈ef（v））log（a+bi）∑v∈Vf（v）∑e∈Ef（e）=2loga2+b2eitan-1ba∑e∈E（f（e）∑v∈ef（v））loga2+b2eitan-1ba∑v∈Vf（v）∑e∈Ef（e）（15）

2.2?節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)的超網(wǎng)絡(luò)

接下來，對節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)，超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)、復(fù)數(shù)等四種不同的權(quán)重組合進(jìn)行分析，共有四種不同的權(quán)重組合，下面分別進(jìn)行討論。

對節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)、超邊權(quán)重為正實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDNP=2log∑e∈E（f（e）∑v∈e-f（v））log∑v∈V-f（v）∑e∈Ef（e）=2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e） （16）

對節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)、超邊權(quán)重為負(fù)實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDNN=2log∑e∈E（-f（e）∑v∈e-f（v））log∑v∈V-f（v）∑e∈E-f（e）=2log∑e∈E（f（e）∑v∈ef（v））log∑v∈Vf（v）∑e∈Ef（e） （17）

對節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)、超邊權(quán)重為純虛數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDNI=2log∑e∈E（if（e）∑v∈e-f（v））loge∑v∈V-f（v）∑e∈Eif（e）=2log-i∑e∈E（f（e）∑v∈ef（v））log-i∑v∈Vf（v）∑e∈Ef（e）=2loge32iπ∑e∈E（f（e）∑v∈ef（v））loge32iπ∑v∈Vf（v）∑e∈Ef（e） （18）

對節(jié)點(diǎn)權(quán)重為負(fù)實(shí)數(shù)、超邊權(quán)重為復(fù)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDNC=2log∑e∈E（a+bi）f（e）∑v∈e-f（v）log∑v∈V（-f（v））∑e∈E（a+bi）f（e）=2log-（a+bi）∑e∈E（f（e）∑v∈ef（v））log-（a+bi）∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π）∑v∈Vf（v）∑e∈Ef（e） （19）

2.3?節(jié)點(diǎn)權(quán)重為純虛數(shù)的超網(wǎng)絡(luò)

繼續(xù)對節(jié)點(diǎn)權(quán)重為純虛數(shù)，超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)、復(fù)數(shù)等四種不同的權(quán)重組合進(jìn)行分析，共有四種不同的權(quán)重組合，下面分別進(jìn)行討論。

對節(jié)點(diǎn)權(quán)重為純虛數(shù)、超邊權(quán)重為正實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDIP=2log∑e∈E（f（e）∑v∈eif（v））log∑v∈Vif（v）∑e∈Ef（e）=2logi∑e∈E（f（e）∑v∈ef（v））logi∑v∈Vf（v）∑e∈Ef（e）=2logeiπ2∑e∈E（f（e）∑v∈ef（v））logeiπ2∑v∈Vf（v）∑e∈Ef（e） （20）

對節(jié)點(diǎn)權(quán)重為純虛數(shù)、超邊權(quán)重為負(fù)實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDIN=2log∑e∈E（-f（e）∑v∈eif（v））loge∑v∈Vif（v）∑e∈E-f（e）=2log-i∑e∈E（f（e）∑v∈ef（v））log-i∑v∈Vf（v）∑e∈Ef（e）=

2loge32iπ∑e∈E（f（e）∑v∈ef（v））loge32iπ∑v∈Vf（v）∑e∈Ef（e） （21）

對節(jié)點(diǎn)權(quán)重為純虛數(shù)、超邊權(quán)重為純虛數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDII=2log∑e∈E（if（e）∑v∈eif（v））log∑v∈Vif（v）∑e∈Eif（e）=2log-∑e∈E（f（e）∑v∈ef（v））log-∑v∈Vf（v）∑e∈Ef（e）=2logeiπ∑e∈E（f（e）∑v∈ef（v））logeiπ∑v∈Vf（v）∑e∈Ef（e） （22）

對節(jié)點(diǎn)權(quán)重為純虛數(shù)、超邊權(quán)重為復(fù)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDIC=2log∑e∈E（a+bi）f（e）∑v∈eif（v）log∑v∈Vif（v）∑e∈E（a+bi）f（e）=2log（a+bi）i∑e∈E（f（e）∑v∈ef（v））log（a+bi）i∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π2）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π2）∑v∈Vf（v）∑e∈Ef（e） （23）

2.4?節(jié)點(diǎn)權(quán)重為復(fù)數(shù)的超網(wǎng)絡(luò)

最后，本文對節(jié)點(diǎn)權(quán)重為復(fù)數(shù)，超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)、復(fù)數(shù)四種不同的權(quán)重組合進(jìn)行分析，共有四種不同的權(quán)重組合，下面分別進(jìn)行討論。

對節(jié)點(diǎn)權(quán)重為復(fù)數(shù)、超邊權(quán)重為正實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDCP=2log∑e∈Ef（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈Ef（e）=2log（a+bi）∑e∈E（f（e）∑v∈ef（v））log（a+bi）∑v∈Vf（v）∑e∈Ef（e）=2loga2+b2eitan-1ba∑e∈E（f（e）∑v∈ef（v））loga2+b2eitan-1ba∑v∈Vf（v）∑e∈Ef（e） （24）

對節(jié)點(diǎn)權(quán)重為復(fù)數(shù)、超邊權(quán)重為負(fù)實(shí)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDCN=2log∑e∈E-f（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈E（-f（e））=2log-（a+bi）∑e∈E（f（e）∑v∈ef（v））log-（a+bi）∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π）∑v∈Vf（v）∑e∈Ef（e） （25）

對節(jié)點(diǎn)權(quán)重為復(fù)數(shù)、超邊權(quán)重為純虛數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDCI=2log∑e∈Eif（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈Eif（e）=2log（a+bi）i∑e∈E（f（e）∑v∈ef（v））log（a+bi）i∑v∈Vf（v）∑e∈Ef（e）=

2loga2+b2ei（tan-1ba+π2）∑e∈E（f（e）∑v∈ef（v））loga2+b2ei（tan-1ba+π2）∑v∈Vf（v）∑e∈Ef（e） （26）

對節(jié)點(diǎn)權(quán)重為復(fù)數(shù)、超邊權(quán)重為復(fù)數(shù)的超網(wǎng)絡(luò)來說，其超網(wǎng)絡(luò)維數(shù)為：

HDCC=2log∑e∈Ef（a+bi）（e）∑v∈e（a+bi）f（v）log∑v∈V（a+bi）f（v）∑e∈E（a+bi）f（e）=2log（a+bi）2∑e∈E（f（e）∑v∈ef（v））log（a+bi）2∑v∈Vf（v）∑e∈Ef（e）=2log（a2+b2）eitan-12aba2-b2∑e∈E（f（e）∑v∈ef（v））log（a2+b2）eitan-12aba2-b2∑v∈Vf（v）∑e∈Ef（e） （27）

至此，本文分析了節(jié)點(diǎn)權(quán)重及超邊權(quán)重分別為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)等多種不同類型的權(quán)重組合，共16種情形。通過2.1～2.4節(jié)，可以較為直觀地看出16種不同的權(quán)重組合之間的關(guān)系。本文下面對這16種不同的權(quán)重組合進(jìn)行分析，實(shí)際上就是對式（12）～（27）的16個(gè)公式進(jìn)行分析。

3?超網(wǎng)絡(luò)維數(shù)關(guān)系研究

通過上述分析發(fā)現(xiàn)，在16種不同的情形中，共有8種不同的類型，對8種不同的等價(jià)類進(jìn)行分析，可以得到如圖1所示的關(guān)系圖。

從圖1可以看出，從處于中心的節(jié)點(diǎn)權(quán)重及超邊權(quán)重均為正實(shí)數(shù)的帶權(quán)超網(wǎng)絡(luò)出發(fā)，可以逐步轉(zhuǎn)化到其他15種權(quán)重類別的帶權(quán)超網(wǎng)絡(luò)，而且16種帶權(quán)超網(wǎng)絡(luò)共有8種超網(wǎng)絡(luò)維數(shù)。于是，在實(shí)際的分析研究中，只需要對8種不同的帶權(quán)超網(wǎng)絡(luò)進(jìn)行研究即可全部涵蓋所有的16種帶權(quán)超網(wǎng)絡(luò)。

進(jìn)一步，本文對圖1中列出的8種超網(wǎng)絡(luò)類別進(jìn)行分析，可以得到圖2所示的超網(wǎng)絡(luò)維數(shù)關(guān)系圖。

從圖2可以看出，8種不同的超網(wǎng)絡(luò)維數(shù)呈現(xiàn)出極為對稱的上下對稱、左右對稱的軸對稱關(guān)系。于是，在深入的分析研究中，只需對4種不同的超網(wǎng)絡(luò)維數(shù)進(jìn)行分析即可推廣并應(yīng)用到其他類型的帶權(quán)超網(wǎng)絡(luò)中。

4?超網(wǎng)絡(luò)維數(shù)性質(zhì)研究

在論述了超網(wǎng)絡(luò)的度量方法——超網(wǎng)絡(luò)維數(shù)之后，本文對超網(wǎng)絡(luò)維數(shù)的性質(zhì)進(jìn)行分析研究。由于對超網(wǎng)絡(luò)的研究均是從最簡單的無向無權(quán)超圖開始的，本文對超網(wǎng)絡(luò)維數(shù)性質(zhì)的研究也從最簡單的無向無權(quán)超圖開始，再將其推廣到更一般的其他情形。

定理1?任意超網(wǎng)絡(luò)的超網(wǎng)絡(luò)維數(shù)不小于0。

證明?根據(jù)定義，對式（4）進(jìn)行分析，可以得到：

HD（H）=2log∑i∈V∑j∈ECijlogVE≥2log1logVE=0 （28）

定理1得證。

對由不同超圖得到的TracySingh積超圖進(jìn)行分析，則可以得到如下定理。

定理2?對于n個(gè)超圖H（i）（1≤i≤n）的TracySingh積超圖H（n）而言，H（n）的超網(wǎng)絡(luò)維數(shù)是所有構(gòu)成此TracySingh積超圖的H（i）（1≤i≤n）的超邊包含的節(jié)點(diǎn)數(shù)目的對數(shù)值總和與節(jié)點(diǎn)數(shù)目與超邊數(shù)目乘積對數(shù)值總和的比值的兩倍，用公式表述，即：

若有：

H（n）=ni=1H（i） （29）

則有：

HD（H（n））=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i） （30）

證明?根據(jù)TracySingh積超圖的定義，則有：

V（n）=∏ni=1V（i）E（n）=∏ni=1E（i）∑j∈V（n）k∈E（n）Cjk=∏ni=1∑j∈V（i）k∈E（i）Cjk（31）

將式（31）代入式（4），則可以得到：

HD（H（n））=2log∑j∈V（n）k∈E（n）CjklogV（n）E（n）=2log∏ni=1∑j∈V（i）k∈E（i）Cjklog∏ni=1V（i）∏ni=1E（i）=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i）（32）

定理2得證。

若由一個(gè)超圖進(jìn)行n次迭代TracySingh積運(yùn)算，則得到的所有TracySingh積超圖的超網(wǎng)絡(luò)維數(shù)都相等，而且都等于初始超圖的超網(wǎng)絡(luò)維數(shù)，則可以得到如下引理。

引理1?迭代TracySingh積超圖的超網(wǎng)絡(luò)維數(shù)都相等，而且都等于初始超圖的超網(wǎng)絡(luò)維數(shù)。

證明?對式（32）進(jìn)行分析，則可以得到：

HD（H（n））=2∑ni=1log∑j∈V（i）k∈E（i）Cjk∑ni=1logV（i）E（i）=2nlog∑j∈V（i）k∈E（i）CjknlogV（i）E（i）=2log∑j∈V（1）k∈E（1）CjklogV（1）E（1）（33）

引理1得證。

定理3?對k均勻超圖H=（V， E）而言，其超網(wǎng)絡(luò)維數(shù)可以表述為：

HD（H）=2logkElogVE （34）

證明?在k均勻超圖H=（V， E）中，其一條超邊連接有k個(gè)節(jié)點(diǎn)，則有：

∑i∈V∑j∈ECij=kE （35）

將式（35）代入式（4），即得式（34）。定理3得證。

由于圖是超圖的特例，圖就是2均勻超圖，對圖形式的2均勻超圖進(jìn)行分析，則可以得到如下引理。

引理2?對圖形式的2均勻超圖H=（V， E）而言，其超網(wǎng)絡(luò)維數(shù)可以表述為：

HD（H）=2log2ElogVE （36）

證明?根據(jù)2均勻超圖的定義，結(jié)合定理2，引理2顯然成立。引理2得證。

從引理2可以得知，分別從圖及超圖的視角度量通常意義上的圖，得到的網(wǎng)絡(luò)維數(shù)及超網(wǎng)絡(luò)維數(shù)可能并不一致。

定理4?對超圖H=（V， E）而言，其網(wǎng)絡(luò)維數(shù)可以表述為：

HD（H）=2+2logDensity（H）logVE （37）

證明?將式（5）代入式（4），有：

HD（H）=2logVEDensity（H）logVE=2logVE+2logDensity（H）logVE=2+2logDensity（H）logVE （38）

定理4得證。

由于0

5?結(jié)語

超圖是廣義上的圖，超網(wǎng)絡(luò)是較通常意義上的復(fù)雜網(wǎng)絡(luò)更為復(fù)雜的一種網(wǎng)絡(luò)。針對現(xiàn)有超網(wǎng)絡(luò)的度量方法并不能全面刻畫超網(wǎng)絡(luò)的各項(xiàng)特性，本文從自相似超網(wǎng)絡(luò)的分形維數(shù)出發(fā)，結(jié)合復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)維數(shù)，提出了一種度量超網(wǎng)絡(luò)的新方法——超網(wǎng)絡(luò)維數(shù)，具體表述為超網(wǎng)絡(luò)中所有超邊包含的節(jié)點(diǎn)權(quán)重之和與對應(yīng)超邊權(quán)重乘積之和的對數(shù)值與節(jié)點(diǎn)權(quán)重之和與超邊權(quán)重之和乘積對數(shù)值的比值的兩倍。本文提出的超網(wǎng)絡(luò)維數(shù)可以應(yīng)用于節(jié)點(diǎn)權(quán)重及超邊權(quán)重為正實(shí)數(shù)、負(fù)實(shí)數(shù)、純虛數(shù)及復(fù)數(shù)等多種不同數(shù)值類型的帶權(quán)超網(wǎng)絡(luò)。最后，本文以最簡單的無向無權(quán)超圖為例，論述了所提出的超網(wǎng)絡(luò)維數(shù)的若干重要性質(zhì)。后續(xù)研究的重點(diǎn)在于結(jié)合現(xiàn)實(shí)生活中真實(shí)復(fù)雜系統(tǒng)的具體特性對所提出的超網(wǎng)絡(luò)維數(shù)進(jìn)行深入細(xì)致的分析，尤其是對具體實(shí)例及實(shí)驗(yàn)仿真進(jìn)行深入的分析研究，同時(shí)探討動(dòng)態(tài)環(huán)境下超網(wǎng)絡(luò)維數(shù)的演化機(jī)理及演進(jìn)趨勢等。

參考文獻(xiàn) （References）

[1]ERDOS P， RENYI A. On random graphs I[J]. Publicationes Mathematicae， 1959， 6： 290-297.

[2]WATTS D J， STROGATZ S H. Collective dynamics of ′smallworld′ networks[J]. Nature， 1998， 393： 440-442.

[3]NEWMAN M E J， WATTS D J. Renormalization group analysis of the smallworld network model[J]. Physics Letter A， 1999， 293（4/5/6）： 341-346.

[4]BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）： 509-512.

[5]ERDOS P， HAJNAL A. On the chromatic number of graphs and set systems[J]. Acta Mathematica Academiae Scientiarum Hungarica， 1966， 17： 61-99.

[6]BERGE C. Graphs and Hypergraphs[M]. Amsterdam： NorthHolland Publishing Company， 1973： 3-11.

[7]ESTRADA E， RODR?GUEZVEL?ZQUEZ J A. Subgraph centrality in complex networks[J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 71（5 Pt 2）：056103.

[8]NAGURNEY A， DONG J. Supernetworks： DecisionMaking for the Information Age[M]. Cheltenham： Edward Elgar Publishing， 2002： 844-847.

[9]劉勝久， 李天瑞， 洪西進(jìn)， 等. 基于矩陣運(yùn)算的復(fù)雜網(wǎng)絡(luò)構(gòu)建方法[J]. 中國科學(xué)： 信息科學(xué)， 2016， 46（5）： 610-626. （LIU S J， LI T R， HORNG S J， et al. Complex network construction based on matrix operation[J]. SCIENTIA SINICA Informationis， 2016， 46（5）： 610-626.）

[10]劉勝久， 李天瑞， 洪西進(jìn)， 等. 超網(wǎng)絡(luò)模型構(gòu)建及特性分析[J]. 計(jì)算機(jī)科學(xué)與探索， 2017， 11（2）： 194-211. （LIU S J， LI T R， HORNG S J， et al. Hypernetwork model and its properties[J]. Journal of Frontiers of Computer Science and Technology， 2017， 11（2）： 194-211.）

[11]劉勝久， 李天瑞， 劉小偉. 網(wǎng)絡(luò)維數(shù)：一種度量復(fù)雜網(wǎng)絡(luò)的新方法[J]. 計(jì)算機(jī)科學(xué)， 2019， 46（1）： 51-56. （LIU S J， LI T R， LIU X W. Network dimension： a new measure for complex networks[J]. Computer Science， 2019， 46（1）： 51-56.）

[12]GALLO G， LONGO G， NGUYEN S. Directed hypergraphs and applications[J]. Discrete Applied Mathematics， 1993， 42（2/3）： 177-201.

[13]ERGINCAN F， GREGORY D A. Directed Moore hypergraphs[J]. Discrete Applied Mathematics， 1995， 63（2）： 117-127.

[14]黃汝激. 超網(wǎng)絡(luò)的有向k超樹分析法[J]. 電子科學(xué)學(xué)刊， 1987， 9（3）： 244-255. （HUANG R J. Directedkhypertree method for hypernetwork analysis[J]. Journal of Electronics， 1987， 9（3）： 244-255.）

[15]FENG K， LI W. Spectra of hypergraphs and applications[J]. Journal of Number Theory， 1996， 60（1）： 1-22.

[16]王建方. 超圖的理論基礎(chǔ)[M]. 北京： 高等教育出版社， 2006： 1-3. （WANG J F. Theoretical Principle of Hypergraph[M]. Beijing： Higher Education Press， 2006： 1-3.）

[17]胡楓， 趙海興， 馬秀娟. 一種超網(wǎng)絡(luò)演化模型構(gòu)建及特性分析[J]. 中國科學(xué)： 物理學(xué) 力學(xué) 天文學(xué)， 2013， 43（1）： 16-22. （HU F， ZHAO H X， MA X J. An evolving hypernetwork model and its properties[J]. SCIENTIA SINICA Physica， Mechanica & Astronomica， 2013， 43（1）： 16-22.）

This work is partially supported by the National Natural Science Foundation of China （61262058， 61751216）.

LIU Shengjiu， born in 1988， Ph. D. His research interests include complex network， natural language processing， data mining.

LI Tianrui， born in 1969， Ph. D.， professor. His research interests include rough set， granular computing， data mining.

YANG Zonglin， born in 1994， M. S. candidate. His research interests include natural language processing， cloud computing.

ZHU Jie， born in 1973， Ph. D.， professor. His research interests include natural language processing， data mining.