楊之江，周煜岷，扈 震，曾 文，周 揚，李曉麗，馮 麗

（1.中國地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院，湖北武漢 430078；2.武漢眾智鴻圖科技有限公司，湖北武漢 430074）

在城市化發(fā)展進(jìn)程中，供水管網(wǎng)漏損率居高不下，管理難度越來越大。科學(xué)合理地劃分獨立計量分區(qū)（district metering area，DMA）對供水管網(wǎng)漏損控制至關(guān)重要［1］。近年來，許多學(xué)者研究并提出多種基于網(wǎng)絡(luò)拓?fù)涞墓┧芫W(wǎng)分區(qū)優(yōu)化方法，模塊度優(yōu)化和譜聚類算法是其中2種主流的方法，在供水管網(wǎng)分區(qū)中得到了廣泛應(yīng)用［2］。

在基于模塊度優(yōu)化的管網(wǎng)分區(qū)方法中，Diao等［3］利用快速模塊度優(yōu)化算法對供水管網(wǎng)進(jìn)行社區(qū)結(jié)構(gòu)劃分，證明了該算法用于供水管網(wǎng)分區(qū)的有效性；Liu等［4］分別采用快速模塊度優(yōu)化、隨機游走和Metis算法對案例管網(wǎng)進(jìn)行分區(qū)實驗，相比隨機游走和Metis方法，驗證快速模塊度優(yōu)化算法能得到高模塊度的分區(qū)方案；在基于譜聚類的管網(wǎng)分區(qū)方法中，Herrera等［5］利用譜聚類算法，以管徑和標(biāo)高差作為邊的權(quán)值，構(gòu)建相似度矩陣，將相似度高的節(jié)點劃分到同一分區(qū)；Nardo等［6］運用加權(quán)譜聚類算法，考慮管網(wǎng)幾何和水力特性，確定了管網(wǎng)最優(yōu)分區(qū)布局?？焖倌K度優(yōu)化算法（Fastgreedy）相比譜聚類算法（Spectral Clustering，SC），雖然能生成較高模塊度的分區(qū)結(jié)果，但也會產(chǎn)生更多的邊界管道，而SC能約束邊界管道數(shù)量，但在模塊度方面表現(xiàn)一般。通過這2種分區(qū)算法所得到的分區(qū)方案在綜合模塊度和邊界管道數(shù)均衡性方面表現(xiàn)較差，更重要的是它們在對供水管網(wǎng)分區(qū)時，會產(chǎn)生狹長型無效分區(qū)（同一分區(qū)邊界線部分重疊，成線狀向外突出的區(qū)域），不便于分區(qū)管理。此外，水力特征是影響管網(wǎng)分區(qū)有效性的重要因素之一，分區(qū)不可避免地會增加管網(wǎng)水頭損失［6］，同時管網(wǎng)的鋪設(shè)以街區(qū)為最小單元不斷擴展，形成商業(yè)、工業(yè)、居住等功能分區(qū)，最后形成的管網(wǎng)空間布局會帶有明顯的中心性、空間分異性［7］。Yao等［8］指出地區(qū)功能區(qū)特征由其所提供的基礎(chǔ)設(shè)施服務(wù)所表征，可以用區(qū)域內(nèi)部各類興趣點分布（points of interest，POIs）來描述。而Fast-greedy和SC本身沒有考慮管網(wǎng)的水力特征和空間布局。

本文研究耦合模塊度優(yōu)化與譜聚類的供水管網(wǎng)分區(qū)算法（coupling modularity optimization and spectral clustering algorithm，MOSC）。該算法結(jié)合管網(wǎng)水力特征和空間布局，對中國某市供水管網(wǎng)分區(qū)，以模塊度和邊界管道數(shù)為指標(biāo)，構(gòu)建MOSC與Fast-greedy、SC對比實驗，驗證MOSC有效性。

1 快速模塊度優(yōu)化和譜聚類算法

1.1 快速模塊度優(yōu)化算法

模塊度Q是衡量網(wǎng)絡(luò)劃分為社區(qū)的強度指標(biāo)，以Q值的大小來評價社區(qū)劃分的優(yōu)劣，Q值越接近1時，表示對社區(qū)結(jié)構(gòu)的劃分越好；模塊度Q值越大，社區(qū)內(nèi)部連接越緊密，社區(qū)間連接越稀疏，分區(qū)效果越好［9］。基于模塊度Q最大化的快速模塊度優(yōu)化算法是一種自下而上的貪婪優(yōu)化算法，該算法基于貪心算法的思想，從每個節(jié)點為一個社區(qū)開始，依次合并相鄰的社區(qū)計算產(chǎn)生的模塊度變化量ΔQ，沿著模塊度Q增加最大的方向不斷合并社區(qū)，直到獲得模塊度Q最大所對應(yīng)的社區(qū)劃分結(jié)果［10］。模塊度Q計算公式可表示為

式中：A為網(wǎng)絡(luò)的鄰接矩陣，v和w為節(jié)點，若節(jié)點v和節(jié)點w相連，則A vw=1，否則A vw=0。m為網(wǎng)絡(luò)的邊數(shù)，kv，kw分別為節(jié)點v、w的度，即連接到節(jié)點v、w的邊數(shù)。Cv為節(jié)點v所在的社區(qū)。若節(jié)點v和節(jié)點w在同一社區(qū)，則Cv=Cw，δ=1，否則δ=0。

1.2 譜聚類算法

邊界管道是指連接不同管網(wǎng)分區(qū)之間的管道，由于供水管網(wǎng)分區(qū)方案是通過在邊界管道上安裝流量計和閘閥來實現(xiàn)，它的數(shù)量決定了分區(qū)改造的經(jīng)濟成本，所以從經(jīng)濟成本角度，邊界管道數(shù)量越少越好［11］。在邊界管道數(shù)量上表現(xiàn)優(yōu)異的譜聚類算法建立在圖論中的譜圖劃分理論基礎(chǔ)上，是一種基于兩點間相似關(guān)系的聚類算法，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題［12］。該算法利用特征值和特征向量挖掘管網(wǎng)的社區(qū)結(jié)構(gòu)，得到的聚類結(jié)果中社區(qū)內(nèi)部相似度高，社區(qū)間相似度低且規(guī)模相似。該算法的最大特點是能使分割的邊界管道數(shù)量少［13］。此方法的具體步驟為［2，14］：

（1）計算圖的拉普拉斯（Laplacian）矩陣

式中：A為鄰接矩陣；D為對角矩陣（也稱度矩陣），對角線上的值為節(jié)點的度，為節(jié)點i與節(jié)點j之間的權(quán)重。

（2）拉普拉斯矩陣L標(biāo)準(zhǔn)化為

（3）計算L rw的特征值與特征向量。Luxburg［15］指出求解圖的拉普拉斯矩陣的零特征值對應(yīng)特征向量個數(shù)等于圖的連通分量個數(shù)。更進(jìn)一步，將特征值從小到大排序取前k個較小特征值構(gòu)成的譜空間中，拓?fù)渎?lián)系緊密，相似性權(quán)重高的節(jié)點處于一個區(qū)域，而拓?fù)渎?lián)系稀疏相似性較低的樣本對則處于不同的區(qū)域，從而實現(xiàn)樣本在高維空間中的線性可分。故按特征值從小到大取前k個特征向量組成矩陣X=[x1，x2，…，x k]∈Rn×k，取矩陣X的行向量，得到矩陣Y，將矩陣Y的每一行作為Rk空間中的一點y。

（4）利用K-means算法對Rk空間中的每一點y進(jìn)行聚類，得到最終的聚類結(jié)果。

2 MOSC與評價指標(biāo)

2.1 MOSC

針對Fast-greedy和SC的不足，MOSC耦合Fast-greedy和SC，一方面，集成Fast-greedy對網(wǎng)絡(luò)拓?fù)渚o密連接結(jié)構(gòu)的高模塊度社區(qū)挖掘能力，另一方面，集成SC對邊界管道數(shù)量的約束能力，并綜合考慮管網(wǎng)的水力特征和空間布局。MOSC包含3個步驟：最優(yōu)模塊度求解、對偶圖構(gòu)建和拉普拉斯特征分解與聚類，如圖1所示。

圖1 MOSC流程圖Fig.1 Flowchart of MOSC

2.1.1 最優(yōu)模塊度求解

城市供水管網(wǎng)是由相互連接的管道和其他附屬設(shè)施組成的設(shè)施網(wǎng)絡(luò)，水通過這些管道以及附屬設(shè)施輸送到需水節(jié)點，以滿足系統(tǒng)的用水需求和壓力要求［16］。在管網(wǎng)無向無權(quán)圖G=(V，E)中，以取水點、水表、閥門等作為節(jié)點，V={v1，v2，…，vn}為節(jié)點集，vi∈V，i=1，2，…，n為管網(wǎng)節(jié)點，以相鄰節(jié)點之間的管道作為邊，E={e1，e2，…，em}為邊集，ej=(vj1，vj2)，ej∈E，j=1，2，…，m為管段。最優(yōu)模塊度求解的具體步驟為：

（1）利用Fast-greedy對圖G進(jìn)行社區(qū)劃分，初始化每個節(jié)點為一個社區(qū)，初始條件下的社區(qū)劃分結(jié)果為C0={c1，c2，…，cn}，ci為第i個節(jié)點所在的社區(qū)，此時，vi∈ci，i=1，2，…，n，計算初始化條件下的模塊度Qt0。

（2）遍歷圖G所有連邊，分別合并相鄰2個社區(qū)，得到每一種合并方案并計算對應(yīng)的模塊度Qt1，對比初始狀態(tài)下的模塊度Qt0。得到模塊度變化量

式中：Qt0為當(dāng)前社區(qū)合并條件下的管網(wǎng)模塊度；Qt1為合并2個社區(qū)之后的模塊度。

（3）取合并后ΔQ最大的合并方案為新的社區(qū)劃分方案，劃分后的結(jié)果為C1={c1，c2，…，cn?1}，其中c1，c2，…，cn?1為劃分后的社區(qū)。

（4）重復(fù)上述社區(qū)合并過程，當(dāng)Q最大時，停止合并，得到對應(yīng)的社區(qū)劃分結(jié)果C={c1，c2，…，cl}，其中c1，c2，…，cl為最終社區(qū)。

2.1.2 對偶圖構(gòu)建

基于社區(qū)劃分結(jié)果，結(jié)合社區(qū)內(nèi)部的水力特征與空間分布特征來描述社區(qū)，完成對偶圖的構(gòu)建。如圖2所示，圖中ci為第i個社區(qū)，w ij為社區(qū)i與社區(qū)j之間的權(quán)重，i，j=1，2，…，7。

圖2 社區(qū)劃分對偶圖Fig.2 Duality map of community division

社區(qū)劃分對偶圖的具體構(gòu)建步驟為：

（1）以社區(qū)劃分結(jié)果為基礎(chǔ)，將社區(qū)作為節(jié)點，社區(qū)之間的連接關(guān)系作為邊，構(gòu)建社區(qū)劃分對偶圖G′=(V′，E′)，其 中V′=C={c1，c2，…，cl}為 節(jié) 點集，cx∈V′，x=1，2，…，l為 對 偶 圖 節(jié) 點，E′={e′1，e′2，…，ez′}為邊集，e′y=(cy1，cy2)，e′y∈E′，cy1≠cy2，y=1，2，…，z為對偶圖邊。

（2）為了降低水頭損失，得到對管網(wǎng)水力性能影響最小的分區(qū)布局，提出以下水力特征向量Hd

式中：La為社區(qū)內(nèi)平均管徑；Da為社區(qū)內(nèi)平均管長；Ha為社區(qū)內(nèi)平均節(jié)點高程。

（3）提出以餐飲、購物、醫(yī)療服務(wù)、住宿、政府機關(guān)、休閑娛樂、交通出行和科研教育8個類型的POIs數(shù)量來表征社區(qū)內(nèi)部的空間區(qū)位特征，得到以下功能結(jié)構(gòu)特征向量Fc：

式中：n1，n2，…，n8分別表示餐飲、購物等8個類型的POIs數(shù)量。

（4）拼接水力特征向量和功能結(jié)構(gòu)特征向量得到總的特征向量

式中：x i為第i個節(jié)點對應(yīng)社區(qū)的總特征向量；nij為第i個節(jié)點對應(yīng)社區(qū)的第j種類型的POIs數(shù)量。

（5）對每個特征向量進(jìn)行標(biāo)準(zhǔn)化zi=(ti?μ)/σ，其中，zi為x i中各個特征向量標(biāo)準(zhǔn)化后的特征值，ti為x i中的各個特征向量的特征值，μ為所有x i中各個特征向量特征值的均值，σ為所有x i中各個特征向量特征值的標(biāo)準(zhǔn)差。計算各個社區(qū)之間標(biāo)準(zhǔn)化后的特征向量歐氏距離d ij=‖ ‖x i?x j，變化得到相似性作為邊權(quán)重

式中：std(d ij)為d ij的標(biāo)準(zhǔn)差。

2.1.3 拉普拉斯特征分解與聚類

基于構(gòu)建的對偶圖G′=(V′，E′)，利用SC，通過拉普拉斯特征分解和K-means聚類，得到管網(wǎng)分區(qū)結(jié)果。具體分區(qū)步驟為：

（1）計算對偶圖G′的拉普拉斯矩陣

式 中：W為 帶 權(quán) 鄰 接 矩 陣，W=(w ij)，i，j=1，2，…，n；D為 帶 權(quán) 度 矩 陣，D=diag(d i)，d i=

（2）計算標(biāo)準(zhǔn)化拉普拉斯矩陣Lrw的特征值與特征向量

（3）按特征值從小到大取前k個特征向量組成矩陣V=[v1，v2，…，v k]，V∈Rn×k，取V的行向量作為節(jié)點的譜空間表征yi∈Rk，i=1，2，…，n，該特征空間中，拓?fù)溧徑忧姨卣髅枋鱿嗨频臉颖军c聚集在一起。

（4）利用譜空間特征向量進(jìn)行K-means聚類，得到分區(qū)結(jié)果C′=(c′1，c′2，…，c′k)，其中c′1，c′2，…，c′k為各個分區(qū)。

2.2 評價指標(biāo)

通過MOSC可以得到不同分區(qū)數(shù)量的分區(qū)方案，為了選出在模塊度和邊界管道數(shù)上表現(xiàn)最好的方案，引入綜合評價值F，該值是以模塊度和邊界管道數(shù)作為評價指標(biāo)，通過簡單加權(quán)歸一化公式［17］計算得到，F(xiàn)的計算公式為

式中：rm、rc分別為分區(qū)方案對應(yīng)的模塊度和邊界管道數(shù)；r′m、r′c分別為歸一化后的模塊度和邊界管道數(shù)；wm、wc分別為模塊度和邊界管道數(shù)的權(quán)重。

3 案例分析

采用我國某市管徑100mm以上的實際供水管網(wǎng)作為實例分析數(shù)據(jù)，以模塊度和邊界管道數(shù)為指標(biāo)，分析MOSC與Fast-greedy、SC的對比實驗結(jié)果，驗證MOSC用于供水管網(wǎng)分區(qū)的有效性。管網(wǎng)的基本信息如表1。

表1 實例管網(wǎng)基本信息Tab.1 Basic information of water network cases

3.1 對比實驗

對實例管網(wǎng)數(shù)據(jù)利用Fast-greedy、SC和MOSC求解分區(qū)，其中Fast-greedy由開源igraph模塊實現(xiàn)，SC由sklearn.cluster模塊實現(xiàn)。以模塊度作為分區(qū)形態(tài)指標(biāo)，以邊界管道數(shù)量作為分區(qū)成本指標(biāo)構(gòu)建對比實驗。以MOSC作為實驗組，以Fast-greedy、管徑為邊權(quán)的SC作為對照組進(jìn)行分區(qū)數(shù)量10到50的實驗，實驗結(jié)果如圖3所示。其中，SC的加權(quán)具體計算方式為，將第1.2節(jié)中的鄰接矩陣A改寫為以管徑（d）的賦權(quán)形式。即

從圖3a可以看出，在模塊度方面，F(xiàn)ast-greedy與SC差異較大，尤其在分區(qū)數(shù)較少時，SC模塊度迅速降低，整體上也低于Fast-greedy，而MOSC耦合了Fastgreedy，所以保持較高的模塊度，最后從MOSC的曲線看出，由于該算法引入了許多分區(qū)特征，隨著分區(qū)數(shù)量的減少，MOSC的模塊度減少速度明顯慢于SC，在分區(qū)數(shù)較少時也不會損失太多的模塊度值；隨著分區(qū)數(shù)量的增多，MOSC的模塊度越來越接近Fast-greedy的模塊度，直至完全重合，因此通過MOSC所得的分區(qū)結(jié)果模塊度高。圖3b可以直觀反映出，在邊界管道數(shù)量上，SC明顯低于Fast-greedy，而通過MOSC得到的邊界管道數(shù)量與SC非常接近。隨著分區(qū)數(shù)量的增多，尤其是分區(qū)數(shù)量在16及以上時，MOSC與SC的邊界管道數(shù)曲線完全重合，因此MOSC所得的邊界管道少。MOSC耦合了Fast-greedy和SC，使得該算法集成了這2種算法的優(yōu)點，在保持較高模塊度的條件下，能盡量減少邊界管道的數(shù)量，該算法在模塊度和邊界管道數(shù)上表現(xiàn)比較均衡。

圖3 對比實驗結(jié)果Fig.3 Comparison of experimental result

3.2 MOSC有效性

圖4顯示了利用MOSC得到11～35個不同分區(qū)數(shù)量方案對應(yīng)的模塊度和邊界管道數(shù)。以模塊度和邊界管道數(shù)作為綜合評價指標(biāo)F的重要依據(jù)，其權(quán)值為wm=wc=0.5。得到從11～35這25個不同分區(qū)方案的綜合評價值，如圖5所示。

圖4 MOSC實驗結(jié)果Fig.4 MOSC of experimental result

圖5 分區(qū)方案綜合評價Fig.5 Overall merit of partition plan

分析圖5發(fā)現(xiàn)，分區(qū)數(shù)量17的分區(qū)方案綜合評價值F（0.653）最高，所以采用分區(qū)數(shù)量17的分區(qū)方案。分別利用Fast-greedy、以管徑為邊權(quán)的SC和MOSC對該實例供水管網(wǎng)進(jìn)行分區(qū)數(shù)量17的分區(qū)實驗，對應(yīng)的模塊度和邊界管道數(shù)量如表2所示。在MOSC進(jìn)行分區(qū)的過程中，通過Fast-greedy對該實例供水管網(wǎng)圖G進(jìn)行社區(qū)劃分，得到數(shù)量為360、模塊度為0.998的社區(qū)劃分結(jié)果，并構(gòu)建社區(qū)劃分對偶圖，結(jié)合平均管徑、平均管長、平均節(jié)點高程的水力特性以及各類POIs數(shù)量的功能結(jié)構(gòu)特征計算相似性矩陣，實現(xiàn)SC，得到該方案的分區(qū)結(jié)果。3種算法所得的分區(qū)結(jié)果如圖6所示。

表2 分區(qū)數(shù)量17的對比結(jié)果Tab.2 Comparison of Section No.17

分析圖6d發(fā)現(xiàn)，MOSC捕獲到了管網(wǎng)的單中心空間布局，將管網(wǎng)密度較大的中心城區(qū)管網(wǎng)劃分為1、2、3這3個分區(qū)，市郊劃分為其他分區(qū)；分析圖6b、6c、6d發(fā)現(xiàn)，對比這3種算法所得的分區(qū)邊界形狀，F(xiàn)ast-greedy和SC的結(jié)果都產(chǎn)生了狹長型無效分區(qū)，圖6b和圖6c中標(biāo)注的數(shù)字1到6分別代表6個不同分區(qū)，對比圖7a、7b、7c，圖7a的1分區(qū)中，有兩部分已經(jīng)延伸到了2分區(qū)中，這兩部分即為狹長型無效分區(qū)，從空間位置上來說，它們本該屬于2分區(qū)，這是由于Fast-greedy僅僅只考慮了管網(wǎng)中管段間的拓?fù)浣Y(jié)構(gòu)，只是依次合并相鄰的2個社區(qū)，并沒有考慮管段的空間位置，同樣圖7b的1分區(qū)中，也出現(xiàn)了狹長型無效分區(qū)，加權(quán)SC只是以管徑作為邊權(quán)重，構(gòu)建相似度矩陣，同樣也是依賴管段間的拓?fù)浣Y(jié)構(gòu)，而在MOSC社區(qū)劃分對偶圖構(gòu)建過程中，以管段管長、節(jié)點高程等為水力特征，尤其是以該市各類POIs數(shù)量作為管網(wǎng)空間區(qū)位特征，綜合這2種特征所得到的對偶圖邊權(quán)重，考慮了管段空間位置，將空間上更鄰近的管段劃分在同一分區(qū)，如圖7c所示，相對于這2種算法MOSC不會產(chǎn)生該類型的分區(qū)。

圖6 3種算法分區(qū)結(jié)果Fig.6 Partitioning result of three algorithms

圖7 3種算法分區(qū)局部結(jié)果Fig.7 Partitioning local results of three algorithms

4 結(jié)論

利用Fast-greedy對管網(wǎng)的高模塊度社區(qū)劃分能力以及SC對于最小邊界管道的識別能力，提出一種耦合模塊度優(yōu)化與譜聚類的管網(wǎng)分區(qū)算法MOSC。對比該算法與Fast-greedy和SC在模塊度以及邊界管段數(shù)量的表現(xiàn)，證明MOSC克服了Fast-greedy在處理分區(qū)邊界較弱以及SC在模塊度方面表現(xiàn)較差的缺點。MOSC算法相較于Fast-greedy算法和SC算法，所得分區(qū)方案具有模塊度高、邊界管道數(shù)量少的特點，而漏損控制則需要對區(qū)域內(nèi)所有邊界管道上的閥門、流量計進(jìn)行清晰劃分。因此，MOSC算法所得DMA分區(qū)不僅界限分明，沒有出現(xiàn)狹長型無效分區(qū)和空間位置上的交叉重疊從而有利于水司進(jìn)行分區(qū)的日常管理和維護(hù)，而且較少的邊界管道有利于在漏損控制過程中減少閥門、流量計等設(shè)備的數(shù)量從而節(jié)省分區(qū)成本。本文提出的MOSC進(jìn)行管網(wǎng)分區(qū)，考慮管徑、管長、材質(zhì)、管段數(shù)量等水力拓?fù)涮卣?，后續(xù)可以引入更多諸如節(jié)點壓力、水齡、用戶數(shù)等特征，以進(jìn)一步優(yōu)化分區(qū)結(jié)果。

作者貢獻(xiàn)聲明：

楊之江：提出研究選題；設(shè)計研究方案；論文撰寫、修訂。

周煜岷：調(diào)研整理文獻(xiàn)；實施研究過程；論文撰寫。

扈 震：技術(shù)支持；指導(dǎo)性支持；終審論文。

曾 文：指導(dǎo)性支持；技術(shù)支持。

周 揚：實驗驗證。

李曉麗：數(shù)據(jù)獲取及加工。

馮 麗：實驗驗證。