王眾托

(大連理工大學(xué)系統(tǒng)工程研究所,大連 116085)

關(guān)于超網(wǎng)絡(luò)的一點思考

王眾托

(大連理工大學(xué)系統(tǒng)工程研究所,大連 116085)

在探討超網(wǎng)絡(luò)的內(nèi)涵時提到,除了Nagurney所著重研究的多層超網(wǎng)絡(luò)之外,還有一類基于超圖(hypergragh)的超網(wǎng)絡(luò)(hypernetwork)值得關(guān)注.超圖的特點是圖中的邊可以連接兩個以上的節(jié)點,這對研究信息與知識網(wǎng)絡(luò)的研究與應(yīng)用會有獨特的用途.以知識的超網(wǎng)絡(luò)表述為例,介紹了基于超圖的超網(wǎng)絡(luò)的簡單應(yīng)用.

復(fù)雜網(wǎng)絡(luò);超網(wǎng)絡(luò);超圖

現(xiàn)在可以說我們是生活在一個網(wǎng)絡(luò)世界里,各種設(shè)施和事務(wù)都是通過網(wǎng)絡(luò)聯(lián)系起來的.例如交通運輸網(wǎng)絡(luò)是由道路把站點連接形成的網(wǎng)絡(luò).電力網(wǎng)絡(luò)是由發(fā)電廠、變電所和用戶通過輸電和配電線路連成的網(wǎng)絡(luò).計算機網(wǎng)絡(luò)可以看作是自主工作的計算機通過通信介質(zhì)如光纜、雙絞線、同軸電纜或者無線電波等相互連接形成的網(wǎng)絡(luò).神經(jīng)系統(tǒng)可以看作是大量神經(jīng)細胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò).上面提到的是有形的網(wǎng)絡(luò),還有許多由于社會關(guān)系(業(yè)務(wù)活動、血緣與人際交往等等)而形成的無形網(wǎng)絡(luò).人類社會中的網(wǎng)絡(luò)的產(chǎn)生和發(fā)展推動了社會的進步,例如交通運輸系統(tǒng)給人員與貨物的流動帶來方便,促進了商貿(mào)和工農(nóng)業(yè)的發(fā)展;信息系統(tǒng)給資金的流轉(zhuǎn)、商務(wù)的流通帶來很多的方便,提高了生產(chǎn)效率和生活質(zhì)量.但是另一方面像傳染病的流行和網(wǎng)絡(luò)病毒的傳播,電力網(wǎng)的局部故障引起大面積的停電,核輻射的傳播給人們的健康帶來了威脅,這又是由于網(wǎng)絡(luò)的存在而帶來的危害.因此對自然網(wǎng)絡(luò)和人工網(wǎng)絡(luò)的認識和干預(yù)(構(gòu)建、運行和防護)就成為科學(xué)技術(shù)所要解決的問題之一.

典型的網(wǎng)絡(luò)是由許多“節(jié)點”與連接兩個節(jié)點之間的一些“邊”組成的,其中節(jié)點用來表示實際系統(tǒng)中不同的個體,連接的邊則用來表示兩個節(jié)點之間具有某種特定的關(guān)系.用圖形表示就是常見的網(wǎng)絡(luò)圖.在節(jié)點之間通過邊有網(wǎng)絡(luò)流(物流、能流、信息流、資金流)在流動.隨著網(wǎng)絡(luò)規(guī)模的日益擴大和連接的日益復(fù)雜,人們對網(wǎng)絡(luò)除了從各自專業(yè)的角度加以研究外,還關(guān)注各類網(wǎng)絡(luò)在結(jié)構(gòu)和運行上的共性,希望能夠用抽象的數(shù)學(xué)工具來加以描述和分析.從18世紀數(shù)學(xué)家歐拉對所謂“Konigsberg七橋問題”的建模和分析,從而開創(chuàng)了數(shù)學(xué)中圖論這一分支以來,在運籌學(xué)中的網(wǎng)絡(luò)系統(tǒng)分析中對最短路徑、最大流以及最小費用流等方面,還有對時間流進行分析與設(shè)計的網(wǎng)絡(luò)計劃技術(shù)等,有了一些解決實際問題的研究.隨著交通事業(yè)的發(fā)展,出現(xiàn)了鐵路網(wǎng)、公路網(wǎng)、航空網(wǎng),信息化的發(fā)展產(chǎn)生了各類信息網(wǎng).網(wǎng)絡(luò)化的發(fā)展,出現(xiàn)了許多復(fù)雜的網(wǎng)絡(luò),這些網(wǎng)絡(luò)節(jié)點和邊的數(shù)量眾多,結(jié)構(gòu)復(fù)雜,例如互聯(lián)網(wǎng)(Internet)的用戶已經(jīng)是數(shù)以億計,由于缺少統(tǒng)一的管理,時至今日沒有任何一個人或組織能夠知道互聯(lián)網(wǎng)上所有的路由器到底是怎么聯(lián)結(jié)在一起的.再就是連接的多樣性,有的松散有的緊密,屬性也有差異.網(wǎng)絡(luò)節(jié)點和邊又都可能有復(fù)雜的動態(tài)行為.人們在運用網(wǎng)絡(luò)滿足自己的要求,常常是多目標或多準則的,而網(wǎng)絡(luò)的存在又提供了更多的選擇性,因而使得決策和優(yōu)化問題更加復(fù)雜.生活實踐和理論研究都需要對這樣的復(fù)雜網(wǎng)絡(luò)(complex network)進行深人的認識與分析.

到目前為止,科學(xué)家們還沒有給出復(fù)雜網(wǎng)絡(luò)精確嚴格的定義,但我們已經(jīng)可以從上面列舉的復(fù)雜網(wǎng)絡(luò)的特征來理解它的含義.

一個網(wǎng)絡(luò)的功能與它的結(jié)構(gòu)密切相關(guān),因此要從研究網(wǎng)絡(luò)的結(jié)構(gòu)人手.最初對復(fù)雜網(wǎng)絡(luò)的拓樸結(jié)構(gòu)是用具有一定規(guī)則的結(jié)構(gòu)表示的,形成所謂規(guī)則網(wǎng)絡(luò),但其適用范圍過窄.20世紀60年代出現(xiàn)的隨機圖理論,適應(yīng)了網(wǎng)絡(luò)的不確定性特點,開創(chuàng)了復(fù)雜網(wǎng)絡(luò)的系統(tǒng)性研究.在這種方法中,兩個節(jié)點之間是否有邊相連不再是確定的事情,而是根據(jù)一個概率決定.但大多數(shù)實際的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)并不是完全規(guī)則或完全隨機這兩個極端,而是要比規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)更為復(fù)雜.因此需要探索和發(fā)現(xiàn)網(wǎng)絡(luò)中的一些特殊的性質(zhì).當時有兩項研究成果使得研究工作得到了很大的推進,即發(fā)現(xiàn)某些網(wǎng)絡(luò)中的小世界效應(yīng)(small-world effect)和無標度特性(scale-free property)[1-2].科學(xué)家在研究節(jié)點的度(與該節(jié)點連接的邊的數(shù)目)的分布時,發(fā)現(xiàn)大量真實網(wǎng)絡(luò)的節(jié)點度服從冪率分布(連接邊多的節(jié)點少而連接邊少的節(jié)點卻非常多),而不是像隨機網(wǎng)絡(luò)那樣服從鐘型分布.我們把節(jié)點度服從冪律分布的網(wǎng)絡(luò)叫做無標度網(wǎng)絡(luò)(scale-free networks),Barabási和Albert把真實系統(tǒng)通過自組織生成無標度的網(wǎng)絡(luò)歸功于兩個主要因素：生長和優(yōu)先連接,而他們的網(wǎng)絡(luò)模型(BA網(wǎng)絡(luò))正是模擬這兩個關(guān)鍵機制設(shè)計的[2-3].

這些成果使得人們對于實際存在的網(wǎng)絡(luò)的生成機制、傳播機制、茁壯性和脆弱性等有了新的認識.隨后有關(guān)復(fù)雜網(wǎng)絡(luò)的研究有了長足的進展.

1 超網(wǎng)絡(luò)

但是在有些情況下,用一般的網(wǎng)絡(luò)圖并不能完全刻劃真實世界網(wǎng)絡(luò)的特征.在研究超大規(guī)模的網(wǎng)絡(luò)系統(tǒng)時,會出現(xiàn)網(wǎng)絡(luò)中的網(wǎng)絡(luò)的問題.如果用原來簡單或有向圖的方法來處理這類問題,就很難理清各個網(wǎng)絡(luò)之間的關(guān)系.因此就出現(xiàn)了超越一般網(wǎng)絡(luò)的網(wǎng)絡(luò)系統(tǒng)問題.人們常常把規(guī)模巨大、連接復(fù)雜、節(jié)點具有異質(zhì)性的網(wǎng)絡(luò)稱為超網(wǎng)絡(luò),例如認為互聯(lián)網(wǎng)是一種超網(wǎng)絡(luò),但這只是從常識上的一種稱呼,沒有明確定義.另有一種對超網(wǎng)絡(luò)的理解,是認為超網(wǎng)絡(luò)是網(wǎng)絡(luò)組成的網(wǎng)絡(luò).最早明確提出“超網(wǎng)絡(luò)”概念的是美國科學(xué)家Nagurney等[4-5],她在處理物流網(wǎng)絡(luò)與信息網(wǎng)絡(luò)、資金網(wǎng)絡(luò)相交織的問題時,把高于而又超于現(xiàn)存網(wǎng)絡(luò)(“above and beyond”existing networks)的網(wǎng)絡(luò),稱為超網(wǎng)絡(luò)(supernetwork).

Nagurney所研究的超網(wǎng)絡(luò)具備一種或幾種特征：a.多層特征,例如交通運輸網(wǎng)就有物理層、業(yè)務(wù)層和管理層;信息網(wǎng)絡(luò)協(xié)議也是多層的.層內(nèi)和層間都有連接.b.多級特征,例如企業(yè)的信息網(wǎng)絡(luò)有部門、公司、總部等級別.同級和級間都有連接.c.它的流量可以是多維的,例如鐵路、公路、水運和航空都是既有客運又有貨運.d.多屬性或多準則的,例如在城市中出行不僅有路徑選擇,而且有方式(駕車、公交、步行)的選擇,運輸網(wǎng)絡(luò)需要同時考慮時間、成本、安全舒適等.e.存在擁塞性,不僅交通運輸網(wǎng)絡(luò),而且信息網(wǎng)絡(luò)也存在擁堵問題.f.全局優(yōu)化和個體優(yōu)化需要協(xié)調(diào).

超網(wǎng)絡(luò)模型可用來描述和表示網(wǎng)絡(luò)之間的相互作用和影響.它可以將許多不同層次、不同標準的決策者之間的關(guān)系用關(guān)系函數(shù)來表示,在建立關(guān)系過程中,決策者必須付出一定的代價,如需付出物品、時間、金錢等.隨著關(guān)系層的增加,交易的成本和不確定性就會增加,因此必須給關(guān)系附加描述值.為了以較小的代價取得最大的利潤,決策者一定會考慮最大關(guān)系值,因此決策者既要找到與網(wǎng)絡(luò)中其它決策者交易的組合優(yōu)化,又要找到關(guān)系層的組合優(yōu)化.超網(wǎng)絡(luò)的構(gòu)架為研究網(wǎng)絡(luò)之間的相互作用和影響提供了工具.它可以用一些數(shù)學(xué)工具對網(wǎng)絡(luò)上的流量、時間等變量進行定量的分析和計算,這些數(shù)學(xué)工具包含：優(yōu)化理論、博弈論、變分不等式及可視化工具等.可以舉出下面一些超網(wǎng)絡(luò)的例子：

a.供應(yīng)鏈與社會網(wǎng)絡(luò)結(jié)合的超網(wǎng)絡(luò)模型[5]這是由社會網(wǎng)絡(luò)和供應(yīng)鏈網(wǎng)絡(luò)組成的超網(wǎng)絡(luò).這兩個網(wǎng)絡(luò)都由三層決策者構(gòu)成,社會網(wǎng)絡(luò)中的流是各層之間的關(guān)系,供應(yīng)鏈網(wǎng)絡(luò)中的流是產(chǎn)品之間的交易.

b.電子商務(wù)中的供應(yīng)鏈超網(wǎng)絡(luò)模型 這是一個包括m個商家和n個需求市場的供應(yīng)鏈超網(wǎng)絡(luò),其中.商家與需求市場的交易流程(訂貨、付款、傳遞)都在互聯(lián)網(wǎng)上進行,脫離了傳統(tǒng)的物流配送系統(tǒng).

c.回收超網(wǎng)絡(luò)模型 一個由m+n+o個單位組成的回收超網(wǎng)絡(luò),其中包括m個可造產(chǎn)品資源地,n個回收商和o個需求生產(chǎn)商,并任意取第i個資源地,第j個回收商和第k個需求生產(chǎn)商進行討論.有一些載能資源恢復(fù)理想中的使用價值會比由原材料生成所需要費用更高,不值得回收,因此對它們的處理就是使之銷毀并掩埋.

d.閉環(huán)供應(yīng)鏈超網(wǎng)絡(luò)模型 由原材料供應(yīng)商、生產(chǎn)商、零售商、需求市場和回收商組成的I+J+K+M+N個閉環(huán)供應(yīng)鏈超網(wǎng)絡(luò).其中,包括I個生產(chǎn)商總數(shù),J個零售商總數(shù),K個需求市場總數(shù),M個回收商總數(shù),N個原材料供應(yīng)商總數(shù),并任意取第i個生產(chǎn)商,j個零售商,k個需求市場,m個回收商,n個原材料供應(yīng)商.

前面的一些超網(wǎng)絡(luò)是從網(wǎng)絡(luò)結(jié)構(gòu)來考慮的,而現(xiàn)實生活中還有另外一些超網(wǎng)絡(luò)是從聯(lián)系方式來考慮的.例如：

a.社會網(wǎng)絡(luò)[6]在社會網(wǎng)絡(luò)中,點表示一個人或一群人,通常稱為行動者,他們之間如果交往或接觸就用一條邊將其連結(jié).這樣的連結(jié)方式可以是友誼、合作、貿(mào)易關(guān)系等.例如貿(mào)易交往中,必須考慮多于3者之間的關(guān)系,如賣者、買者、經(jīng)紀人.其它的例子中,不僅僅要考慮行動者參加行動的重要性,還要考慮其它的一些因素,如參加行動的時間、地點等.

b.蛋白質(zhì)網(wǎng)絡(luò)[6]在一個有機體蛋白質(zhì)水解過程中,對多蛋白質(zhì)復(fù)合物的系統(tǒng)描述需要蛋白質(zhì)成員之間有組織的數(shù)據(jù).這個組織最普通的形式是蛋白質(zhì)之間的相互反應(yīng)網(wǎng)絡(luò)和復(fù)合物交叉圖.在前一種表示中,網(wǎng)絡(luò)的點代表蛋白質(zhì)而邊連著相互反應(yīng)的蛋白質(zhì).然而,這個表示并沒有考慮到多蛋白質(zhì)復(fù)合物.在復(fù)合物交叉圖中,點表示復(fù)合物,而如果兩個復(fù)合物之間有一個或多個共同的蛋白質(zhì)的話,就用一條鏈將它們連結(jié).很明顯,這后一個表示并不能提供關(guān)于蛋白質(zhì)的信息,因此需要使用超網(wǎng)絡(luò)來提供蛋白質(zhì)和多個共同的蛋白質(zhì)成員之間的信息[7].

c.食物網(wǎng)[6]在生態(tài)學(xué)中,營養(yǎng)關(guān)系通常用表示為有向圖(子圖)的食物網(wǎng)來表示,其中,點表示物種而鏈表示物種之間的營養(yǎng)關(guān)系[8].表示食物網(wǎng)的另一種方法是用競爭圖C(G)來表示,其中點集與食物網(wǎng)相同,當且僅當聯(lián)系的物種在食物網(wǎng)中有共同的獵物時兩點之間是連通的[9].在競爭圖中,僅僅知道兩個聯(lián)系的物種之間有共同的獵物,但并不知道為共同獵物競爭的整個物種群的構(gòu)成情況.為了解決這個問題,需要建立競爭超網(wǎng)絡(luò)[10].

d.計算機網(wǎng)絡(luò)[6]在計算機領(lǐng)域中,若把多機系統(tǒng)中的處理機看作節(jié)點,處理機的集合作為超網(wǎng)絡(luò)節(jié)點集;把總線集作為超網(wǎng)絡(luò)的邊集,于是一個多機系統(tǒng)就抽象為一個超網(wǎng)絡(luò).

e.知識網(wǎng)絡(luò)[11]現(xiàn)在已經(jīng)存在的互聯(lián)網(wǎng)和各組織內(nèi)部的內(nèi)聯(lián)網(wǎng)也都可以看作是知識網(wǎng)絡(luò),因為以信息為知識載體,在網(wǎng)上儲存了與流通著大量的知識.這類知識網(wǎng)絡(luò)由三層組成：技術(shù)層、知識內(nèi)容層和人員層(社會網(wǎng)絡(luò)層).

2 基于超圖的超網(wǎng)絡(luò)

目前還有用超圖(Hypergraph)來定義的另一類超網(wǎng)絡(luò).這類超網(wǎng)絡(luò)的英文名字叫Hypernetwork,有別于Supernetwork.超圖的概念是Berge[12]于1970年提出的,文獻[12-13]第一次系統(tǒng)地建立了無向超圖理論.超圖不同于一般圖論中的無向或有向圖的地方在于：后者的每一個邊只連接兩個節(jié)點,而超圖中的邊可以連接兩個以上的節(jié)點,所以稱之為超邊.

數(shù)學(xué)上超圖的嚴格定義為：

設(shè)V={v1,v2,…,vn}是一個有限集.若

則稱二元關(guān)系H=(E,V)為一個超圖.V的元素v1,v2,…vn稱為超圖的頂點,E={e1,e2,…,em}是超圖的邊集合,集合ei={vi1,vi2,…,vij} (i=1,2,…,m)稱為超圖的邊.

超圖H的對偶H*稱為對偶超圖.如果對所有的那么,超圖H*=(E;V1,V2,…Vn)稱為H的對偶超圖.顯然,(H*)*=H.例如,研究圖1中的4個拱門

a1、a2、a3、a4.它們是由總共8類構(gòu)件b1、b2、b3、b4、b5、b6、b7、b8組成的,每個拱門所用的構(gòu)件不同.

圖1 4個拱門的圖形Fig.1 Diagram of 4 arches

如果用二分圖來表示構(gòu)建和拱門的關(guān)系,可以畫出圖2來(見圖2).這里有兩類性質(zhì)不同的節(jié)點,一類表示拱門,一類表示構(gòu)件,這時節(jié)點的同質(zhì)性失去了,在處理上就會帶來許多不方便.

圖2 用二分圖來表示4個拱門Fig.2 Representation of 4 arches by Bi-partition graph

如果用超圖表示其中的關(guān)系,以各構(gòu)件b為節(jié)點,以a1(b1,b2,b3)、a2(b2,b3,b4)、a3(b4,b5,b6)、a4(b6,b7,b8)為超邊,就得到了如圖3所示的超圖.這些超邊表示出各拱門都是用哪些構(gòu)件購成

的.假如以各拱門a為節(jié)點,以b1(a1)、b2(a1,a2)、b3(a1,a2,a3)、b4(a2,a3)、b5(a3)、b6(a3,a4)、b7(a4)、b8(a4)為超邊,就得到如圖4所示的超圖.其中的超邊表示各構(gòu)件都用在哪些拱門上.

圖3 超圖表示的4個拱門Fig.3 Representation of 4 arches by hypergraph

圖3、圖4兩個超圖是互為對偶的.超圖在描述多個節(jié)點有連接的網(wǎng)絡(luò)時,有它的方便之處.例如在電話的通話業(yè)務(wù)中,每一個用戶可以用一個節(jié)點來表示.如果兩個人通話,可以用一般圖論中的邊來描述.如果是3個人召開電話會議,用一般圖論中的邊來描述,就得像圖5(a)中那樣,需要3個邊.如果用超圖來描述,則如圖5(b)那樣,使用一個超邊就行了.

圖4 超圖3的對偶超圖Fig.4 Duality of Fig.3

圖5 電話通話的圖形表示Fig.5 Representation of phone communication

從現(xiàn)有研究成果來看,關(guān)于超圖理論及其應(yīng)用的研究是另外一條主線.這里可以提到的主要有以下幾個方面：

關(guān)于超圖理論本身的研究開始較早,文獻[14-17]分別研究了超圖理論的基本概念及基本性質(zhì).文獻[18]引人了超通路、超回路、超邊分解、分解超圖、k-超樹、單向超通路和單向超樹等概念,建立了有向超圖理論.文獻[19]研究了超圖的Helly性質(zhì)、Ramsey數(shù)、橫貫與匹配、分數(shù)橫貫、著色等.文獻[20]研究了超圖的t-設(shè)計.

基于超圖的超網(wǎng)絡(luò)的應(yīng)用方面,文獻[21]將超圖應(yīng)用在大規(guī)模集成電路布圖設(shè)計中.文獻[22]提出一種“基于超圖的容錯VLSI處理陣列”,基于文獻[23]的成果,文獻[24-25]應(yīng)用具有最佳連通性超圖的一些性質(zhì)解決了多總線系統(tǒng)的分析和綜合問題.文獻[26]提出了一種基于優(yōu)先記發(fā)式的超圖二劃分算法.文獻[27]給出了函數(shù)依賴集的超圖表示,提出了一種基于有向超圖的求最小覆蓋集的新算法.文獻[28]基于超圖模型生成了緊的無冗余XML文件.文獻[29]將超圖劃分方法應(yīng)用在VLSI領(lǐng)域.文獻[30-32]將超圖與圖象處理相結(jié)合,建立了圖象鄰域超圖模型.文獻[33]對細胞動態(tài)交流系統(tǒng)建立了超圖模型.文獻[34-35]對數(shù)據(jù)挖掘中的聚類提出了新的算法且建立了超圖模型.文獻[36]將超圖應(yīng)用在化學(xué)上,利用超圖的拓撲指數(shù)來識別化學(xué)中的化合物分子結(jié)構(gòu).文獻[37]用超網(wǎng)絡(luò)來辯別DNA切塊,文獻[38]用DNA超網(wǎng)絡(luò)對信息進行存貯和獲取.文獻[39]用進化超網(wǎng)絡(luò)對模式進行了分類,建立了進化變階的超網(wǎng)絡(luò)模型.超圖作為一類特殊的圖,不像一般圖論那樣和易于運用.它的應(yīng)用也還沒有像一般圖論那樣成熟,但是在運用于復(fù)雜的網(wǎng)絡(luò)系統(tǒng)的描述和分析上,具有很大的潛力.

筆者認為,基于超圖的超網(wǎng)絡(luò)可以認為是廣義的超網(wǎng)絡(luò)中的一個子類,就像以Nagurney為代表所研究具有前面所述的6種特性的網(wǎng)絡(luò),也是超網(wǎng)絡(luò)的一個子類.因為兩者像Nagurney所說的,都是高于而又超于現(xiàn)存網(wǎng)絡(luò)(“above and beyond”existing networks)的網(wǎng)絡(luò).

3 基于超圖的超網(wǎng)絡(luò)在知識表述上的應(yīng)用舉例

如何將網(wǎng)絡(luò)同知識的表示與組織結(jié)合起來,成為許多知識科學(xué)與知識管理研究者感興趣的話題之一.經(jīng)過近年來的探索,知識網(wǎng)絡(luò)的概念逐步形成.知識網(wǎng)絡(luò)作為一個概念,早在1995年Beckmann[40]就提出過,他認為知識網(wǎng)絡(luò)指的是從事科學(xué)知識的生產(chǎn)和傳播的機構(gòu)和活動.超網(wǎng)絡(luò)和超圖在知識的表述和處理(聚類、分類、集成等)中將會有很多的用途.可以用一個簡單的例子來加以說明[11].主題的辨識與提取是知識建模中的重要環(huán)節(jié).長期以來認為通過超鏈可以找到圍繞著主題的文檔類,但這還不足,應(yīng)該進一步研究辨識主題或者說生成主題的方法.一類含有同樣主題的文檔是可以聚類的,但主題是隱含在其中的.有時候一個主題是可以用一個表述能力很強的詞語來描述的,也有時候需要一組相關(guān)的詞語來描述.有的詞語有利于檢索,但并不一定是好的描述符.這又和具體任務(wù)有關(guān),有的是為了尋找一個很狹小的范圍內(nèi)的具體內(nèi)容,有的是要在一個很寬泛的范圍內(nèi)收集涉及面很廣的知識.兩者對描述符的要求就不一樣.從直覺上來判斷,如果一個或幾個詞語能夠明確回答“這個主題是關(guān)于什么的”問題,就是好的主題描述符.如果一個或幾個詞語能夠回答“什么是能夠得到類似的信息的好的詢問詞語”,就是好的鑒別符.

為了確定主題的描述符和鑒別符,需要分析詞語、文檔和主體之間的關(guān)系.文獻[41]建議使用超圖來表示這樣的關(guān)系.我們可以把一組文檔看做一個超圖H=(T,D),其中每一個節(jié)點t∈T對應(yīng)于一個詞語,每一個超邊d∈D對應(yīng)于一個文檔.一個超邊d是一個T中元素的多元集,把一個文檔抽象地表示為像一個裝了詞語的口袋.可以把這種超圖稱為以文檔為中心的超圖.

對應(yīng)于每一個以文檔為中心的超圖H=(T,D),有一個以詞語為中心的超圖H*=(D,T),它的節(jié)點對應(yīng)于文檔而超邊對應(yīng)于詞語,超邊是文檔的多元集.超圖H*是超圖H的對偶超圖.圖6中的超圖,表示的是由3個文檔A、B、C和其中包含的詞語1,2,3,4之間的關(guān)系.

圖6 用超圖表示文檔(取自于文獻[41])Fig.6 Representation of documents(from[41])

圖6(a)是以文檔為中心的超圖

圖6(b)是它的對偶超圖

在圖6中,圓圈表示超邊而小三角表示節(jié)點.圖6(a)與圖6(b)中節(jié)點和超邊的連接上的數(shù)字表示的是該節(jié)點在超邊中出現(xiàn)的次數(shù).例如節(jié)點1和超邊A的連接上標注的2,表示詞語1在文檔A中出現(xiàn)2次.

這里這樣定義關(guān)聯(lián)矩陣：對一個由m個文檔和n個詞語的以文檔為中心的超圖來說,其關(guān)聯(lián)矩陣的m行對應(yīng)于文檔,n列對應(yīng)于詞語.矩陣的元素

其中,k是第j列的詞語在第i行的文檔中出現(xiàn)的次數(shù).我們還可以知道,對偶超圖的關(guān)聯(lián)矩陣是原超圖關(guān)聯(lián)矩陣的轉(zhuǎn)置.可以使用關(guān)聯(lián)矩陣的某些性質(zhì)來反映詞語在文檔中的描述能力和鑒別能力.詞語j在文檔i中的描述能力可以用下列函數(shù)來衡量

利用這一函數(shù)(它的數(shù)值在0與1之間)可以構(gòu)成加權(quán)的以文檔為中心的超圖,如圖6(c)所示,它可以稱為d-超圖.從圖中可以看出,不同的詞語的描述能力是不同的,例如詞語2對文檔B的描述能力最強,詞語1對文檔A的描述能力比詞語2強.

為了度量詞語對文檔的鑒別能力,可以使用下列函數(shù)

其中的s(k)是當k＞0時其值為1,當k=0時其值為0.這個函數(shù)的值也是在0與1之間.如果第i個詞語不出現(xiàn)在文檔j之中,則函數(shù)值為0;如果第i個詞語除了出現(xiàn)在文檔j之外不再出現(xiàn)在其它文檔之中,則該函數(shù)值為1,因而可以說這個詞語完全鑒別出該文檔.這個函數(shù)與詞語在文檔中出現(xiàn)的次數(shù)無關(guān).利用這一函數(shù)可以構(gòu)成加權(quán)的以詞語為中心的超圖,如圖6(d)所示,它可以稱為t-超圖.其中,詞語1完全鑒別出文檔A.

對d-超圖與t-超圖來說存在關(guān)系

上面這種選擇最好的描述符合鑒別符的方法僅僅是對文檔而言的,還需要為主題選取好的描述符和鑒別符.主題總是要涉及多個類似的文檔或詞語,因此需要研究文檔的相似性和詞語的同時出現(xiàn)性.

兩個文檔di與dj的相似性可以按照眾所熟知的余弦測度來衡量

圖7(a)使用d-超圖來闡明文檔的相似性.從圖中可以看出,文檔D和E是相似的.圖7(b)使用t-超圖來闡明同時出現(xiàn)性.可以看出,詞語3和4是同時出現(xiàn)的.怎樣識別一個文檔的主題的最好的鑒別符呢?如果一個詞語他所鑒別出來的文檔是和某一已知文檔相似的,那么這個詞語就是這個文檔的好的鑒別符.如果用公式,則可用函數(shù)

表述.可以把詞語ti對文檔dj的鑒別能力,看作是文檔dj與由ti鑒別出來的其它文檔的相似性的平均值.

圖7 用超圖來說明文檔的性質(zhì)圖(取自于文獻[41])Fig.7 Explanation of features of documents(from[41])

下面再來看主題的描述符.前面曾經(jīng)非正式地說到過,主題的描述符就是在主題的環(huán)境中經(jīng)常出現(xiàn)的詞語.一個詞語在主題中的描述能力可以用前面用到的對文檔相似性和文檔中詞語的描述能力來計算.這樣就能夠用函數(shù)來度量

一個詞語tj在文檔di的主題中的描述能力,是詞語tj作為與文檔di相似的所有文檔的描述符的質(zhì)量指標.如果沒有其它文檔和di相似,或者tj沒有出現(xiàn)在與di相似的其它文檔之中,則tj在di的主題中的描述能力為0.在圖7中,詞語2,3,4在文檔D、E、F的主題中都是好的描述符.但是3,4是這一主題好的鑒別符,而2卻不是.因為2雖然在該主題中,但卻不僅在這一主題中.在這3個文檔中,只有D和E是聚焦在這一主題上的.文檔F包含了這一主題同時出現(xiàn)的詞語,但不是這一主題的獨有詞語.

以上僅僅是一個簡單的例子用來說明這類超網(wǎng)絡(luò)的應(yīng)用,這方面還有很大的發(fā)展空間.

4 超網(wǎng)絡(luò)進一步發(fā)展的一點思考

超網(wǎng)絡(luò)的提出只是近幾年的事,目前它也只是一個概念,其邊界并不十分清晰.對于一些實際問題,僅僅在利用變分不等式和超圖的基礎(chǔ)上建立了一些模型,提出了一些解法.對超網(wǎng)絡(luò)本身還沒有眾所公認的定義.對于什么樣的網(wǎng)絡(luò)可以算作超網(wǎng)絡(luò)也還有一個逐步明確的過程.但是從上面已經(jīng)列舉的一些事例來看,由于社會經(jīng)濟和科學(xué)技術(shù)的網(wǎng)絡(luò)化的進一步發(fā)展,這類網(wǎng)絡(luò)問題逐漸呈現(xiàn),像對有關(guān)復(fù)雜網(wǎng)絡(luò)的研究一樣,人們開始找到了它的一些特征,以及合適的描述方法.

對照復(fù)雜網(wǎng)絡(luò)的含義,可以說超網(wǎng)絡(luò)也是一類特殊的復(fù)雜網(wǎng)絡(luò).上世紀末和本世紀初國內(nèi)外都掀起了對復(fù)雜網(wǎng)絡(luò)研究的高潮.特別是人們擺脫了還原論的局限性,進而開始研究網(wǎng)絡(luò)各組成部分的相互影響,這正是超網(wǎng)絡(luò)的研究內(nèi)容.在文獻[42]中一批權(quán)威作者經(jīng)過討論提出了當前網(wǎng)絡(luò)研究的10個主要問題,其中談到了有關(guān)“網(wǎng)絡(luò)的網(wǎng)絡(luò)”問題,即研究不同性質(zhì)網(wǎng)絡(luò)間的相互作用問題.可見超網(wǎng)絡(luò)問題將逐步進人網(wǎng)絡(luò)研究的主流.特別是在系統(tǒng)工程界近年來開始研究所謂“系統(tǒng)的系統(tǒng),SoS”,如果系統(tǒng)可以用網(wǎng)絡(luò)來描述,那么“系統(tǒng)的系統(tǒng)”就可以用“網(wǎng)絡(luò)的網(wǎng)絡(luò)”也就是超網(wǎng)絡(luò)來描述.對超網(wǎng)絡(luò)的研究,和對一般的復(fù)雜網(wǎng)絡(luò)的研究一樣,將會有助于理解“復(fù)雜系統(tǒng)之所以復(fù)雜”這一極其重要的問題,這也就是說,超網(wǎng)絡(luò)問題的研究不僅有其實際意義,而且也對系統(tǒng)復(fù)雜性的探索開辟了一個新的途徑.超網(wǎng)絡(luò)概念的提出,使得人們對一些多層、多級、多維網(wǎng)絡(luò)流、多屬性和多準則的網(wǎng)絡(luò)問題有了新的認識和理解,但是我們還只是在復(fù)雜性的密林中剛剛找到一些小道,還需要開辟新的道路.盡管在文獻[6]中用到了復(fù)雜超網(wǎng)絡(luò)這一提法,但依我們的看法,除了一些極其簡單的超網(wǎng)絡(luò)問題可以憑經(jīng)驗解決外,大多數(shù)超網(wǎng)絡(luò)都是復(fù)雜的超網(wǎng)絡(luò),都可以看作是一類特殊的復(fù)雜網(wǎng)絡(luò),這種復(fù)雜性主要表現(xiàn)在屬性上,而不是在規(guī)模上.所以不必另加復(fù)雜這一定語.正是由于其屬性的特點才使超網(wǎng)絡(luò)問題需要另辟蹊徑專門加以研究.

依筆者的淺見,對超網(wǎng)絡(luò)問題的研究首先要考慮的問題,是探索發(fā)現(xiàn)實際生活中的一些網(wǎng)絡(luò)由于哪些特征才需要,而且可以把它們看作是超網(wǎng)絡(luò)問題,以及怎樣建立從概念模型、結(jié)構(gòu)模型乃至于數(shù)學(xué)模型.現(xiàn)有的超網(wǎng)絡(luò)分析優(yōu)化方法還是極其有限的,需要探尋新的方法.超網(wǎng)絡(luò)雖然一時無法得到眾所公認的定義,但是否可以從深人研究其典型特征人手來加以界定.網(wǎng)絡(luò)的拓撲結(jié)構(gòu)在網(wǎng)絡(luò)的穩(wěn)定性等方面有著非常重要的作用.

在應(yīng)用方面,值得考慮的問題是：

a.復(fù)雜網(wǎng)絡(luò)和超網(wǎng)絡(luò)概念的提出,一方面在為客觀事物的描述和建模過程中,填補了離散對象的集總參數(shù)模型(利用代數(shù)和常微分方程、差分方程)和連續(xù)介質(zhì)對象的分布參數(shù)模型(利用數(shù)學(xué)物理方程)之間的空白(過去像對復(fù)雜運輸網(wǎng)絡(luò)這類系統(tǒng)的建模是面臨很大困難的).另一方面,提供了考慮和分析網(wǎng)絡(luò)各組成部分之間(特別是層間和級間)以及網(wǎng)絡(luò)和網(wǎng)絡(luò)之間關(guān)系的方法.這就為許多復(fù)雜系統(tǒng)研究提供了新思路,隨著實際生活中系統(tǒng)的日益復(fù)雜和多樣化,將有更多的系統(tǒng)可按照超網(wǎng)絡(luò)來處理.

b.在Nagurney所說的“高于而又超于現(xiàn)存網(wǎng)絡(luò)”中所指的現(xiàn)存網(wǎng)絡(luò),是節(jié)點對應(yīng)于空間位置、邊對應(yīng)于物理連接(如道路、線纜)的網(wǎng)絡(luò),而超乎這樣網(wǎng)絡(luò)的則是一些帶有虛擬特點的節(jié)點、邊和流,如知識節(jié)點、社會關(guān)系、價格流等.因此超網(wǎng)絡(luò)的概念和處理方法必將在虛實結(jié)合的網(wǎng)絡(luò)研究中顯示其獨特優(yōu)勢,得到廣泛應(yīng)用,特別是基于超圖的超網(wǎng)絡(luò).

c.在解決問題的已有研究基礎(chǔ)上,應(yīng)該在更廣泛的運輸網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、能源網(wǎng)絡(luò)、金融網(wǎng)絡(luò)中,考慮更多的風(fēng)險和其它因素,將超網(wǎng)絡(luò)模型進一步完善,使之更符合現(xiàn)實.

d.將超網(wǎng)絡(luò)進一步應(yīng)用于物聯(lián)網(wǎng)系統(tǒng)、知識管理系統(tǒng)[11]等一些新型系統(tǒng)之中.

[1] WATTSD J,STROGATESSH.Collective dynamics of“small-world”networks[J].Nature,1998,393： 440-442.

[2] ALBERT R,BARABASI A L,Statistical mechanics of complex networks[J].Review of Modern Physics, 2002,74：47-97.

[3] BARABASI A L,Linked：How Everything Is Connected to Everything Else and What It Means for Science, Business and Everyday Life[M].Cambridge：Perseus Publishing,Inc,2002.

[4] NAGURNEY A,DONG J.Supernetworks：Decision-Making for the Information Age[M].Cheotenham： Edward Elgar Publishers,2002.

[5] NAGURNEY A,WAKOLBINGER T.Supernetworks： An introduction to the concept and its applications with a specific focus on knowledge supernetworks[J]. International Journal of Knowledge Culture and Change Management,2005,4：1-16.

[6] EMESTO ESTRAD A,JUAN A.Rodriguez-velazquez. subgraph centrality and clustering in complex hypernetworks[J].Physica A,2006,364：581-594.

[7] RAMADAN E,TARAFDAR A,POTHEN A.A hypergraph model for the yeast protein complex network[C]∥IPDPS Workshop on High-Performance Computational Biology.Proceedings of the HICOMB 2004.New Mexico：Santa Fe NM,2004.

[8] PIMM S L.Food Webs[M].London：Chapman& Hall,1982.

[9] COHEN J E.Interval graphs and food webs,a finding and a problem.Document 17696-PR[Z].Santa Monica：RAND CORP,1968.

[10] SONNTAG M,TEICHERT H M.Competition hypergraphs[J].Discrete Appl Math,2004,143：324-329.

[11] 王志平,王眾托.超網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：科學(xué)出版社,2008.

[12] BERGE C.Graphs and Hypergraphs[M].New York： Elsevier,1973.

[13] BERGE C.Hypergraphs：The Theory of Finite Sets [M].Amsterdam：Elsevier Science,1989.

[14] 羅靜,毛其智,黨安榮.基于超圖的生態(tài)環(huán)境修復(fù)模型的研究與應(yīng)用[J].計算機工程與應(yīng)用,2007,43(31)： 188-191.

[15] KARONSKI M.A review of random graphs[J].Journal of Graph Theory,1982,6(4)：349-389.

[16] ARIEZRI S,FRACNKDL E.A deletions game on hypergraph[J].Discrete Applied Mathematics,1991,30： 155-162.

[17] ENDRE BOROS(USA),On shift stable hypergraphs [J].Discrete mathematics,1991,87：81-84.

[18] 黃汝激.超網(wǎng)絡(luò)的有向k超樹分析法[J].電子科學(xué)學(xué)刊,1987,19(3)：244-255.

[19] 貝爾熱C.超圖-有限集的組合學(xué)[M].卜月華,張克民譯.南京：東南大學(xué)出版社,2002.

[20] TUAN N D.Hypergraphical t-designs[J].Discrete Mathematics,2006,306：1189-1197.

[21] 黃汝激.應(yīng)用超圖理論實現(xiàn)有向基本割集矩陣[J].電子科學(xué)學(xué)刊,1992,14(1)：50-60.

[22] HU T C,MOERDER K.超圖中的多端流[C]∥圖論應(yīng)用新進展,北京：中國電子學(xué)會,1989：235-245.

[23] ROSERNBERG A.A hypergraph model for fault-tolerant VLSI processor arrays[J].IEEE Transaction, Computer,1985,C-34(6)：578-584.

[24] 陳廷槐.超圖的連通性和容錯多總線系統(tǒng)的設(shè)計[J].中國科學(xué)A,1990(11)：1309-1319.

[25] 高則年.具有最佳連通性的超圖和容錯總線系統(tǒng)的設(shè)計[J].計算機學(xué)報,1990(11)：878-881.

[26] KAMIDOI Y,WAKABAYASHI S,YOSHIDA N.A fast heuristic algorithm for hypergraph bisection[J].IEEE ISCAS,1991(2)：1160-1163.

[27] 郝忠孝.一種基于超圖的最小覆蓋集求法[M].計算機研究與發(fā)展,1990(10)：58-64.

[28] WAI YIN MOK,EMBLEY D W.Generating compact redundancy-free XML documents from conceptualmodel hypergraphs[J].IEEE Transactions on Knowledge&Data Engineering,2006(18)：1082-1096.

[29] KARYPISG.Multilevel hypergraph partitioning：Applications in VLSI domain[J].IEEE Transactions on Very Large Scale Integration Systems,1999(7)： 69-70.

[30] BRETTOA,GILLIBERT L.Hypergraph-based imagerepresentation[J].Lecture Notes in Computer Science,2005,3435(135)：1-11.

[31] ALAIN B,HOCINE C,DRISS A.Hypergraph Imaging an overview[J].Pattern Recongition,2002(35)：651-658.

[32] CHASTEL S,COLANTONI P.Displaying image neighborhood hypergraphs line-graphs[J].Lecture Notes in Computer Science,2002(2301)：124-135.

[33] SARKAL S,KUMARN.Hypergraph models for cellular mobile communications systems[J].IEEE Transactions on Vehicular Technology,1998(47)：460-471.

[34] HAN E-H(Sam),GEORGE K.Research Issue on Data Mining and Knowledge Discovery[M].Navi Mumbai：Bioinfo Publications,1997.

[35] OZDAL M,AYKANAT C.Hypergraph models and algorithms for date-pattern-based clustering[J].Data mining and Knowledge Discovery,2004(9)：29-57.

[36] ELENA V K,VLADIMIR A S.Application of hypergraph theory in chemistry[J].Discrete Mathematics, 2001,235：365-383.

[37] SEGOVIA-JUAREZ J L,COLOMBANO S,KIRSCHNER D.Identifying DNA splice sites using hypernetworks with artificial molecular evolution[J].Bio-Systems,2007,87：117-124.

[38] MAO C,YOKOMORI T.DNA hypernetworks for information storage and retrieval[J].DNA12,LNCS,2006, 4287：298-307.

[39] KIM J K,ZHANG B T.Evolving hypernetworks for pattern classificatIon[C]//IEEE Congress on Evolutionary Computation(CEC),Singapore：2007：1856 -1862.

[40] BECKMAN M J.Economic models of knowledge networks[C]∥BATTEN D,CASTI J.Networks Action. Berlin：Springer-Verlag,1995：159-174.

[41] MAGUITMAN A G.Intelligent support for knowledge capture and constructioon[D].Indianapolis：Indiana U-niversity,USA,2004.

[42] BARABASI A L.Virtual round table on ten leading questions for network research[J].European Physical Journal B,2004,38(2)： 143-145.

作者介紹

王眾托中國工程院院士,系統(tǒng)工程與管理工程專家.1951年畢業(yè)于清華大學(xué)電機系.曾任大連理工大學(xué)管理學(xué)院院長、中國系統(tǒng)工程學(xué)會副理事長.現(xiàn)任大連理工大學(xué)教授、知識科學(xué)與技術(shù)研究中心主任.20世紀50年代至60年代,從事自動化專業(yè)建設(shè)、自動控制理論與計算機應(yīng)用方面的學(xué)科引進和研究,長期從事教材的編寫與組織,做過許多艱苦的開拓工作.曾研究開發(fā)過我國自主研制的石油管卷管機的自動控制系統(tǒng),以及我國第一臺電渣重熔的交流控制系統(tǒng).70年代后期開始從事系統(tǒng)工程專業(yè)與學(xué)位建設(shè),是我國系統(tǒng)工程研究生教育與學(xué)科創(chuàng)建人之一.在學(xué)科創(chuàng)建初期就開展網(wǎng)絡(luò)計劃技術(shù)的新方法(決策關(guān)鍵路線法)與應(yīng)用、基于虛擬裝置的煉油企業(yè)生產(chǎn)計劃與調(diào)度系統(tǒng)分析、元決策理論與應(yīng)用、智能型交互式集成化決策支持系統(tǒng)等研究,取得顯著經(jīng)濟效益.曾在維也納國際應(yīng)用系統(tǒng)分析研究所(IIASA)任研究員,主持國際合作項目,最早開發(fā)了用于宏觀經(jīng)濟發(fā)展研究的智能型交互式集成化決策支持系統(tǒng),開我國決策支持系統(tǒng)研究之先河.曾獲國家級獎勵兩項,部委級獎勵6項.撰寫出版14種教材與專著,翻譯9種經(jīng)典著作和教材.在國內(nèi)外發(fā)表140余篇學(xué)術(shù)論文與科學(xué)報告.現(xiàn)從事所倡導(dǎo)的知識系統(tǒng)工程研究與應(yīng)用.

Reflection on supernetwor k

WANGZhong-tuo
(Institute of Systems Engineering,Dalian University of Technology,Dalian 116085,China)

In this paper,the concept of hypernetwork based on hypergraph suggested by C.Berge as another kind of supernetwork is introduced.The main feature of hypernetwork is the edge in hypergraph can be connected to more than one nodes.For the investigation of some complex network like telecommunication network,knowledge network,social network,this unique feature may offer more advantages.

complex work;hypernetwork;hypergraph

N 94

A

1007-6735(2011)03-0229-09

2011-06-07

王眾托(1928-),男,中國工程院院士.研究方向：系統(tǒng)工程、知識科學(xué)與技術(shù)、決策分析. E-mail：wangzt@dlut.edu.cn