配水管網(wǎng)管段改造排序的PageRank算法

李飛宇，石振鋒，吳晨光，于美婷，袁一星

（1.哈爾濱工業(yè)大學市政環(huán)境工程學院，150090哈爾濱；2.哈爾濱工業(yè)大學數(shù)學系，150001哈爾濱）

配水管網(wǎng)管段改造排序的PageRank算法

李飛宇1，石振鋒2，吳晨光1，于美婷2，袁一星1

（1.哈爾濱工業(yè)大學市政環(huán)境工程學院，150090哈爾濱；2.哈爾濱工業(yè)大學數(shù)學系，150001哈爾濱）

針對城市配水管網(wǎng)管段改造比選排序問題，提出了基于PageRank的改進的MPR-Pipe算法，實現(xiàn)了對管網(wǎng)節(jié)點和管段多種水力屬性的PR值求解.利用經(jīng)濟流量和管段單位水力坡降PR值，定義了管段改造的重要性度量，并以此作為改造比選排序的依據(jù).理論計算表明該算法求解效率較高，工程應用案例表明該算法提出的管段改造比選排序方案有效、可行.

配水管網(wǎng)；管段改造；PageRank；單位水力坡降；管段重要性

結合我國配水管網(wǎng)的實際情況，管網(wǎng)急需改造的原因主要包括：管網(wǎng)設備陳舊與老化；管網(wǎng)運行負荷較重；管網(wǎng)布局欠合理；水源新建及改造；更高的水質安全需求；節(jié)能降耗.因此，在對供水管網(wǎng)進行改造過程中應用管網(wǎng)水力模型，分析供水管網(wǎng)的工況，合理地對供水管網(wǎng)進行改造，特別是通過優(yōu)化管網(wǎng)改造的順序可以節(jié)約投資，最大限度地降低能量消耗，而且可以提高整個供水系統(tǒng)的安全性能，對于企業(yè)和社會都具有重要意義.為此，國內外開展了管網(wǎng)改造方面的研究，主要包括：管段老化模型研究［1］、管網(wǎng)運行現(xiàn)狀模型研究［2-3］、管網(wǎng)運行成本模型研究［4］及管網(wǎng)改造決策模型研究［5-6］，其中管網(wǎng)改造決策模型的建立與求解是最主要的研究方向，其結果可以直接指導管網(wǎng)改造問題［7］.管段老化模型、管網(wǎng)運行現(xiàn)狀分析、管段運行成本經(jīng)濟型分析，一般在構建和求解管網(wǎng)改造決策模型中起輔助作用［8］.同時，國內外還建立了多種優(yōu)化改造模型用于管網(wǎng)的改造，如基于多目標優(yōu)化的管網(wǎng)改造決策模型［6］、基于遺傳算法的管網(wǎng)優(yōu)化模型［9］.這些模型建模的思想、形式、復雜程度差異性較大，各有側重.

賦予靜態(tài)屬性和動態(tài)的狀態(tài)屬性后的供水管網(wǎng)在應用過程中可抽象為網(wǎng)絡.管網(wǎng)改造過程中管段的排序問題即可轉化為網(wǎng)絡中對連接邊的排序問題.Google網(wǎng)頁搜索過程中，通過網(wǎng)頁間的鏈接來評價網(wǎng)頁的重要性，這就是Google網(wǎng)頁搜索引擎中的核心算法——PageRank算法［10］.隨著對 PageRank算法的廣泛研究，其不僅在自身網(wǎng)頁排序中應用效果顯著，在很多領域都得到了應用，如圖書管推薦技術、網(wǎng)絡安全評估、Web數(shù)據(jù)挖掘等.借鑒PageRank算法在其他行業(yè)中的應用，利用管網(wǎng)改造管段排序問題和網(wǎng)頁排序問題的相似性，將PageRank算法引入城市配水管網(wǎng)改造的應用中目前未見報道.本文首先介紹了PageRank算法，并評述了其優(yōu)缺點.結合城市配水管網(wǎng)的特殊性，提出了適于管網(wǎng)改造排序應用的改進的PageRank算法，并定義了管段的重要性度量，進而給出管段改造排序的計算方法.最后，根據(jù)管段排序的結果并通過實例驗證，表明該算法描述管段重要性度量的定義是合理的、可行的，可為城市配水管網(wǎng)提供可行的科學改造方案.

1 PageRank算法簡介及評述

1.1 PageRank算法簡介

PageRank算法是Google網(wǎng)頁搜索引擎中的核心算法，由Google的創(chuàng)始人Sergey Brin和Lawrence Page［10］于1998年提出并得到了成功應用.其基本思想主要來自傳統(tǒng)文獻計量學中對文獻引用的研究和分析［11］，即一篇文獻被其他文獻引用的越多，說明文獻的質量就越高.假設網(wǎng)頁A鏈接網(wǎng)頁B，則可看作是網(wǎng)頁A對網(wǎng)頁B進行投票，根據(jù)投票數(shù)來判斷網(wǎng)頁的重要性（PageRank值，簡稱PR值）.PageRank技術根據(jù)整個Web的鏈接結構來計算各個網(wǎng)頁的重要性值，構造有向網(wǎng)頁圖G=＜V，E＞，其中頂點V為所有的網(wǎng)頁集合，邊 E為網(wǎng)頁中所有的鏈接集合，網(wǎng)頁A存在一條指向網(wǎng)頁B的鏈接即表示為網(wǎng)頁有向圖的邊E.PageRank算法的基本定義為

1.2 PageRank算法的不足

PageRank算法在Web頁面重要性應用中存在兩個主要的不足，即P R值沉淀現(xiàn)象和“黑洞效應”.在多個網(wǎng)頁彼此鏈接后形成的有向圖中，當網(wǎng)頁鏈接形成的有向圖之外的網(wǎng)頁鏈接到該有向圖內部的網(wǎng)頁時，就會出現(xiàn)有向圖內部網(wǎng)頁傳遞不出去PR值而導致傳遞進來的PR值一直滯留在此有向圖內部，即PR值沉淀現(xiàn)象.圖 1解釋了該現(xiàn)象.在圖1中，網(wǎng)頁A、B、C、D內部相互鏈接，無向外鏈接，網(wǎng)頁E、F分別鏈接網(wǎng)頁B和D，在應用PageRank算法進行迭代計算中，網(wǎng)頁E、F的PR值不能在網(wǎng)頁A、B、C、D形成的組內貢獻出去而出現(xiàn)沉淀的現(xiàn)象.為此，Sergrey Brin和Law Page對PageRank算法進行改進［13］，引入衰退因子D（Pi），對應某一網(wǎng)頁的初始PR值，改進算法即

其中‖P R（Pi）‖=1.

在求解式（2）描述的方程組時，其收斂性問題是關鍵.對于連通的有向Web圖G=＜V，E＞，設其中某個頂點的入度為0，由于其沒有對外貢獻PR值，P R值會逐漸減少，經(jīng)過有限次迭代之后，該連通圖內所有頂點的PR值將全部為0，這就是PageRank算法存在的“黑洞效應”，即入度為0的頂點就像黑洞一樣，將整個有向圖內的P R值全部慢慢“吸收”.然而，針對“黑洞效應”，Google并沒有公布其處理辦法，有些研究者認為可以將Web有向圖內所有的網(wǎng)頁均作為入度為0網(wǎng)頁的鏈接，這樣就能有效避免“黑洞效應”.

針對PageRank算法存在的上述兩個不足，在管段排序應用中，應該根據(jù)給水管網(wǎng)的實際特點，對PageRank算法進行適當改進.

2 面向管網(wǎng)改造管段排序的改進的PageRank算法——MPR-Pipe

2.1 改進的PageRank算法——MPR-Pipe

為將PageRank算法更好地應用在給水管網(wǎng)的管段改造排序問題，對PageRank算法作如下兩點改進：

1）在網(wǎng)頁模型中，網(wǎng)頁的屬性值只體現(xiàn)了鏈接數(shù)，各個鏈接只是數(shù)值上平分此網(wǎng)頁的PR值.給水管網(wǎng)中，每個管段具有更多實際意義的屬性值，如流量、流速、單位水頭損失等，不同的管段屬性值對管段的最終改造排序結果有重要的影響，因此，在管網(wǎng)模型中應以管段屬性信息值的比例來分配該管網(wǎng)節(jié)點的PR值.本文選用單位水力坡降.

2）根據(jù)PageRank算法的介紹，由式（1）可知，PageRank的名次和該網(wǎng)頁被鏈接的數(shù)目基本一致，無論該網(wǎng)頁鏈接多少網(wǎng)頁均幾乎不會影響PR值.相反有多少網(wǎng)頁鏈接該網(wǎng)頁從根本上決定網(wǎng)頁P R值的大小.本文提出對管段進行排序的改進的PageRank算法由管網(wǎng)節(jié)點的正向鏈接和反向鏈接共同決定，這種改進一方面結合了管網(wǎng)模型的實際情況，另一方面也有效地避免了在網(wǎng)頁模型中PageRank算法存在的沉淀現(xiàn)象和“黑洞效應”.

記I（Ji，Jj）為管網(wǎng)節(jié)點Ji到節(jié)點Jj的單位水頭損失，I（：，Ji）為所有流入節(jié)點Ji，并與節(jié)點Ji鏈接的節(jié)點構成的Ji單位水頭損失總和，I（Ji，：）為流出節(jié)點Ji，與節(jié)點Ji鏈接的節(jié)點構成的Ji單位水頭損失總和.在節(jié)點總數(shù)為NJ的給水管網(wǎng)中，改進的PageRank算法（modified PageRank for pipe，MPRPipe）可以概括為如下線性方程：

式中：i=1，2，...，NJ；

In（Ji）為流入管網(wǎng)節(jié)點 Ji的管網(wǎng)節(jié)點集合；Out（Ji）為從管網(wǎng)節(jié)點Ji流出的管網(wǎng)節(jié)點集合；c1和c2分別為流入與流出權重系數(shù)（介于0～1的常數(shù)），且c1+c2=1；d為阻尼因子，用于保證線性方程（3）的收斂性.

2.2 管段重要性度量的定義

通過方程組（3）求得供水管網(wǎng)中每個節(jié)點在流量、絕對水頭和自由水頭等屬性上的PR值.然而，管網(wǎng)改造過程中都是基于管段進行的，因此，需要利用每個節(jié)點的PR值定義管段重要性的度量.考慮到管段的單位水力坡降和流量是刻畫管段輸水能力和經(jīng)濟指標計算時的重要指標，本文將結合管段的單位水力坡降和實際計算流量與經(jīng)濟流量之間的關系來定義管段的重要性.設連接管段Pi的兩個節(jié)點分別為和的實際計算流量為，其經(jīng)濟流量為.則定義管段改造的重要性程度為

其中e1+e2=1.本文取e1=e2=0.5，利用供水管網(wǎng)中管段的單位水力坡降屬性來定義管段重要性度量，并稱為管段的PR值.由式（4）可以看出，當管道實際流量越大于經(jīng)濟流量時，管段的PR值就越大，據(jù)此排序在前，表明管段越急需改造，因此，式（4）具有明顯的物理意義.該PR值標明了所有管段改造的順序（不考慮管段改造的經(jīng)濟成本等因素）.當實際流量遠小于經(jīng)濟流量時，從物理意義上講也急需改造.在實際工程應用中，對這種管道的改造一般采用關閥改變供水管網(wǎng)邏輯拓撲結構，或調整閥門開度改變這部分管道的水力工況狀態(tài)等方案來實現(xiàn)管網(wǎng)的改造，不在本文的討論范圍之內.

2.3 MPR-Pipe算法的數(shù)值求解

給定管網(wǎng)有向圖G=＜V，E＞，定義管網(wǎng)的鄰接矩陣P，若管段i鏈接管段j，且水流方向為從管段i到管段j，則Pi，j=I（Ji，Jj），否則Pi，j=0.即

其中m=m（x）=（I-d）eTx=（I-d）‖x‖1為常數(shù)，于是可將式（6）簡化成線性方程組.記B=I-d（c1P1+ c2P2T），m=（I-d）v，則式（6）的求解過程轉化為對線性方程組（8）的求解，即

注意到管網(wǎng)中的節(jié)點數(shù)量通常較大，基于高斯消元法進行求解效率較低.為此，本文采用Jacobi迭代法，建立迭代公式

則MPR-Pipe算法轉換后的等效線性方程組Bx=m的Jacobi迭代矩陣為

綜上，MPR-Pipe算法可描述為

算法1面向管段改造排序的改進的PageRank算法

Input管網(wǎng)水力計算結果數(shù)據(jù)文件；阻尼因子d；流入和流出權重系數(shù)c1，c2；迭代終止精度ε；最大迭代次數(shù)MAX_Iter；

Output城市供水管網(wǎng)管段和節(jié)點的PR值；

Step 1讀取供水管網(wǎng)水力計算結果數(shù)據(jù)文件；

Step 2建立管段鄰接關系矩陣A_E；

Step 3由流入和流出權重系數(shù)c1，c2，建立與鄰接矩陣A_E相關的水力工況參數(shù)系數(shù)矩陣C_E；

利用線性方程組的Jacobi數(shù)值求解算法求解公式（6）；

ifδ＜εgoto Step 5；

end

Step 5根據(jù)節(jié)點的PR值，計算管段的PR值；Step 6保存管段和節(jié)點的PR值信息為數(shù)據(jù)文件.

3 結果及分析

3.1 數(shù)據(jù)結構設計

設計如下數(shù)據(jù)結構實現(xiàn)MPR-Pipe算法：

■節(jié)點的數(shù)據(jù)結構描述如下：

struct NODE｛ ／／節(jié)點結構

long innNo；／／內部編號

double dFlow_PR； ／／流量PR值

double dSpeed_PR； ／／流速PR值

double dFall_PR； ／／壓降PR值

｝；

■管段的數(shù)據(jù)結構描述如下：

struct PIPE｛ ／／管段結構

long innNo； ／／內部編號

long from_innNo； ／／流出節(jié)點內部編號

long to_innNo； ／／流入節(jié)點內部編號

double dFlow_PR； ／／流量PR值

double dSpeed_PR； ／／流速PR值

double dFall_PR； ／／壓降PR值

double dFall_1000_PR；／／單位水損PR值

｝；

■管網(wǎng)拓撲結構描述如下：

typedef struct ADJACENT_ELEMENT ｛

int no；

PIPE?pipe；

｝A_E；

typedef struct COEFFICIENT_ELEMENT ｛

int col；

double value；

｝C_E；

typedef struct WaterPipeNet ｛

vector＜PIPE＞pipe_list； ／／管段數(shù)組.

vector＜NODE＞node_list； ／／節(jié)點數(shù)組.

vector＜vector＜A_E＞＞row_type；／／鄰接矩陣

vector＜vector＜A_E＞＞col_type；／／鄰接矩陣

vector＜vector＜C_E＞＞cem；／／系數(shù)矩陣

｝GRAPH；

3.2 計算實例及分析

本文基于Embarcadero RAD XE 5平臺，利用C++編程實現(xiàn)了MPR-Pipe算法.以北方某市部分管網(wǎng)為例進行了仿真計算和分析，其管網(wǎng)拓撲如圖2所示.

在該管網(wǎng)拓撲結構中，由291條管段、259個節(jié)點及6個水廠構成.在水力計算過程中，共計算了24個時段，水力計算的邊界約束不做列出.利用本文的MPR-Pipe算法針對該管網(wǎng)24個時段水力計算結果中的管段流量、流速、水頭損失和單位水頭損失等動態(tài)水力屬性分別進行求解，花費的總計算時間為0.058 s.圖3給出了上述管網(wǎng)在23時、9時、14時和18時的管段改造重要性排序示意圖.

圖3中4個子圖中共標識了8條管段，其在24個時段中，有超過18個時段均具有較大的P R值.也就是說，從管段改造應用的意義上看，這8條管段為急需改造的管段，也是上述管網(wǎng)中的較“薄弱”管段.對于具有相同管材的管段，其阻力系數(shù)C值會隨著敷設年代的增加而逐漸變小，在相同的用水形式下，其單位管段水力坡降也會變大.根據(jù)管段重要性的定義，對于單位水力坡降較大的管段，如果計算得到的流量小于經(jīng)濟流量的管段，則其重要性將按照指數(shù)級（小于1）平緩；對于實際計算流量大于經(jīng)濟流量的管段，其重要性將按照指數(shù)級（大于1）提升，從而加速這部分管段的排序，成為急需改造的管段.

3.3 MPR-Pipe算法與傳統(tǒng)分析方法的比較

為了驗證本文算法的合理性和有效性，以高日高時為水力計算的基本工況，與傳統(tǒng)的管段運行負荷計算方法［14］得到的結果進行了比較，結果如圖 4所示.其中管段運行負荷中的經(jīng)濟指標等因素與本文中計算經(jīng)濟流量時設定的參數(shù)相同.可以看出，本文得到的8條急需改造的管段，其運行負荷普遍高于其他管段.在這一點上本文定義的重要性較好地包括了傳統(tǒng)的管段運行負荷分析的范疇.然而，在運行負荷分析方法中，有較多的管段處于略低負荷、經(jīng)濟負荷及略超負荷等，尚不能較好地給出管段改造的排序結果.本文提出的管段重要性度量可較好地對運行負荷偏高的管段實現(xiàn)數(shù)值上較大范圍的放大，而運行負荷較低的管段則實現(xiàn)了數(shù)值上較大范圍的縮小，從而可更有效地實現(xiàn)管段重要性兩個不同層級上的區(qū)分，也更有利于快速實現(xiàn)急需改造管段的選擇.因此，從傳統(tǒng)的管段改造角度看，本文算法得到的排序結果要優(yōu)于通過管段運行負荷分析得到的改造的管段集合.

綜上，本文提出的改進的PageRank算法快速地實現(xiàn)了對管段改造方案的比選排序，該排序結果綜合反映了管段的單位水頭損失和經(jīng)濟流量的情況.對于敷設年代較久遠的管段，因其單位水力坡降較大而可能成為排序中急需改造的管段.本文算法得到的排序結果已成功應用于該城市這部分供水管網(wǎng)的實際改造.由于管徑的優(yōu)化選擇不在本文的討論范圍之內，這里僅給出了需要改造管段的優(yōu)先順序，而未給出這些管段改造后的管徑選擇方案.

4 結 論

1）基于PageRank算法，提出了面向城市配水管網(wǎng)改造管段排序應用的改進的 PageRank算法——MPR-Pipe算法.

2）基于MPR-Pipe算法，定義了管段改造排序的重要性度量——管段改造的PR值.

3）基于管段改造的PR值得到管段改造排序方案，實現(xiàn)了對北方某城市部分管網(wǎng)的實際改造應用，表明本文的方法具有實用的工程意義和理論意義.

［1］WATSON T，MASON A.A hierarchical Bayesian model for the maintenance of water pipe networks［C］／／Proceedings of the 7“International Conference on Hydroinfor-Matics.France：Nice，2006：2991-2998.

［2］GYERGYEK L，PERSEN S.Simulation and optimal control of large water distribution systems［J］.Mathematics and Computers in Simulation，1982，96（2）：214-216

［3］舒詩湖，何文杰，趙明，等.供水管網(wǎng)漏失檢測技術現(xiàn)狀與進展［J］.給水排水，2008，34（6）：114-116.

［4］SAVIC D A，WALTERS G A.Genetic algorithms for least-cost design of water distribution networks［J］.Journal of Water Resources Planning and Management，1997，123（2）：67-77.

［5］MALM A，SVENSSON G，B?CKMAN H，et al.Prediction of water and wastewater networks rehabilitation based current age and material distribution［J］.Water Science＆Technology：Water Supply，2013，13（2）：23-28.

［6］ROSHANI E，F(xiàn)ILION Y R.Multi-objective rehabilitation planning of water distribution systems under climate change mitigation scenarios ［J］. Bridges，2014，10：9780784412312.321.

［7］SARGAONKAR A，KAMBLE S，RAO R.Model study for rehabilitation planning of water supply network［J］.Computers，Environment and Urban Systems，2013，39：172-181.

［8］BEALE D J，MARLOW D R，COOK S.Estimating the cost and carbon impact of a long term water main rehabilitation strategy［J］.Water Resources Management，2013，27（11）：3899-3910.

［9］KANTA L，ZECHMAN E，BRUMBELOW K.Multiobjective evolutionary computation approach for redesigning water distribution systems to provide fire flows［J］.Journal of Water Resources Planning and Management，2011，138（2）：144-152.

［10］BRIN S，PAGE L.The anatomy of a large-scale hypertextual web search engine［J］.Computer Networks and ISDN Systems，1998，30（1）：107-117.

［11］GIBSON D.Device discovery and power management in embedded systems［C］／／Proceedings of the Linux Symposium 2003.Ottawa：［s.n.］，2003：213-224.

［12］AUSTIN D.How Google finds your needle in the web’s haystack［J］.American Mathematical Society Feature Column，2006，10：12.

［13］PAGE L，BRIN S，MOTWANI R，et al.The PageRank citation ranking：bringing order to the web［J］.Stanford Infolab，1999，9（1）：1-14.

［14］趙洪濱.給水管網(wǎng)系統(tǒng)理論與分析［M］.北京：中國建筑工業(yè)出版社，2003：312-313.

（編輯 劉 彤）

PageRank-based selection sort of pipe renewal in water distribution system

LI Feiyu1，SHI Zhenfeng2，WU Chenguang1，YU Meiting2，YUAN Yixing1

（1.School of Municipal and Environmental Engineering，Harbin Institute of Technology，150090 Harbin，China；2.Department of Mathematics，Harbin Institute of Technology，150001 Harbin，China）

A novel modified Page Rank algorithm for pipe renewal（MPR-Pipe）is presented to realize selection sort and provide Page Rank values of static and dynamic attributions of junctions and pipes in water distribution systems.The measurement of pipe renewal significance，well defined on the grounds of economic flow and unit hydraulic gradient，can be taken as the criterion for the selection sort of pipe renewal.Theoretical calculations confirm the high efficiency of the algorithm，and engineering application cases indicate the effectiveness and feasibility of the renewal plan based on MPR-Pipe algorithm.

water distribution system；pipe renewal；PageRank；unit hydraulic gradient；pipe significance

TU821.3

A

0367-6234（2015）08-0025-05

10.11918／j.issn.0367-6234.2015.08.006

2014-06-20.

國家自然科學基金（51178141）；水體污染控制與治理科技重大專項（2012ZX07408-002-004-002）.

李飛宇（1981—），男，博士研究生；袁一星（1957—），男，教授，博士生導師.

吳晨光，wu.cg＠126.com.