吳學文，瞿永鋼，李 玲

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

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

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

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

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

1.1 河流網(wǎng)絡模型構建

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

其中

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

1.2 應用實例

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

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

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

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

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

介數(shù)指標用來刻畫網(wǎng)絡中節(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)絡節(jié)點重要性權值指標

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

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

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

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

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

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

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

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

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

2.2.1 海河網(wǎng)絡構建

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

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

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

2.2.2.1 介數(shù)指標

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

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

2.2.2.2 權值指標

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

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

2.2.2.3 2種指標對比分析

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

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

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

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

3.1 河流網(wǎng)絡邊重要性的權值指標

3.1.1 邊介數(shù)指標

目前，研究邊的重要性有多種方法，例如邊介數(shù)指標［15］。邊介數(shù)指標通過計算邊介數(shù)來描述邊對網(wǎng)絡的信息傳遞能力［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 邊權值指標

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

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

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

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

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

3.2.1 邊介數(shù)指標

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

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

3.2.2 邊權值指標

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

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

3.2.3 2種指標對比分析

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

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

4 結(jié) 語

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

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

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

［1］倪向萍，梅生偉，張雪敏.基于復雜網(wǎng)絡理論的輸電線路脆弱度評估方法［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］趙月，杜文，陳爽.復雜網(wǎng)絡理論在城市交通網(wǎ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］田占偉，隋玚.基于復雜網(wǎng)絡理論的微博信息傳播實證分析［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］何大韌，劉宗華，汪秉宏.復雜系統(tǒng)與復雜網(wǎng)絡［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)絡及其統(tǒng)計描述［C］//方錦清.第二屆全國復雜動態(tài)網(wǎng)絡學術論壇論文集.北京:中國高等科學技術中心，2005:662-664.

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

［12］汪小帆，李翔，陳關榮.復雜網(wǎ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］全國水力資源復查工作領導小組.中華人民共和國水力資源復查成果(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.