Node Importance Evaluation of Long-distance Water Delivery System Based on Complex Networks

Yuan-yuan YANG; Hao-yu ZHU; Yun-bin DU; Gang LI

China Rural Water and Hydropower ›› 2022 ›› (2) : 179-183.

Author information +

History +

Abstract

Identifying important nodes in water delivery system plays a significant role in its protection resources distribution and safe operation. A topology network of long-distance water delivery system is constructed by using complex network theory， then a node importance evaluation is achieved with the consideration of local centrality， closeness centrality， betweenness centrality and network centrality from local， global and location aspects. Then evolution process of water delivery network comprehensive efficiency is calculated by removing nodes following their degree of importance. The results show that the nodes located in the middle of the water delivery system are more important， the water delivery network comprehensive efficiency decreased from 0.12 to 0.02 while 34% important nodes were destroyed， which indicates that a few important nodes failed can cause the rapidly collapse of the water delivery system.

Key words

complex network / long-distance water delivery system / node importance / network comprehensive efficiency

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

Yuan-yuan YANG , Hao-yu ZHU , Yun-bin DU , Gang LI. Node Importance Evaluation of Long-distance Water Delivery System Based on Complex Networks. China Rural Water and Hydropower. 2022, 0(2): 179-183

建设长距离输水系统是解决区域水资源紧缺问题的重要工程措施^［1，2］，而闸阀、泵站等控配水建筑物作为长距离输水系统的重要组成部分^［3］，对其开展重要性评估，根据其重要程度进行相应的水力设计和防护资源分配，可保障长距离输水系统的安全可靠运行，有效发挥其输水效益。目前的相关研究主要是针对流经控配水建筑物的水流特性对其破坏程度的大小来确定其重要性，梁圣辰等^［4］模拟了粤东三江引水工程泵站的水锤效应，提出了针对重要泵站的联合防护方案；张焱炜^［5］以贵州某管道输水工程为背景，进行了输水系统中泵站水击防护方案的设计和优化。然而，由输水管线和控配水建筑物构成的长距离输水系统同时还具有复杂的网络拓扑结构^［6］，目前从复杂网络的角度进行控配水建筑物重要性评价的研究还较为匮乏。因此，本文以输水管线为边，控配水建筑物为节点，构建长距离输水系统拓扑网络，从节点的局部属性、全局属性和位置属性三个方面筛选指标，进行节点重要性的综合评估，可避免复杂的水力计算，并利用节点移除后的输水网络综合效率验证评估结果，为长距离输水系统的重要节点识别和监测保护提供理论指导。

1 节点重要性评估方法

1.1 输水系统拓扑网络构建

长距离输水系统的输水线路可能横跨几个甚至十几个省市，输水线路长度可达数百公里，而输水系统往往受到功能需求以及环境条件的制约，需要设置数量众多的输水建筑物（渠道、管道等）和控配水建筑物（泵站、闸阀等），形成连通发达的网络系统^［7］。因此，运用复杂网络理论，将长距离输水系统输水设施抽象为边，控配水设施抽象为节点，以水流流向为方向，构建长距离输水网络拓扑结构图，记为

G :

G = 〈V, E, A〉

（1）

式中：

V = \{v_{i} | i \in I = \{1,2, \dots, N\}\}

为网络节点集合；

E = \{e_{i j} = (v_{i}, v_{j}) | i, j \in I\} \subseteq V \times V

为节点之间的边集合；

A = {[a_{i j}]}_{n \times n}

为输水网络邻接矩阵。

a_{i j} = \{\begin{matrix} 1 i 指 向 j \\ 0 j 指 向 i \end{matrix}

（2）

1.2 节点重要度指标确定

由于输水节点所处的位置以及与其连接的输水设施数量不同，使得节点的重要程度存在一定的差异^［8］，可从输水网络中节点与邻居节点的联系（局部属性）、与全网节点间的联系（全局属性）以及节点所处的位置（位置属性）3个方面来进行节点重要度指标的选取。

1.2.1 局部属性

输水节点的邻居节点数目可表征该节点与邻居节点建立联系的能力，邻居节点越多，输水节点失效后对输水系统的影响越大，引入节点的度^［9］来表示节点的邻居节点数目：

K_{i} = k_{i}^{i n} + k_{i}^{o u t}

（3）

式中：

K_{i}

为节点的度，表征与该节点连接的上下级节点数量；

k_{i}^{i n} = \sum_{j = 1}^{n} a_{j i}

为节点的入度；

k_{i}^{o u t} = \sum_{j = 1}^{n} a_{i j}

为节点的出度，节点的度越大，与之相连节点越多，节点失效对整个输水网络影响越大。

对于度相同的输水节点，邻居节点间的相互联系程度不同，节点失效后对整个输水网络影响也存在一定的差异，邻居节点联系越紧密，节点失效后水流传输的可替代路径越多，对输水系统的影响越低。因此，引入输水节点的聚类系数^［10］来表示邻居节点间的联系紧密程度，表示为邻居节点间实际相连边数与可能相连边数的比值。

c_{i} = \frac{\{e_{k j} | k, j \in Γ (i)\}}{2 C_{k_{i}}^{2}}

（4）

式中：

c_{i}

为输水节点的聚类系数；

e_{k j}

为节点

v_{i}

与其邻居节点的实际相连边数；

2 C_{k_{i}}^{2}

为节点

v_{i}

邻居节点的可能相连边数，聚类系数取值范围介于0~1，当聚类系数接近1时，表明节点的邻居节点之间联系越紧密，节点重要性越低。

节点的度考虑了节点与相邻节点的联系程度，而聚类系数考虑了节点的邻居节点间联系紧密程度，本研究综合考虑上述两方面对节点局部重要性的影响，定义节点的局部中心性为：

L C (i) = α (1 - C (i)) + (1 - α) K_{i}, α ϵ [0,1]

（5）

式中：

L C_{i}

为输水节点的局部中心性；

α

为重要度影响分配系数，取值为0.5。

1.2.2 全局属性

输水节点与全网中除邻居节点外其他位置节点的平均最短距离越小，则表明该节点与网络中其他节点越接近，水流传输到其他节点越容易，引入节点接近中心性^［11］来表征节点与全网中除邻居节点外其他输水节点的联系程度：

C C (i) = \sum_{j = 1}^{n} \frac{1}{d_{i j}}

（6）

式中：

C C_{i}

为输水节点的接近中心性；

d_{i j}

为节点

v_{i}

与节点

v_{j}

之间的最短路径，若节点

v_{i}

与节点

v_{j}

之间没有路径可达，则

d_{i j} = \infty

。

C C (i)

值越大，表明节点

v_{i}

与网络中其他节点距离越近，联系越紧密，失效后对输水系统影响越大。

1.2.3 位置属性

在输水网络中，一对节点之间通常存在多条最短路径，经过某个节点的最短路径数量越多，则该节点越重要。引入节点的介数中心性^［12］为网络中节点对之间经过某节点的最短路径条数与节点对所有最短路径条数之比：

B C (i) = \sum_{s \neq i \neq t} g_{s t}^{i} / g_{s t}

（7）

式中：

g_{s t}

为节点

v_{s}

到节点

v_{t}

的最短路径数目；

g_{s t}^{i}

为节点

v_{s}

到节点

v_{t}

的

g_{s t}

条路径中经过节点

v_{i}

的最短路径数目，

B C

越大，节点

v_{i}

失效后对输水系统影响越大。

处于网络中不同层级的节点其重要程度存在一定的差异，位于网络边缘的节点重要性相较于处于网络中心的节点其重要程度相对较低，利用K-shell分解方法^［13］递归的移除网络中所有度值小于或等于

k_{m i n}

的节点来逐步确定节点在网络中的层级及其重要性，考虑到节点度指标中出度入度差异，定义度指标影响分配系数

λ

，提出节点交叉度概念：

k_{i}^{} = {(k_{i}^{i n})}^{λ} {(k_{i}^{o u t})}^{1 - λ}

（8）

式中：

k_{i}

为输水节点的交叉度；

λ

取值为0.5，同时考虑出度入度为0时计算的交叉度与实际存在偏差情况，引入一个虚拟的全局节点^［14］，使该节点与网络中全部节点双向连接，则网络中所有节点的出度和入度都增加

1

，最终得到改进后的节点交叉度：

k_{i}^{c} = {(k_{i}^{i n} + 1)}^{λ} {(k_{i}^{o u t} + 1)}^{1 - λ}

（9）

设初始网络为

G_{0}

，根据上式，计算网络中所有节点的

k^{c}

值，定义

k^{c}

值最小的节点

K s

值为

K s^{1} = 1

，移除网络中

k^{c}

值最小的节点（集）及与其相连的边得到子图

G_{1}

，更新

G_{1}

中节点的

k^{i n}

和

k^{o u t}

，计算剩余节点

k^{c}

值，

k^{c}

值最小的节点K_s 值为

K_{s}^{2} = K_{s}^{1} + 1

。重复上述步骤直至网络中所有节点都有其对应的K_s 值。

1.3 节点重要度计算

为避免单一指标评价片面性，综合考虑四种指标，通过熵权法^［15］计算各指标权重。熵权法根据各项指标提供的信息熵大小确定权重，可以避免确定权重时的人为主观影响。具体步骤如下：

R_{i j} = x_{i j}^{'} / \sum_{i = 1}^{m} x_{i j}^{'}

（10）

e_{j} = - {(l n m)}^{- 1} \sum_{i = 1}^{m} R_{i j} l n R_{i j}

f（11）

g_{j} = 1 - e_{j}

（12）

w_{j} = (1 - e_{j}) / \sum_{i = 1}^{n} (1 - e_{j}) (i = 1,2, \dots, n)

（13）

式中：

R_{i j}

为计算指标

x_{i j}^{'}

的比重；

e_{j}

为第j项指标的熵值；

g_{j}

为第j项指标的差异性系数，值越大表明相应指标在评价中的重要性越强；

w_{j}

为各指标的权重。

指标权重越大，表示该指标对节点重要度评价时的作用越大，节点重要度表示为各节点重要度指标与其权重之积：

I (i) = \sum_{j = 1}^{p} x_{i j}^{'} \times w_{j}

（14）

式中：

I (i)

为节点的综合重要度，

I (i)

越大，节点

v_{i}

在输水网络中越重要，失效后对输水系统影响越大。

1.4 输水网络综合效率计算

长距离输水网络中节点失效后，输水网络的结构发生变化，使得水流在输水网络中的流动重新分布，本文引入复杂网络抗毁性测度指标网络综合效率^［16］，用来表示节点失效后网络输水功能的破坏程度以及水流在输水网络中流通的难易程度^［17］：

E = \frac{1}{n (n - 1)} \sum_{i \neq j} \frac{1}{d_{i j}}

（15）

式中：

E

为网络综合效率值；n为初始网络输水节点数目。

当输水网络中有输水节点

v_{k}

遭到破坏时，若该节点

v_{k}

不在节点对

v_{i}

和

v_{j}

的路径上，水流从节点

v_{i}

输送到

v_{j}

的最短路径不发生改变；若节点对

v_{i}

和

v_{j}

之间存在多条输水路径，节点

v_{k}

处在节点对

v_{i}

和

v_{j}

的非最短路径上，则节点

v_{k}

失效时，水流仍可以通过节点

v_{i}

和节点

v_{j}

的最短路径进行输送，输水网络综合效率保持不变；当节点

v_{k}

处于节点对

v_{i}

和

v_{j}

之间的路径中的最短路径时，节点

v_{k}

一旦遭到破坏，节点

v_{i}

和

v_{j}

之间的最短路径必然会被其他边取代，使得水流从节点

v_{i}

传输到节点

v_{j}

的距离变长，进一步影响到节点

v_{i}

和

v_{j}

之间的输水效率，使得水网综合效率变低。

2 案例分析

2.1 工程概况

图1表示某长距离输水工程，该工程包括泵站、闸阀等控配水设施以及管道、渠道等输水设施，将控配水设施抽象为节点，输水设施抽象为边，得到输水网络拓扑结构图，共包括67个输水节点和116条输水边，1、4、9、22为水源节点。

Fig.1 The topology of water delivery system

图1 输水系统网络拓扑结构

Full size|PPT slide

2.2 输水节点重要度分析

根据式（3）~（9）计算得到4个节点重要度指标，由于不同的指标计算结果处于不同的量级，经归一化后各指标下节点的重要度排序如图2所示。从图2中可以看出

L C

和

K s

的排序结果呈现为一定的阶梯型分布，同一阶梯上的节点重要性相同，使得部分节点的重要性无法有效区分；

B C

和

C C

的排序结果虽然较为平滑，但根据单一指标的计算结果进行节点的重要性评价存在较大的片面性，需要从不同的角度选取多个节点重要性指标进行综合评价。

Fig.2 Evaluation results of node importance indices

图2 节点重要度指标评价结果

Full size|PPT slide

利用熵权法计算得到

L C

、

B C

、

C C

、

K s

的权重分别为0.247、0.238、0.252、0.263，根据式（14）计算得到各节点重要度

I (i)

，结果如表1所示，重要度较高的节点所处位置如图3所示。结合表1和图3可以看出，重要度排序前10的节点为39、27、43、32、44、45、30、10、19、25，主要位于输水网络的中部位置，在实际的长距离输水工程中应对这些重要输水节点进行重点监测和保护。

Tab.1 Node importance

表1 节点重要度

节点	$I (i)$	节点	$I (i)$	节点	$I (i)$	节点	$I (i)$	节点	$I (i)$	节点	$I (i)$
1	0.202 6	13	0.266 3	25	0.668 4	37	0.558 9	49	0.590 4	61	0.342 3
2	0.253 0	14	0.609 7	26	0.589 5	38	0.617 7	50	0.547 7	62	0.234 5
3	0.304 3	15	0.584 0	27	0.834 9	39	0.926 9	51	0.394 1	63	0.291 7
4	0.196 5	16	0.398 4	28	0.515 2	40	0.602 4	52	0.482 2	64	0.233 6
5	0.423 4	17	0.452 6	29	0.522 9	41	0.632 9	53	0.369 8	65	0.129 7
6	0.437 6	18	0.020 8	30	0.711 0	42	0.630 3	54	0.414 1	66	0.172 2
7	0.377 8	19	0.670 4	31	0.647 6	43	0.799 4	55	0.510 9	67	0.115 3
8	0.407 2	20	0.567 8	32	0.790 4	44	0.778 9	56	0.539 9
9	0.352 8	21	0.590 6	33	0.581 5	45	0.749 6	57	0.566 1
10	0.692 5	22	0.070 5	34	0.599 8	46	0.634 3	58	0.405 0
11	0.598 7	23	0.180 5	35	0.111 1	47	0.533 0	59	0.326 2
12	0.338 8	24	0.663 7	36	0.404 5	48	0.589 9	60	0.455 1

Fig.3 Distribution of important nodes

图3 重要节点分布图

Full size|PPT slide

2.3 输水网络综合效率分析

根据式（15）计算得到输水系统初始网络综合效率值为0.12，再依次按节点重要度顺序移除节点并计算每个节点移除后的输水网络综合效率值［图4（a）］，同时比较了重要度排序前10的节点单独移除后输水网络综合效率值的降低程度［图4（b）］。移除23个输水节点后，输水网络综合效率值从0.12下降到0.02，34%的节点影响了输水网络83%的综合效率值，即少量重要节点失效可导致输水系统的迅速崩溃，同时，按节点重要度顺序单独移除节点时，输水网络综合效率值的降低程度总体上随着节点重要度的降低而降低，表明节点的重要度评价结果总体较为准确，能够有效识别长距离输水系统中的重要节点。

Fig.4 The evolution process of water conveyance comprehensive efficiency when nodes are removed in sequence and degradation degree when important nodes are removed separately

图4 依次移除节点时输水网络综合效率演变过程及单独移除重要节点时水综合效率降低程度

Full size|PPT slide

3 结论

（1）将长距离输水系统控配水建筑物抽象为节点，基于复杂网络理论从局部属性、全局属性和位置属性评估了节点的重要性，提出的综合评估方法可有效识别关键节点，为其针对性监测及防护资源分配提供理论指导。

（2）长距离输水网络中少部分关键节点失效即可对长距离输水系统造成较大的破坏，本案例中34%的节点影响了输水网络83%的输水网络综合效率，同时，位于输水网络中心的节点重要性往往大于边缘节点，应对这些节点进行重点监测和防护。

本研究将输水管线抽象为复杂网络的边时未考虑到输水管线的性质差异（如管道流量大小、有压无压等）对节点的重要性影响，如何区分上述差异并将其引入到输水系统节点重要性评估中来是笔者的下一步研究方向。 □

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	张建云，贺瑞敏，齐晶，等. 关于中国北方水资源问题的再认识［J］. 水科学进展， 2013，24（3）：303-310. 本文引用 [1]

2	周利全，蒋乐英，杨选波，等. 西部长距离引调水工程质量管理与对策研究［J］. 中国农村水利水电， 2021（2）：148-151. 本文引用 [1]

3	裴双保. 长距离输水系统重力流段水锤防护措施研究［J］. 人民黄河， 2021，43（）：122-124. 本文引用 [1] 摘要增刊1

4	梁圣辰，张健，贺蔚，等.长距离输水系统串联多阻抗调压室的水锤防护效果［J］. 河海大学学报（自然科学版）， 2021，49（2）：170-175. 本文引用 [1]

5	张焱炜. 管道输水工程水击防护设计及优化研究［D］. 济南：山东大学， 2020. 本文引用 [1]

6	吴汉美，段国凡，李春娥. 洪涝灾害后城镇景观长距离输水系统水文风险评估［J］. 灾害学， 2021，36（2）：43-46，78. 本文引用 [1]

7	刘忠华，于华，杨方廷，等.不确定条件下的山西省水资源调度规划研究［J］. 水力发电学报， 2016，35（3）：36-46. 本文引用 [1]

8	任晓龙，吕琳媛. 网络重要节点排序方法综述［J］. 科学通报， 2014，59（13）：1 175-1 197. 本文引用 [1]

9	张鑫，陈燕，李桃迎. 基于改进PageRank的多属性水网节点综合评价［J］. 计算机应用研究， 2018，35（12）：3 659-3 663. 本文引用 [1]

10	CHEN D B， GAO H， LU L， et al. Identifying Influential Nodes in Large-Scale Directed Networks： The Role of Clustering［J］. PLOS ONE， 2013，8（10）. 本文引用 [1]

11	FREEMAN L C. Centrality in social networks conceptual clarification［J］. Social Networks， 1978，1（3）：215-239. 本文引用 [1]

12	FREEMAN L C. A set of measures of centrality based on betweenness. ［J］. Sociometry， 1977，40（1）：35-41. 本文引用 [1]

13	KITSAK M， GALLOS L K， HAVLIN S， et al. Identification of influential spreaders in complex networks［J］. Nature Physics， 2010，6（11）：888-893. 本文引用 [1]

14	周立欣，刘臣，霍良安，等. 基于交叉度的有向网络中心节点识别算法研究［J］. 计算机应用研究， 2016，33（11）：3 299-3 302，3 306. 本文引用 [1]

15	FANG R， SHANG R， WANG Y， et al. Identification of vulnerable lines in power grids with wind power integration based on a weighted entropy analysis method［J］. International Journal of Hydrogen Energy， 2017，42（31）：20 269-20 276. 本文引用 [1]

16	黄建华，党延忠. 复杂网络二维抗毁性测度指标及评价算法［J］. 计算机工程， 2011，37（15）：63-65. 本文引用 [1]

17	郑霞忠，汪飞，陈述，等. 序贯攻击下长距离输水网络结构抗毁性演化研究［J］. 灾害学， 2017，32（4）：1-5，10. 本文引用 [1]

PDF(1079 KB)

Accesses

Citation

Detail

Sections

Recommended

Received	Published
2021-08-11	2022-02-15
Issue Date
2022-03-09

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 节点重要性评估方法

1.1 输水系统拓扑网络构建

1.2 节点重要度指标确定

1.2.1 局部属性

1.2.2 全局属性

1.2.3 位置属性

1.3 节点重要度计算

1.4 输水网络综合效率计算

2 案例分析

2.1 工程概况

Fig.1 The topology of water delivery system

2.2 输水节点重要度分析

Fig.2 Evaluation results of node importance indices

Tab.1 Node importance

Fig.3 Distribution of important nodes

2.3 输水网络综合效率分析

Fig.4 The evolution process of water conveyance comprehensive efficiency when nodes are removed in sequence and degradation degree when important nodes are removed separately

3 结论

{{custom_sec.title}}

{{custom_sec.title}}

References

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 节点重要性评估方法

1.1 输水系统拓扑网络构建

1.2 节点重要度指标确定

1.2.1 局部属性

1.2.2 全局属性

1.2.3 位置属性

1.3 节点重要度计算

1.4 输水网络综合效率计算

2 案例分析

2.1 工程概况

Fig.1 The topology of water delivery system

2.2 输水节点重要度分析

Fig.2 Evaluation results of node importance indices

Tab.1 Node importance

Fig.3 Distribution of important nodes

2.3 输水网络综合效率分析

Fig.4 The evolution process of water conveyance comprehensive efficiency when nodes are removed in sequence and degradation degree when important nodes are removed separately

3 结 论

{{custom_sec.title}}

{{custom_sec.title}}

References

3 结论