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

吳學(xué)文，瞿永鋼，李 玲

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院，江蘇南京 210098)

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

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

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

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

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

其中

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

1.2 應(yīng)用實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2.1 介數(shù)指標(biāo)

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

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

2.2.2.2 權(quán)值指標(biāo)

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

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

2.2.2.3 2種指標(biāo)對比分析

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

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

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

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

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

3.1.1 邊介數(shù)指標(biāo)

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

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

3.1.2 邊權(quán)值指標(biāo)

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

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

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

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

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

3.2.1 邊介數(shù)指標(biāo)

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

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

3.2.2 邊權(quán)值指標(biāo)

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

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

3.2.3 2種指標(biāo)對比分析

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

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

4 結(jié) 語

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

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

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

［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ò)理論的微博信息傳播實(shí)證分析［J］.圖書情報(bào)工作，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)計(jì)描述［C］//方錦清.第二屆全國復(fù)雜動態(tài)網(wǎng)絡(luò)學(xué)術(shù)論壇論文集.北京:中國高等科學(xué)技術(shù)中心，2005:662-664.

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

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