Nowadays,certain infrastructures,such as water supply system,energy supply system,and transportation system,etc are consisted as the keystone and critical infrastructures of society development. The quality of the normal city life depends on these critical infrastructures. Critical infrastructures are increasing in complexity,because of the successful application of information and communication technologies. The current water supply system is a large and distributed network,and it is expanding rapidly to meet the increasing demands from industry and normal life in the bigger cities. These integrated systems are not only traditional embedded systems but also cyber-physical systems (CPSs). CPSs mainly take into account the interaction between the physical elements in the real world and the computing elements in the cyber space^{[1, 2, 3, 4]}. As described in ^[1],there are three key characteristics of CPSs. Firstly,the CPSs is a system of systems which consists of many subsystems that can stand alone in an individual manner. Secondly,there are novel interactions among control,communication,and computation. Last,the computing element in the cyber world should be tightly coupled with the physical systems in the real world. These three key characteristics bring a lot of challenges. Few of the challenges are robustness,safety and security^{[1, 3]}.

The intrinsic nature of CPSs can be leveraged by exploiting the physical information on location and timing of the system^[1]. This paper focuses on the subsystems' interrelationship such as connectivity and controllability. The subsystems in the CPS can be taken as nodes in a complex network. The communications between subsystems can be taken as edges in a complex network. The CPS can be abstracted as a complex network system from the view of the data-accessing perspective of the subsystems. The paper ^[2] considers vehicular ad hoc networking (VANET) connectivity of platoon-based vehicular cyber-physical systems (VCPSs) where all vehicles drive in platoon-based patterns,which facilitate better traffic performance as well as information services. The number of the subsystems in the paper ^[2] is small and the connectivity condition is simple. In the complex network area,there are lots of results in connectivity and controllability. Capocci et al.^[5] proposes a correlation in the spectral methods to detect community in complex network. Diao et al.^[6] proposes an approach that could create boundaries for district metered areas automatically on the basis of the community structure of water distribution systems. Sheng et al.^[7] improves the Capocci's method by proposing a $d$ dimensional eigenvector space. This paper uses complex network theory to analyze the complex network system modeling the water supply networks,and combine Capocci's method and Sheng's algorithm to detect communities in different states in a complex network system.

As it is well known,the CPSs grand challenges are in lots of areas such as biomedical and healthcare systems,next-generation air transportation systems and smart grid and renewable energy which are all critical areas. The controllability are the keys to these CPSs. For a classical CPS,it can be abstracted as a complex network system. As is known to all,it is hard to find a suitable way to design controllers for a complex network system^{[8, 9]}. In the year 2011,Liu et al.^[10] developed analytical tools to study the controllability of an arbitrary complex directed network by identifying the set of driver nodes with time-dependent control that can guide the system's entire dynamics. Liu also found that the number of driver nodes is determined mainly by the network's degree distribution. Yuan et al.^[11] proposes a framework of exact controllability as an alternative to the structural controllability framework,which offers a more general tool to treat the controllability of complex networks with arbitrary structures and link weights. In this paper we take a water supply network as an undirected and unweighted complex network and find out driver nodes by Yuan's method.

The remainder of this paper is organized as follows. Section II analyzes a cyber-physical system structure for the water supply networks and proposes a complex network model. Section III introduces a spectral analysis method to detect the communities in the complex network,then use this method to detect the water supply networks. Section IV discusses the structural controllability of the water supply networks and design controllers for a complex network system. Section V discusses the limitation and improvement of this research.

The area of the Shanghai water supply is more than 190 square kilometres. The length of the pipe network is 2 848 kilometres,and the pipe diameter is between 500 mm and 2 000 mm. Main pipes are directly connected to the water distribution system. The water of the Shanghai city is supplied by four water supply companies which are South City Water Supply Company,North City Water Supply Company,Pudong Veolia Water Supply Company and Minhang Water Supply Company. These four companies contain 14 water plants and 51 boostering pumps which can supply 6 million tons water per-day for the whole city. The real water supply network is very complicated as in Fig. 1,which is the Shanghai water supply system made up with pipes having diameter over 800 mm. In Fig. 1,dots represent the main pumps and water plants in the water supply system.

Fig. 1

	Download: JPG larger image
Fig. 1. The geographic information system of Shanghai water supply networks.

The city water supply networks contain water plants,pump stations,reservoirs and pipes shown in Fig. 2. In the water plant,the raw water undergoes a process of pretreatment,dosing,precipitation,filtration and advanced treatment,then the pure water is stored in the reservoir of the water plants. The high power pump stations transport the pure water to the water supply network. In the network,there are lots of pump stations which can guarantee the pipe pressure at a suitable level which can supply water to every customer,considering the loss of water head.

Fig. 2

	Download: JPG larger image
Fig. 2. Distributed network of water supply networks.

Supervisory control and data acquisition (SCADA) systems are widely used in the modern water supply system. Fig. 3 shows the interactions between distributed areas and SCADA systems. Based on the information from the SCADA systems,we can get the node model and the predictive instantaneous demand,then the optimal setpoints can be sent to the distributed areas via SCADA systems.

Fig. 3

	Download: JPG larger image
Fig. 3. SCADA information structure of water supply networks.

A water supply system is a critical infrastructure which can be modeled as a complex network of pipelines CPS. The distribution center contains an embedded computer that coordinates directly with physical components such as actuators via actuating signals to maintain control over the pipeline shown in Fig. 4. An embedded computer comprises long-term control and automation control subsystems. The long-term control is used to communicate with neighboring distribution areas and coordinate the distributed setpoints of water. There are $N$ distributed areas in the water supply network.

Fig. 4

	Download: JPG larger image
Fig. 4. Interactions with in pipelines network with cooperating distributed areas.

In the complex network theory,we use lots of symbols from the graph theory to describe a complex network. Let $G=$ $(V$,$E)$ be an undirected graph with $n$ nodes and $m$ undirected edges.

$N=\{1,2,\ldots,n\}$ denotes the sets of all vertices and $L=$ $\{l^{1},l^{2},\ldots,l^{m}\}$ denotes the sets of all edges. For an edge $l$ connecting node $i$ and node $j$,we define a column vector $a_{l}$ $\in$ ${\bf R}^{n}$,where $a_{l_{i}}=1$,$a_{l_{j}}=1$,and other elements are zeros. We can get an adjacency matrix $A$ which is used to illustrate the connection of a graph. Generally,there are lots of nodes or subsystems in the CPS,we take those nodes or subsystems as nodes in a complex network.

According to these definitions,we can get a complex network system from a water supply system which is a part of water supply networks in the Shanghai city shown in Fig. 5. There are $198$ nodes and $298$ edges in Fig. 2. The nodes which have the same color has the same degree. Actually,in the real water supply system,most links are bilateral except a small number of inlet branches. In order to simplify the network,all bilateral links are taken as unilateral shown in Fig. 5,which is the ForceAtlas2 layout graph^[12]. Each node has a unique ID number.

Fig. 5

	Download: JPG larger image
Fig. 5. The complex network of pipeline CPSs.

In order to get more topological information,we need the Laplacian matrix of the complex network. Laplacian matrix $L$ is defined as follows:

where $A$ is the adjacency matrix of the topology which can be written as

$A=\begin{pmatrix} 0 & 1 & \ldots &0 \\ 0 & 0 & \ldots &0\\ \vdots & \vdots &\ddots &\vdots\\ 0 & 0 & \ldots & 0 \end{pmatrix},$

$D$ is the diagonal matrix which can be written as

$D=\begin{pmatrix} d_{1} & 0 & \ldots &0 \\ 0 & d_{2}& \ldots &0\\ \vdots & \vdots &\ddots &\vdots\\ 0 & 0 & \ldots & d_{n} \end{pmatrix},$

$d_{i}$ is the degree of the node $i$ which means the connection from node $i$ to other nodes.

The spectrum of Laplacian matrix contains much topological information of the complex network. We define the eigenvalues of the Laplacian matrix as $\lambda(L)={\lambda_{1},\lambda_{2},\ldots,\lambda_{n}}$. Without loss the generality,we assume $\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}\leq\cdots$ $\leq$ $\lambda_{n}$. Then we can get some properties of the Laplacian matrix^[7].

1) $L$ has only real eigenvalues;

2) $\lambda_{1}=0$ and $\lambda_{2}\geq0$ if and only if the graph is full connected;

3) $\lambda_{1}=0$ and its corresponding eigenvector is constant (all components of this vector are the same). The multiplicity of zero eigenvalues is determined by the number of splitting components of the graph.

In the complex network like Fig. 2,we can get $\lambda_{1}=0$ and $\lambda_{2}=0.0127$,other eigenvalues are real. According to the properties of the Laplacian matrix,the graph is full connected,and has no isolation part.

The traditional spectral bisection method is based on that components in the eigenvectors corresponding nonvanishing eigenvalues have approximately equal value corresponding nodes in the same community. It is very useful to have a clear partition in the network. As long as the partition is sufficiently sharp,the components in the eigenvectors are step-like.

However,in the real large complex network systems,there is no clear partitioning and the precise value of the eigenvector components is of little use. In the pipelines CPS,the typical eigenvector profile is not step-like^[5]. However,such characteristic patterns are much clear in $d$ $(d\geq2)$ dimensional eigenvector space,which is consisted of $d$ eigenvectors of the first $d$ nonvanishing eigenvalues^[7]. Then we can get the community detection algorithm as follows:

Step 1. Use the data of the pipelines CPS network,and transfer the real network to the complex network.

Step 2. Get the adjacency matrix $A$ and the Laplacian matrix $L$.

Step 3. Get the eigenvalues of the Laplacian matrix $L$: $\lambda(L)$ $=$ ${\lambda_{1},\lambda_{2},\ldots,\lambda_{n}}$.

Step 4. If the multiplicity of vanishing eigenvalues of the Laplacian matrix $L$ is 1,then there is no isolated community in the network. Get the first 2 dimensional eigenvector space,and identify the communities in the network. Then the algorithm is done. If the multiplicity of vanishing eigenvalues is not 1,then there is isolated community. Identify communities,and find potential communities. Go to the Step 2.

Remark 1. If the graph of the network is not full connected or there are some isolate nodes,the multiplicity of vanishing eigenvalues of the matrix $L$ is bigger than 1 via the properties of the Laplacian matrix,we should choose the eigenvector space of the first 2 nonvanishing eigenvalues. All isolate nodes are at the $(0,0)$ in the eigenvector space.

We take the pipelines CPS of part of water supply networks in the Shanghai city as an example. We assume two states of the pipelines CPS: the original state,and state 2 (edge $l_{177,145}$ and edge $l_{127,112}$ burst in an unexpected event. That means communications between distribution area $177$ and distribution area $145$,distribution area $127$ and distribution area $112$ have got broken). The proposed algorithm is applied to detect isolated communities.

We use the software "Gephi" and "Pajek" to get the adjacency matrix $A$ and the Laplacian matrix $L$,which have $198$ $\times$ $198$ dimension. Then,we use Matlab to get the eigenvalues and the eigenvectors of the Laplacian matrix $L$. According to the algorithm,$\lambda_{1}=0$ and $\lambda_{2}=0.0127$,and the multiplicity of vanishing eigenvalues of the Laplacian matrix $L$ is 1. Then,we get the 2 dimensional eigenvector space made up with two eigenvectors according to the first 2 nonvanishing eigenvalues shown in Fig. 6.

Fig. 6

	Download: JPG larger image
Fig. 6. Original state of the pipelines.

In the original state of the pipelines shown in Fig. 6,we can get three areas roughly according to the spectral distribution shown in Table I. There are 80 nodes in Area 1,67 nodes in Area 2,and 51 nodes in Area 3. All the three areas are connected.

Table I

Table I SPECTRAL INFORMATION OF ORIGINAL STATE Graph partition Nodes Area 1 108 119 122 123 120 121 126 125 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 216 215 217 218 219 220 221 338 340 369 370 371 1 951 2 261 2 411 Area 2 92 95 98 155 156 157 158 160 161 162 285 163 164 165 166 167 168 286 169 170 171 172 173 174 175 176 177 222 223 224 225 226 227 228 229 230 231 232 233 234 235 237 236 238 239 240 241 242 243 244 245 246 247 248 427 249 250 251 429 262 287 383 401 406 418 425 1 571 Area 3 18 59 60 74 75 76 77 78 88 90 94 99 100 101 102 103 104 105 106 107 109 110 111 112 113 114 115 116 118 117 147 148 149 150 151 152 153 154 159 265 254 255 256 253 273 1 281 1 301 1 521 1 941 1 791 2 531

Table I SPECTRAL INFORMATION OF ORIGINAL STATE

In the state 2,$l_{177,145}$ and $l_{127,112}$ burst in an unexpected event^[13]. By the same method,we can get the spectral information shown in Fig. 6. From the eigenvalues of the Laplacian matrix $L$,we can see the multiplicity of vanishing eigenvalues of the Laplacian matrix $L$ is 2 so that there is an isolated community,which are the spot (0,0) in Fig. 7. There are 80 nodes in the new isolated community. The details about the new Area 1 are shown in Table II.

Fig. 7

	Download: JPG larger image
Fig. 7. State 2 of the pipelines.

Table II

Table II SPECTRAL INFORMATION OF STATE 2 Graph partition Nodes Area 1 108 119 120 123 122 121 126 125 127 128 129 130 131 132 133 134 135 136 137 138 139 143 144 145 146 140 141 142 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 216 218 219 215 217 220 221 338 340 369 370 371 2 261 2 411 1 951

Table II SPECTRAL INFORMATION OF STATE 2

The spectral analysis can provide a deep analysis of the pipelines including the structural connectivity and the vulnerability,and it is also useful to devise countermeasures when unexpected events happen. The spectral analysis can also be suitable for other CPSs.

Consider a network of $N$ nodes described by the following set of ordinary differential equations:

where the vector ${\pmb x}$ stands for the states of nodes,$A \in {\bf R}^{N \times N}$ stands for adjacent matrix of the network,in which $a_{ij}$ represents the weight of a directed link from the node $i$ to $j$ (for undirected unweighted network,$a_{ij}=a_{ji}=1$). ${\pmb u}$ is the controller. $B$ is control matrix. The standard way to address the controllability problem is to find a suitable control matrix $B$ of a minimum number of driver nodes so as to satisfy the stability condition^{[10, 11]}.

Yuan et al.^[11] developed a general theory to calculate the minimum number $N_{D}$ of independent drivers or controllers based on the Popov-Belevitch-Hautus (PBH) rank condition ($N_{D} =\min \{{\rm rank}(B)\}$). For arbitrary matrix $A$,the minimum number $N_{D}$ is determined by the maximum geometric multiplicity $\mu(\lambda_{i})$ of the eigenvalue $\lambda_{i}$ of $A$. From the idea in the paper ^[11],we can get the algorithm as follows:

Step 1. Get the adjacency matrix $A$ and eigenvalues of the adjacency matrix.

Step 2. Get the $A-\lambda ^{i}\times I_{N}$,$\lambda ^{i}$ is the eigenvalue which has the algebraic multiplicity bigger than one. Convert the $A-\lambda ^{i}$ $\times$ $I_{N}$ to the column canonical form by Gaussian elimination method. Find the maximum geometric multiplicity $\mu(\lambda^{M})$.

Step 3. Find the minimum driver node or controllers by linearly dependent rows in the $A-\lambda ^{M}\times I_{N}$.

Remark 2. By the algorithm,we can get the minimum number of the driver nodes for a complex network and the driver nodes set which contains all possible driver nodes. Without loss of generality,we get the driver nodes group as one of the groups in the driver nodes set in the sequel.

To count the algebraic multiplicity,we set a small threshold $10^{-8}$. If the absolute difference between two eigenvalues is less than threshold,the two are regarded as identical. We use the original state of part of Shanghai pipelines system as the control plant. We can get eigenvalues of the adjacency matrix $A$.

There are two eigenvalues $1$ and $-1$ which have the algebraic multiplicity bigger than 1. The algebraic multiplicity of the eigenvalue $1$ is two,and the other is four. By the algorithm mentioned,the geometric multiplicity of the eigenvalue $1$ is two,the geometric multiplicity of the eigenvalue $-1$ is four shown in Fig. 8 (the arrow points out four nodes). So we can get that

Fig. 8

	Download: JPG larger image
Fig. 8. Original eigenvalues of the pipelines.

The maximum geometric multiplicity $\mu(\lambda^{M})$ is four. So we can get the column canonical form of matrix $A-\lambda ^{M}\times I_{N}$ and find linear dependent rows: $149$,$185$,$194$,$195$. The number $149$ is the node $149$ in the pipelines system,others are,$251$,$215$,$196$ as shown in Fig. 9.

Fig. 9

	Download: JPG larger image
Fig. 9. Driver nodes in the complex network of the pipelines.

In the original state,the node $40$,$149$ and $251$ are in Area 3,the node $215$ is in Area 2,and the node $196$ is in Area 1. These four nodes are minimum drivers nodes. The minimum driver nodes set is the same as in the original state when we use the algorithm to analyze the state 2 in which there is an isolated community while the edge $l_{177,145}$ and the edge $l_{127,112}$ are out of order.

In the state 2,there are 80 nodes in the isolated community as shown in Table II. we use the algorithm to analyze the 80 nodes,and get the driver nodes $196$,$215$ which are the same as two driver nodes in the original state with 198 nodes (the number of the driver nodes is the same and the driver nodes are not the same,we pick the same driver nodes from the driver nodes set).

In order to testify whether we can control all of the 80 nodes with the driver node $196$ and $215$,we choose the system which has the discrete state space $A_{80\times 80}$ just as the same as the structural matrix formed by the topology in Table II.

The control matrix $B_{80\times 2}$ is constructed by the method mentioned in the supplementary material of the Yuan et al.^[11]. Using the nonsingular transformation

The system can be rewritten in the following Jordan form:

Based on the method mentioned in the supplementary material of the Yuan et al.^[11],we can get the simplest $Q$ and construct $Q$ by assigning value one to the row of $Q$ corresponding to the last row of every Jordan sub-block of $J( \lambda_{i})$. Then,we can get the complete structure information of $B$ by the following

For a node in a CPS network of water supply system,the node dynamic process system can be described as follows:

where ${\pmb x}_{i}$ is the node state,${\pmb y}_{i}$ is the node output,and $f_{i}({\pmb x})$ is a linear or nonlinear function. According to the network,a node's output may be the neighbor nodes' input. The dynamic process system for a node in the CPS network can be written:

where $c>0$ is the coupling strength between nodes,$l_{ij}$ is the element of the Laplacian matrix $L$ mentioned above.

Without loss of generality,we choose $f_{i}({\pmb x})={\pmb x}_{i}$,$c=1$,$H({\pmb x}_{i})$ $=$ $1$ to show the structural controllability of the CPS network here. Then,we can design controllers to control all $80$ nodes according to the system parameters $A$ and $B$. As we know,there are two driver nodes in the $80$ nodes,we just need to design a controller to control two nodes. The number of the controllers are causal,one can choose a single controller or any number of controllers. In order to show the result is feasible,we design two PID controllers for the system shown in the Fig. 10. There are two closed loops in order to control two nodes' state respectively.

Fig. 10

	Download: JPG larger image
Fig. 10. The control block diagram with two driver nodes.

Based on the state matrix $A$,each node is an integrator. The connectivity relationship between nodes are also described in the state matrix $A$. The driver nodes $196$ and $215$ are nodes $36$ and $37$ in Fig. 10 which are controlled by two PID controllers. We regulate some PID parameters to get appropriate performance as shown in Fig. 11. Fig. 12 shows that non-driver nodes can be stable while the two diver nodes are stable.

Fig. 11

	Download: JPG larger image
Fig. 11. Simulation results of driver nodes with two PID controllers.

Fig. 12

	Download: JPG larger image
Fig. 12. Simulation results with two PID controllers.

Remark 3. According to the algorithm,we can get the minimum number of driver nodes in the pipelines CPS of water supply networks and specific driver nodes set. Choosing appropriate control inputs can guarantee the structural controllability of the CPS network. If the system $A$ is in canonical Jordan form,we can see the difference between the driver nodes and normal nodes obviously. The result of the driver nodes is useful for engineers to design the controllers and choose the control inputs in the pipelines CPS of water supply networks or other CPSs networks.

In this paper,we use the complex network and graph theory to analyze the structural properties of the pipelines CPS of water supply networks. We build a complex network model for the pipelines CPS of water supply networks,and use some metrics mentioned above to investigate the structural properties of the pipelines CPS,which can be used to guide the construction of the of water supply networks and improve the robustness of water supply networks. The algorithms mentioned in the paper are also useful for complex networks of other CPSs.