吳學文，瞿永鋼，李 玲

(河海大學計算機與信息學院，江蘇南京 210098)

目前，復(fù)雜網(wǎng)絡(luò)理論應(yīng)用于各種學科領(lǐng)域。倪向萍等［1］應(yīng)用復(fù)雜網(wǎng)絡(luò)理論研究了電力網(wǎng)絡(luò)的脆弱度;趙月等［2］將復(fù)雜網(wǎng)絡(luò)應(yīng)用于城市交通網(wǎng)絡(luò)研究;Sporns［3］用復(fù)雜網(wǎng)絡(luò)理論研究人腦連接組并研究網(wǎng)絡(luò)動態(tài)特性;田占偉等［4］發(fā)現(xiàn)微博信息傳播網(wǎng)絡(luò)具有集群性、小世界、高度中心化等特征。

河流網(wǎng)絡(luò)是一個遠離平衡態(tài)的、自組織的、開放的網(wǎng)絡(luò)［5-6］，是一個典型的復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)理論為研究河流網(wǎng)絡(luò)提供了新思路和新方法。20世紀90年代，學者開始應(yīng)用復(fù)雜網(wǎng)絡(luò)理論來研究河流網(wǎng)的形成及演化機理［7］。1992—1993 年間，Rodriguez-Ⅰturbe等［8］、Rinaldo等［9］應(yīng)用“哈密頓量最小化選擇生成樹”所得到的“最佳通道網(wǎng)”可以重現(xiàn)實際的河流網(wǎng)絡(luò)形態(tài)。2004—2005年間，沈丹等［10］、許田［11］、汪小帆等［12］研究了長江流域地理網(wǎng)絡(luò)的自組織臨界現(xiàn)象，證明各級支流的總流域面積和各級支流的總長度對河流級別的依賴關(guān)系都符合無標度規(guī)律。2005年，He等［13］證明了北京-廊坊-天津地區(qū)的天然河流網(wǎng)絡(luò)服從指數(shù)為2.48的無標度分布。

筆者應(yīng)用復(fù)雜網(wǎng)絡(luò)理論來建立河流網(wǎng)絡(luò)模型，并進一步研究節(jié)點及邊的重要性。該研究可以為水利規(guī)劃、洪水調(diào)度提供理論依據(jù)。

1 基于復(fù)雜網(wǎng)絡(luò)理論的河流網(wǎng)絡(luò)建模

1.1 河流網(wǎng)絡(luò)模型構(gòu)建

河流網(wǎng)絡(luò)可以抽象概化為一個有向加權(quán)網(wǎng)絡(luò)模型(G)，其基本要素主要包括節(jié)點集合(V)、邊集合(E)、權(quán)重向量集合(W)，即

其中

網(wǎng)絡(luò)節(jié)點定義為河流的流量、水位等水力特征明顯改變的地方，包括河流源口、河流交匯點、河流出口、水電站、水庫、水閘等;邊是指河水在節(jié)點間流經(jīng)的途徑，即河道，包括自然河道和人工河道，邊＜vi，vj＞表示一條從節(jié)點vi到節(jié)點vj的河道;權(quán)值是指各節(jié)點和各邊的重要性。

1.2 應(yīng)用實例

海河水系是中國華北地區(qū)最大的水系。根據(jù)《中華人民共和國水力資源復(fù)查成果》及其他相關(guān)資料［14］，將海河水系抽象概化為網(wǎng)絡(luò)圖，建立海河網(wǎng)絡(luò)模型Ⅰ(圖1)，其包括344個節(jié)點和385條邊，只含自然節(jié)點和自然河道。為了研究工程節(jié)點、人工河道對河流網(wǎng)絡(luò)的影響，建立了含有工程節(jié)點和人工運河的海河網(wǎng)絡(luò)模型Ⅱ(圖2)，其含有565個節(jié)點和612條邊。

圖1 海河網(wǎng)絡(luò)模型ⅠFig.1 Haihe River NetworKModelⅠ

圖2 海河網(wǎng)絡(luò)模型ⅡFig.2 Haihe River NetworKModelⅡ

2 復(fù)雜河流網(wǎng)絡(luò)的節(jié)點重要性

分析河網(wǎng)中節(jié)點及邊的重要性并進行重點保護，有利于認識、預(yù)測和控制整個網(wǎng)絡(luò)。目前，衡量節(jié)點重要性的指標主要有度指標和介數(shù)指標等。這里主要介紹更能反映網(wǎng)絡(luò)狀態(tài)的介數(shù)指標。

介數(shù)指標用來刻畫網(wǎng)絡(luò)中節(jié)點對于信息流動的影響力。節(jié)點x的介數(shù)指標定義為

式中:gjk(x)——gjk中經(jīng)過節(jié)點x的最短路徑數(shù);

gjk——節(jié)點j與節(jié)點k之間的最短路徑數(shù);(n-1)(n-2)/2——最大可能的節(jié)點介數(shù)(任意其他2個節(jié)點的最短路徑都經(jīng)過節(jié)點x)。

2.1 河流網(wǎng)絡(luò)節(jié)點重要性權(quán)值指標

由于河流網(wǎng)絡(luò)節(jié)點具有其特有的性質(zhì)，因此，本節(jié)提出了河流網(wǎng)絡(luò)節(jié)點重要性權(quán)值指標。

河流網(wǎng)絡(luò)中有自然節(jié)點和工程節(jié)點。不同類型的節(jié)點賦予不同的權(quán)值。所有的自然節(jié)點具有相同的類型權(quán)值t1，所有的工程節(jié)點具有相同的類型權(quán)值t2。歸一化的節(jié)點類型權(quán)值定義為

式中:T——自然節(jié)點和工程節(jié)點的權(quán)值之和，T=t1+t2。

節(jié)點的徑流量反映節(jié)點在河流網(wǎng)絡(luò)中的重要性。節(jié)點x的流量權(quán)值為

式中:Q(x)——節(jié)點x的多年平均徑流量;Qmax——河流網(wǎng)絡(luò)中所有節(jié)點的多年平均徑流量最大值。

河流網(wǎng)絡(luò)中，2個節(jié)點之間的連線對應(yīng)于實體中的河道，連線長度對應(yīng)于河道長度。連線長度體現(xiàn)了節(jié)點之間的緊密程度，連線越長，河道就越長，節(jié)點之間就越疏遠。因此，將該節(jié)點到其余節(jié)點的最短河道長度的倒數(shù)之和定義為節(jié)點的距離權(quán)值。當節(jié)點之間有多條路徑時，選擇河道長度最短的路徑來計算距離權(quán)值。節(jié)點的距離權(quán)值可表示為

式中:Dxy——節(jié)點x到節(jié)點y的最短河道長度;dxy——節(jié)點x到節(jié)點y的一條路徑長度。對于無向網(wǎng)絡(luò)，有dxy=dyx，Dxy=Dyx。

河流加權(quán)網(wǎng)絡(luò)的節(jié)點重要性指標定義為類型權(quán)值、流量權(quán)值和距離權(quán)值的乘積，即

2.2 海河網(wǎng)絡(luò)中節(jié)點重要性分析

2.2.1 海河網(wǎng)絡(luò)構(gòu)建

忽略較小的節(jié)點和邊后，建立了含有78個節(jié)點和78條邊的簡化海河網(wǎng)絡(luò)模型，如圖3所示。

圖3 簡化海河網(wǎng)絡(luò)模型Fig.3 Simplified Haihe River NetworKModel

2.2.2 海河網(wǎng)絡(luò)節(jié)點重要性分析

2.2.2.1 介數(shù)指標

計算海河網(wǎng)絡(luò)節(jié)點重要性的介數(shù)指標，將其按區(qū)間段分為7個等級，如表1所示。

表1 海河網(wǎng)絡(luò)節(jié)點重要性的介數(shù)指標分布情況Table 1 Distribution of betweenness index of vertex importance in Haihe River Network

2.2.2.2 權(quán)值指標

計算海河網(wǎng)絡(luò)節(jié)點重要性的權(quán)值指標，將其按區(qū)間段分為8個等級，如表2所示。

表2 海河網(wǎng)絡(luò)的節(jié)點權(quán)值指標分布情況Table 2 Distribution of vertex weight index in Haihe River Network

2.2.2.3 2種指標對比分析

在海河網(wǎng)絡(luò)中，介數(shù)指標對節(jié)點的重要性劃分較詳細。介數(shù)指標能找到獨流減河進洪閘、向陽口一級水電站、官廳水庫等最重要的節(jié)點(等級1～2)，這些節(jié)點的度不一定大，但對于整個網(wǎng)絡(luò)卻具有十分重要的作用，體現(xiàn)了介數(shù)指標的準確性。但介數(shù)指標認為河流源口和河流出口都具有相同的重要性，即都最不重要，因此仍有些片面。

節(jié)點權(quán)值指標同介數(shù)指標一樣，能準確找到最重要的節(jié)點——獨流減河進洪閘。串聯(lián)于同一河道上的多個節(jié)點具有相近的權(quán)值指標，即具有相近的重要程度，這類似于介數(shù)指標。在權(quán)值指標中，源口間的權(quán)值指標不再都是零值，甚至大于交匯點的權(quán)值指標。因此，在對源口的分析上，權(quán)值指標優(yōu)于介數(shù)指標，所以權(quán)值指標能更準確地找到河流網(wǎng)絡(luò)的重要節(jié)點，但計算復(fù)雜度較高。

3 復(fù)雜河流網(wǎng)絡(luò)的邊重要性分析

分析邊的重要性，找出那些相對重要的邊(即河道)，有利于認識、保護和控制重要的河道。

3.1 河流網(wǎng)絡(luò)邊重要性的權(quán)值指標

3.1.1 邊介數(shù)指標

目前，研究邊的重要性有多種方法，例如邊介數(shù)指標［15］。邊介數(shù)指標通過計算邊介數(shù)來描述邊對網(wǎng)絡(luò)的信息傳遞能力［15］。邊介數(shù)指標可以定義為

式中:g'jk(x)——g'jk中經(jīng)過邊x的最短路徑數(shù);g'jk——節(jié)點j與節(jié)點k之間的最短路徑數(shù);(n-1)(n-2)/2——最大可能的邊介數(shù)(任意其他2個節(jié)點的最短路徑都經(jīng)過邊x)。

3.1.2 邊權(quán)值指標

在河流網(wǎng)絡(luò)中，連邊代表著現(xiàn)實中的河道，而河道具有實際長度，長度權(quán)值越大則該邊越具有較高的重要性。長度權(quán)值可以表示為

式中:L(x)——邊x的實際河道長度;Lmax——河流網(wǎng)絡(luò)中的最長河道長度。

多年平均流量可用來衡量一條河流的水量傳輸能力。邊的流量權(quán)值定義為

式中:Q'(x)——邊x對應(yīng)河道的多年平均流量;Q'max——網(wǎng)絡(luò)中河道多年平均流量的最大值。邊權(quán)值指標定義為邊介數(shù)、邊長度權(quán)值與邊流量權(quán)值的乘積，可以表示為

3.2 海河網(wǎng)絡(luò)邊重要性分析

3.2.1 邊介數(shù)指標

計算海河網(wǎng)絡(luò)邊重要性的介數(shù)指標，共有45個值，將其按區(qū)間段分為7個等級，如表3所示。

表3 海河網(wǎng)絡(luò)邊重要性的介數(shù)指標分布情況Table 3 Distribution of betweenness index of edge importance in Haihe River Network

3.2.2 邊權(quán)值指標

經(jīng)計算得到海河網(wǎng)絡(luò)邊重要性的權(quán)值指標，得到78個不同的值，即每條邊的權(quán)值指標都不相等，將其按區(qū)間段分為8個等級，如表4所示。

表4 海河網(wǎng)絡(luò)邊重要性的權(quán)值指標分布情況Table 4 Distribution of weight index of edge importance in Haihe River Network

3.2.3 2種指標對比分析

邊的介數(shù)指標主要考慮邊的信息傳遞能力，具有普遍通用性。由于只需要考慮網(wǎng)絡(luò)的最短路徑，介數(shù)指標的計算量相對較少。在海河網(wǎng)絡(luò)中，介數(shù)指標位于［3.000×10-4，4.510×10-2］區(qū)間，且多數(shù)邊的介數(shù)指標不相等。

邊的權(quán)值指標具體考慮了河道的長度、流量、最短路徑等因素，更能表征河流網(wǎng)絡(luò)的邊重要性。在海河網(wǎng)絡(luò)中，權(quán)值指標位于［4.168×10-6，5.000×10-3］區(qū)間，且邊的權(quán)值指標均不相等，因此邊的權(quán)值指標能精確區(qū)分每條邊的重要性。在權(quán)值指標中，海河干流具有最高的重要性，是整個海河網(wǎng)絡(luò)的核心。而在介數(shù)指標中，海河干流位于等級4，未能體現(xiàn)其重要性，與實際情況不相符。因此，權(quán)值指標更能準確找到河流網(wǎng)絡(luò)的重要邊。但邊的權(quán)值指標的計算量較大。

4 結(jié) 語

引入復(fù)雜網(wǎng)絡(luò)理論，建立了不含工程節(jié)點的海河網(wǎng)絡(luò)模型Ⅰ和含有工程節(jié)點的海河網(wǎng)絡(luò)模型Ⅱ。

針對河流網(wǎng)絡(luò)節(jié)點的特殊性，提出了河流網(wǎng)絡(luò)節(jié)點重要性的權(quán)值指標。研究了海河網(wǎng)絡(luò)的節(jié)點重要性，證明權(quán)值指標綜合考慮了節(jié)點的自身性質(zhì)、信息傳遞能力和節(jié)點間的距離等因素，能更準確地找到河流網(wǎng)絡(luò)的重要節(jié)點。針對河流網(wǎng)絡(luò)邊的特殊性，提出了河流網(wǎng)絡(luò)邊重要性的權(quán)值指標。通過計算海河網(wǎng)絡(luò)的邊重要性，證明邊的權(quán)值指標考慮更全面，更能表征河流網(wǎng)絡(luò)的邊重要性。

本文只是在所建河網(wǎng)模型的基礎(chǔ)上研究河流網(wǎng)絡(luò)的節(jié)點及邊的重要性指標，若能將其應(yīng)用到河流網(wǎng)絡(luò)模型的簡化研究中，刪除河流網(wǎng)絡(luò)中相對不重要的節(jié)點和邊，從而突出相對重要的節(jié)點和邊，有利于保護、監(jiān)控河流網(wǎng)絡(luò)中的重要信息，則更能體現(xiàn)其應(yīng)用價值。

［1］倪向萍，梅生偉，張雪敏.基于復(fù)雜網(wǎng)絡(luò)理論的輸電線路脆弱度評估方法［J］.電力系統(tǒng)自動化，2008，32(4):1-5.(NI Xiangping，MEI Shengwei，ZHANGXuemin.Transmission lines’vulnerability assessment based on complex networKtheory［J］.Automation of Electric Power Systems，2008，32(4):1-5.(in Chinese))

［2］趙月，杜文，陳爽.復(fù)雜網(wǎng)絡(luò)理論在城市交通網(wǎng)絡(luò)分析中的應(yīng)用［J］.城市交通，2009，7(1):57-65.(ZHAO Yue，DU Wen，CHEN Shuang.Application of complex networKtheory to urban transportation networKanalysis［J］.Urban Transport of China，2009，7(1):57-65.(in Chinese))

［3］SPORNSO.The human connectome:a complex network［J］.Ann N Y Acad Sci，2011，1224:109-125.

［4］田占偉，隋玚.基于復(fù)雜網(wǎng)絡(luò)理論的微博信息傳播實證分析［J］.圖書情報工作，2012，56(8):42-46.(TIAN Zhanwei，SUI Yang.The empirical analysis of micro-blog information flow based on complex networKtheory［J］.Library and Information Service，2012，56(8):42-46.(in Chinese))

［5］RINALDO A，RODRIGUEZ-ITURBE I，RIGON R，et al.Self-organized fractal river networks［J］.Physical Review Letters，1993，70(6):822-825.

［6］CIEPLAKM，GIACOMETTIA，MARITAN A，et al.Models of fractal River basins［J］.Journal of Statistical Physics，1998，91(1):1-15.

［7］何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)［M］.北京:高等教育出版社，2009.

［8］RODRIGUEZ-ITURBEI，RINALDOA，RIGONR，et al.Fractal structures as least energy dissipation patterns:the case of river networks［J］.Geophysical Research Letters，1992(5):2854-2860.

［9］RINALDO A，RODRIGUEZ-ITURBE I，RIGON R，et al.Self-organized fractal river networks［J］.Physical Review Letters，1993，70(3):822-825.

［10］沈丹，許田，蘇蓓蓓，等.長江流域的河流網(wǎng)絡(luò)及其統(tǒng)計描述［C］//方錦清.第二屆全國復(fù)雜動態(tài)網(wǎng)絡(luò)學術(shù)論壇論文集.北京:中國高等科學技術(shù)中心，2005:662-664.

［11］許田.對一些復(fù)雜網(wǎng)絡(luò)的統(tǒng)計描述與性質(zhì)的研究［D］.揚州:揚州大學，2004.

［12］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京:清華大學出版社，2006.

［13］HE Jinliao，ZONGYueguang，YANG Wei.The analysis of water networKof Beijing-Tianjin region based on the complex networKtheory［C］//LI Xia，LIU Lin.16th International Conference on Geoinformatics and the Joint Conference.Guangzhou:Sun Yatsen University Press，2008.

［14］全國水力資源復(fù)查工作領(lǐng)導(dǎo)小組.中華人民共和國水力資源復(fù)查成果(2003年)第一卷［M］.北京:中國電力出版社，2004.

［15］GIRVAN M，NEWMAN M E J.Community structure in social and biological networks［J］.Proc Natl Acad Sci，2002，99:782l-7826.