吳學(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ò)動(dòng)態(tài)特性;田占偉等［4］發(fā)現(xiàn)微博信息傳播網(wǎng)絡(luò)具有集群性、小世界、高度中心化等特征。

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

筆者應(yīng)用復(fù)雜網(wǎng)絡(luò)理論來(lái)建立河流網(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)、河流出口、水電站、水庫(kù)、水閘等;邊是指河水在節(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í)例

海河水系是中國(guó)華北地區(qū)最大的水系。根據(jù)《中華人民共和國(guó)水力資源復(fù)查成果》及其他相關(guān)資料［14］，將海河水系抽象概化為網(wǎng)絡(luò)圖，建立海河網(wǎng)絡(luò)模型Ⅰ(圖1)，其包括344個(gè)節(jié)點(diǎn)和385條邊，只含自然節(jié)點(diǎn)和自然河道。為了研究工程節(jié)點(diǎn)、人工河道對(duì)河流網(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)識(shí)、預(yù)測(cè)和控制整個(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)用來(lái)刻畫(huà)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)于信息流動(dòng)的影響力。節(jié)點(diǎn)x的介數(shù)指標(biāo)定義為

式中:gjk(x)——gjk中經(jīng)過(guò)節(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)過(guò)節(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)之間的連線對(duì)應(yīng)于實(shí)體中的河道，連線長(zhǎng)度對(duì)應(yīng)于河道長(zhǎng)度。連線長(zhǎng)度體現(xiàn)了節(jié)點(diǎn)之間的緊密程度，連線越長(zhǎng)，河道就越長(zhǎng)，節(jié)點(diǎn)之間就越疏遠(yuǎn)。因此，將該節(jié)點(diǎn)到其余節(jié)點(diǎn)的最短河道長(zhǎng)度的倒數(shù)之和定義為節(jié)點(diǎn)的距離權(quán)值。當(dāng)節(jié)點(diǎn)之間有多條路徑時(shí)，選擇河道長(zhǎng)度最短的路徑來(lái)計(jì)算距離權(quán)值。節(jié)點(diǎn)的距離權(quán)值可表示為

式中:Dxy——節(jié)點(diǎn)x到節(jié)點(diǎn)y的最短河道長(zhǎng)度;dxy——節(jié)點(diǎn)x到節(jié)點(diǎn)y的一條路徑長(zhǎng)度。對(duì)于無(wú)向網(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條邊的簡(jiǎn)化海河網(wǎng)絡(luò)模型，如圖3所示。

圖3 簡(jiǎn)化海河網(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è)等級(jí)，如表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è)等級(jí)，如表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)對(duì)比分析

在海河網(wǎng)絡(luò)中，介數(shù)指標(biāo)對(duì)節(jié)點(diǎn)的重要性劃分較詳細(xì)。介數(shù)指標(biāo)能找到獨(dú)流減河進(jìn)洪閘、向陽(yáng)口一級(jí)水電站、官?gòu)d水庫(kù)等最重要的節(jié)點(diǎn)(等級(jí)1～2)，這些節(jié)點(diǎn)的度不一定大，但對(duì)于整個(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)。因此，在對(duì)源口的分析上，權(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ò)的邊重要性分析

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

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

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

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

式中:g'jk(x)——g'jk中經(jīng)過(guò)邊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)過(guò)邊x)。

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

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

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

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

式中:Q'(x)——邊x對(duì)應(yīng)河道的多年平均流量;Q'max——網(wǎng)絡(luò)中河道多年平均流量的最大值。邊權(quán)值指標(biāo)定義為邊介數(shù)、邊長(zhǎng)度權(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è)等級(jí)，如表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è)等級(jí)，如表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)對(duì)比分析

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

邊的權(quán)值指標(biāo)具體考慮了河道的長(zhǎng)度、流量、最短路徑等因素，更能表征河流網(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)中，海河干流位于等級(jí)4，未能體現(xiàn)其重要性，與實(shí)際情況不相符。因此，權(quán)值指標(biāo)更能準(zhǔn)確找到河流網(wǎng)絡(luò)的重要邊。但邊的權(quán)值指標(biāo)的計(jì)算量較大。

4 結(jié) 語(yǔ)

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

針對(duì)河流網(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)。針對(duì)河流網(wǎng)絡(luò)邊的特殊性，提出了河流網(wǎng)絡(luò)邊重要性的權(quán)值指標(biāo)。通過(guò)計(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ò)模型的簡(jiǎn)化研究中，刪除河流網(wǎng)絡(luò)中相對(duì)不重要的節(jié)點(diǎn)和邊，從而突出相對(duì)重要的節(jié)點(diǎn)和邊，有利于保護(hù)、監(jiān)控河流網(wǎng)絡(luò)中的重要信息，則更能體現(xiàn)其應(yīng)用價(jià)值。

［1］倪向萍，梅生偉，張雪敏.基于復(fù)雜網(wǎng)絡(luò)理論的輸電線路脆弱度評(píng)估方法［J］.電力系統(tǒng)自動(dò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］.圖書(shū)情報(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］沈丹，許田，蘇蓓蓓，等.長(zhǎng)江流域的河流網(wǎng)絡(luò)及其統(tǒng)計(jì)描述［C］//方錦清.第二屆全國(guó)復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)學(xué)術(shù)論壇論文集.北京:中國(guó)高等科學(xué)技術(shù)中心，2005:662-664.

［11］許田.對(duì)一些復(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］全國(guó)水力資源復(fù)查工作領(lǐng)導(dǎo)小組.中華人民共和國(guó)水力資源復(fù)查成果(2003年)第一卷［M］.北京:中國(guó)電力出版社，2004.

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