Of all of the resources that are most important in the running of society water has to be seen as the most important. Water is required by human societies not just to survive but to create a fully functioning modern world with all of its benefits such as large population centres in the form of cities and towns. It is also required for the maintenance of agriculture and industry in the form of water irrigation methods. Because a more advanced society tends to become more urbanized and structured within cities or towns, the method with which the water was distributed had to be constantly improved. So with the use of many modern technologies such as junctions, reservoirs, tanks, pumps and industrial piping the way that water is distributed could be adapted to the needs of the geography or the layout of the given area. When these water supply systems are fully constructed we can see that they will form a network of interconnected pipes, junctions, tanks, pumps and reservoirs. Because of this layout water supply system are seen to form into complex networks which are constantly increasing and being maintained. The complex networks for water supply can be understood by laying it out in the form of nodes and links. With the nodes being the supply points of the water supply network such as the junctions, tanks, pumps and reservoirs. The links within the complex network for water supply systems will be the method of distribution of the system which in the case of water supply systems will be the distribution pipes used to carry the water between nodes in the system.
What is graph theory:
Because of the importance of such complex networks for water supply systems in the functions modern society a method of analysing these networks is required to fully understand the topological and behavioural features of these complex networks. This is aimed at understanding the efficiencies, possible redundancies and robustness of the given networks for water supply systems. This form of analysis can be done using what is known as graph theory. Most complex networks are mapped out in the form of planar graphs where by a graph can be created without any of the edges of the graph crossing each other on a plane unless at a vertex where both are incident [1]. This the case for the complex networks of water supply systems with the edges of the network being the previously stated links or the pipes for water distribution and the nodes being the water supply points of the system.
Graph theory is the use of graphs to show the connectivity of a complex network’s edges and how they are mapped out. Usually complex network graphs are shown in one of either two forms, directed and undirected graphs. A directed graph is the where a direction of the graphs is set by the edges of the graphs are directed to a specific vertex, a vertex in our water supply networks are the specified supply nodes such as the junctions, tanks, pumps and reservoirs. For analysis to be conducted using directed graphs additional data is required such the flow data from the water distribution centres. [2] Since this data is not readily available and would require increased computational processes to conducted proper analysis of the system we would tend to use undirected graphs. Undirected graphs are where the edges of the graphs are omnidirectional. [3] This is stating that we are assuming that in our complex water supply networks that the flow of the water is not restricted to any direction and that it can flow back and forth between any two given nodes.
Why would you use graph theory to analyse water supply systems:
By using the graph theory, we can identify the topological and behavioural features of the network in a cost efficient and in a non-computationally analytical method. The main aim of using graph theory to preform analysis on a network is to understand and improve on the efficiency by which the network will distribute water and how robust it is against network failure. Representing complex networks as graphs allows for the connectivity of the graph to be more easily analysed because a graph will more easily show the interconnectedness of the network and how this affects the rest of the network [4]. Another advantage of mapping complex networks onto graphs is that it allows for analysis to be conducted of the network using heuristic and mathematical models to perform analysis on the benchmarks of the networks and actions can be taken to improve the connectivity of the network and efficiency and the robustness of the network can be increased.
Another use for graph theory is the ability to find the redundancy of the network. The redundancy of a network is when there is an “independent alternative path between source and demand nodes which can be used to satisfy supply requirements during disruption or failure of the main paths”. [5] What this statement is saying is that the redundancy of a given network is dependent on the number of loops and cycles present in the graph of the network.
Graph theory can also be used to gain a measure of the robustness and efficiency of a complex network. In the journal by Jacobs and Goulter was shown in (Jacobs, P., and Goulter, I. C. (1988). “Evaluation of methods for decomposition of water distribution networks for reliability analysis.” Civ. Eng. Syst., 5(2), 58–64.) [6] They explained that networks are least susceptible to failure when arranged in regular graphs in which there is an equal number of links and nodes and that the inverse of this will result increased failures of the network. This was shown to be incorrect in future studies due to the fact there where bridges and articulation points in network graphs. Bridges are links which would result in the disconnection of the network if they were to be removed and articulation points are nodes if that if they are removed along with their corresponding links cause the disconnection of the network. [7] As stated in (Boesch, F. T., Satyanarayana, A., and Suffel, C. L. (2009). “A survey of some network reliability analysis and synthesis results.” Networks, 54(2), 99–107.) [8] That the vulnerability inherent in a network is clearly dependent in its structure. So because of this reasoning it is more effective to perform robustness analysis on the structure of the network. It is to be noted however that this form of analysis is not very precise but because it is not very time or cost draining it helps in understanding of possible failures that could occur due to the structure of the network.
In what way would you conduct graph theory analysis of water supply systems so talk about topological and behavioural features:
Once all of the characteristics of the networks are quantified which we have explained as the connectivity, redundancy, robustness and efficiency of the network. We can identify them from the network graph using topological and behavioural features calculated from mathematical models and other heuristic methods by conducting such assessments using structural models and metrics of the network. When water supply systems are properly mapped onto undirected graphs with all of the distribution methods such as the pipes displayed as links and the nodes representing the water supply centres such as the junctions, tanks, pumps and reservoirs, observations can be taken with respect to the structure of the network where failures which are dependent on the number of cycles, loops and alternative supply paths are discovered. These observations will highlight many features of the given network that show how failure can occur because the structure affects function as stated in (Strogatz, S. H. (2001). “Exploring complex networks.” Nature, 410, 268–276.) [9] This is the most important reason why Graph theory would be used in the analysis of not just water supply systems but many other complex networks. This is because most of the time nearly all modern networks can be shown as planar graphs and in turn as undirected graphs.
How would you gain these topological and behavioural feature through calculation:
To carry out graph theory analysis on complex water supply networks we must first define the features which will allow us to quantify the characteristics of the network. The method which we would identify these metrics is through the use of mathematical models which would allow us to create mathematical expression for any given metric that we require. The main aim of conducting the analysis in this approach is as was stated in (Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems- by A. Yazdani and P. Jeffrey) [10] It is very important that greater attention be assigned on the water supply nodes such as the junctions, tanks, pumps and reservoirs and their connectivity as their disruption or loss of function will cause significant failures in the rest of the spatial network. A spatial network is where the graph of the network is correspondent to the location of the nodes in the network.
The method with which we conduct the analysis of the network will be dependent on which mathematical model chose and how the components of that model will correspond to the network. The mathematical processes and method of modelling the networks into graphs presented hence forth have been explained by (M. E. J. Newman in Networks, an introduction (Oxford University Press, NY, 2010).) [11].
The water supply network will be modelled into the mathematical Graph G = G (N, E)where by the components of the equation represented as N being the set of all graph nodes which can be denoted as n. E is representing the set of graph edges which can be denoted as m. once we have gained the overarching method of modelling our water supply network onto a mathematical graph we can then go onto find and observe our structural measurements of the given network.
Average node degree:
One of the first possible structural measurement we can take is the average node degree of a network. The node degree which in our case we will denote henceforth as < k > is the value of the number of times in which a node is connected to by an edge in a network. In a directed network there would be number for the edges going in and out of a node known as the in-degree and out-degree so that total node degree of the network will be the sum of these two values. But since we are using an undirected graph for our network we will not be carrying out this method. When calculating the average degree, we must use the equation
< k > =2mnwhere m is the number edges and n is the number of nodes in the graph. By finding the average node degree we can observe how sparse a network is and how this will affect the configuration of the network.
Clustering coefficient:
The clustering coefficient of a network is a method of conducting analysis to determine the redundancy of a network. This structural measurement of a network is also known as it’s transitivity which we will hence forth denote as c. We know that the redundancy of a network is dependent on the number of loops present in a network. So for this reason the clustering coefficient will attempt to determine the density of triangular loops present in the network since transitive triangles are a form redundancy analysis. We can calculate the clustering coefficient of the network using the equation
c=3N∆ N3. In this expression
N∆is the number of triangles present in the network and
N3is the number of connected network triples in the network. Due to the fact that cluster coefficient does not take into account for non-triangular loops it is not a very accurate method when attempting to find the overall redundancy of the network.
Meshed-ness coefficient:
The meshed-ness coefficient is a structural measurement which is used as an improvement on the clustering coefficient when the redundancy of the network. This is done because the meshed-ness coefficient unlike the clustering coefficient can analyse both the number of loops and cycles in the network and is not restricted to just triangular loops in the network. Meshed-ness coefficient which we will denote as rmcan be calculated using the equation
rm=f2n-5where f is the number of independent loops present in the network where f = m – n + 1 for single source networks and f = m – n multiple source networks which is the case for water supply networks.
Link density:
The structural measurement as the link density of the network is when the total number of links is taken as a fraction of the maximum possible links possible in the network. The link density of the network which we will denote as q will be calculated using the equation
q=2mnn-1. The aim of using the link density as a structural measurement is that will allow for the sparseness or in turn the denseness of the network in terms of its connectivity. This form of analysis us only possible for undirected graph since in a directed graph there will be no loops present. [12] When the analysis is conducted a low link density value means that the network present is sparse in nature. Meaning that there is a low number of links present when it is compared to the maximum number of which would be possible.
Link per node ratio:
The link per node ratio is a form structural analysis where we can observe how the given network deviates from usual graphs with mesh like structures. To gain the link per node ratio which we will denote as e will require the use of the equation
e=mnwhere m is the number of edges present in the network and n is the number of nodes in the network. as stated in (Complex network analysis of water distribution systems by Alireza Yazdani and Paul Jeffrey[2]-2011). “The value for the link per node ratio will range between 1 and 2 with any value of 1 representing tree like planar graphs and the value of 2 representing two dimensional regular lattice” [13]. The reason for using this metric is that we know that distribution possibilities of the network is greatly increased when the network has a more grid like structure. We see that the grid like structure is greater when the value for the link per node ratio is closer to 2.
Average path length:
In a connected graph all nodes are connected and the distance between these nodes is shown as a distance of 1. So with that understood the average path length is the shortest distance from one source node to all other nodes in the network. the equation used to calculate the average path length is
l=1n(n-1)∑(i≠j)dijwhere
dijis the minimum number of edges which will be traversed between two specified nodes which in our case are denoted as nodes i and j. The average path length of a network is a useful metric of the efficiency a network. [14]
Between-ness Centrality:
One of the methods with which the robustness of a network is determined is to use what is known as the between-ness centrality. The between-ness centrality is the value of the centrality of a network when analysed by its shortest paths. The reason that this is useful is because if one of the nodes in a network has a high between-ness centrality it means that it will have a greater effect on large parts of the network since it requires short path lengths to the other nodes in the network. So even though increased between-ness centrality will have some benefits where for example if the node with the highest between-ness centrality was to be a supply node in a water supply network allowing for increased efficiency in the distribution as there are shorter paths to be crossed, it will leave the system vulnerable to failures as the failure due to greater centralisation. The equation that is used to find the between-ness centrality is
CBi=∑j<kgjk(i)/gjkwith gjk being the number of geodesic paths that are connecting j and k, and gjk(i) being the number of geodisc paths that node i is on. This theoretical statement for the between-ness centrality is stated by L C. Freeman in “Sociometry” in 1977. [15]
Closeness centrality:
Closeness centrality is another method of analysing the robustness of a network where by the average of the shortest path between a link is compared against all other links in the network and the value of the closeness centrality being the sum of those two values. Like the between-ness centrality the closeness centrality will show the how close a given node is to all other nodes. Also like the between-ness centrality the increase of the closeness centrality will have the same benefits but will also increase the vulnerability of the network to suffer failure due to increase in centrality. The equation that is used for the closeness centrality is
CCi=∑j=1Ndi,j-1.This was stated by Yannick Rochat in “Closeness Centrality Extended To Unconnected Graphs : The Harmonic Centrality Index” 2009.[16]
Methodology:
The method with which the water supply networks will be analysed to determine their network structure will be through the use of the computer software known as Gephi which was developed by the University of Technology of Compiegne, France in 2008[1]. The Gephi computer program allows for the visualization in the form of graphs for the connectivity of a network and in turn to find the structural metrics of the network of the topological and behavioural features of the network allowing us to quantify the network characteristics of the given spatial network generated from the water supply systems. The reason that we will use this program to conduct our analysis is because it will allow us to find our needed metrics for determining how the network characteristics such as the redundancy and connectivity is dependent on the structure of the network.
It is known that water supply systems can be mapped onto network graphs through the use of the mathematical graph model G = G ( N, E) this will allow us to represent our water supply network with the help of the analytical software tool Gephi.
Once all of the relevant water supply networks are plotted onto graphs we can ascertain the structural characteristics of the network such as the number of nodes n and the number of edges present in the network. By gaining these values we can carry out multiple other forms of analysis as most of the methods by which the structure of the network is observed require the number of nodes and the number edges of the network for the calculation to be calculated.
Analysis of the Connectivity of the Networks:
- Node Degree: There are multiple topological features which can be observed from the network graph but the one of the most of the important is the node degree of the network. The equation for calculating the average node degree of the network is< k > =2mn. Since we know the average node degree of the network we can go onto calculate the node degree distribution for the given water supply systems by comparing the percentage of nodes with a given nodal degree. By conducting this form of analysis we can observe the connectivity of the given networks and we can take steps to improve the connectivity between all the nodes present in the water supply network. This form of connectivity analysis was presented by M. E. J. Newman in “Networks, an introduction” 2010. [2]
- Link Per Node Ratio: Since it was determined that the connectivity of a network is dependent on the connectivity of the network we can use the metric of the link per node ratio which will show the ratio of links connecting to a node. Using the equatione=mnwe can analyse how the compare the link per node ratio against the number of nodes present in the network will allow us to determine the robustness of the given water supply network. The link per node ratio will also allow us to determine the structure of the network and whether it is more grid like meaning that it is more efficient in its distribution. The link per node ratio should range between 1 and 2.
Analysis of the Redundancy of the Networks:
- Clustering Coefficient: Using the methods presented in Wassermann Faust in “Social network analysis: Methods and applications” 1994[3] we can ascertain the redundancy of the water supply networks which will require us to find the number of loops present in the network. For this reason, we will calculate the clustering coefficient as it will allow us to find the total number of triangles present in the network against the number of network triples in the network. when we have gained the clustering coefficient of the network we can compare it against the node degree so that we may observe how the connectivity will affect the redundancy of the network. The equation we will use for determining the clustering coefficient of the network isc=3N∆ N3.
- Meshed-ness Coefficient: We can also determine the redundancy of the network by finding the meshed-ness coefficient of the network which is the value of the maximum number of independent loops present in the network against the total number of independent loops in the network. by using the equationrm=f2n-5where f is the number of independent loops found in the network. There be methods of deriving f which will be dependent on whether the network is single or multiple sourced. In our case we will be using multiple source networks f = m – n. We will use the meshed-ness as a comparison with the node degree of the network so that we can determine how the connectivity and structure of the network will affect the redundancy of the network. This method of the analysis was presented in “Topological patterns in street networks of self-organized urban settlements” by J. Buhl, 2006. [4]
- Link Density: The next step for analysing the redundancy of the network will be determining the link per node ratio of the network which allow us to determine the structure of the network and showing us the sparseness of the network. The method with which we will find the link density of the network will be done by using the equationq=2mnn-1.
Analysis of the Robustness of the Networks:
- Average Path Length: The next step that is take is to find the average path length of the network which is done by using the equationl=1n(n-1)∑(i≠j)dijthis equation is just defining the average shortest path length within the network. By comparing the path length against the size of the network we can understand how this will affect we can observe the efficiency of the network since the path length will show that the connectivity and size will determine how reliable a network will be.
- Between-ness Centrality: The robustness of the network will also be determined by analysing the centrality of the network one method of which is the between-ness centrality which will aim to find the number of shortest paths of a network and help to determine how centralised the network is around a node or a group of nodes, thus showing how susceptible the network will be to failures if the central nodal structure was disrupted. This is done by conducting the following equationCBi=∑j<kgjk(i)/gjk.
- Closeness Centrality: Just like the between-ness centrality the closeness centrality will hope to determine the centrality of the network to understand how this might lead to increased possibilities of failure within the network. The closeness centrality will aim to find the sum of the average of the shortest path between a link which is compared against all other links in the network. The network is determined to be more robust when the centrality of the network is lower thus reducing the likelihood of failure due to the fact that a central node will not have such a large effect on the rest of the network. the method with which the closeness centrality is determined is through the use of the equationCCi=∑j=1Ndi,j-1
Once all of the water supply networks been mapped onto graphs using the mathematical model G = G (N, E) where N was defined as the set of all graph nodes which can be denoted as n and E is the set of graph edges which can be denoted as m. Mapping the Network onto this mathematical model will allow us to gain the number of nodes and the number of edges that are within each particular network. Once the number of number of nodes and the number edges connecting to each node is know we can calculate the average node degree. The average node degree of each network is the average of all the node degrees within each network. It is seen that even though the number of nodes and edges present in each network of the water supply systems analysed increases with each network analysed the average node degree tends to stay the same throughout the analysis of the networks. When analysing the average node degree of the network we can calculate the theoretical maximum for the average node degree of the network by using the inequality
< k > =2mn≤2(3n-6)n[1] which is the case for all planar graphs. This will show us that the average node degree will have a theoretical maximum of six. The values of that are gained for the actual average node degree of the networks are much smaller than the stated theoretical maximum.
The link per node ratio of the network as can be seen from the results for each analysis of the network apart from the small sized networks does not increase or decrease dramatically with the values falling around 1.2, this is conformation that the average node degree was conducted with as much accuracy as possible. The link per node ratio will always fall between 1 and 2 with the values closer to 1 being more tree like and values closer to 2 being more regular and grid like. The link per node ratio will for the analysed networks shows that the structure of the network is not that grid like as it falls closer 1 meaning that it will have a more tree like structure.
The link density of the network is a measure of the connectivity of the network which shows the density of the links present in the given networks. The analysed networks show a negative correlation between the size of the network and the relative link density with the link density starting from 0.021355077 for the smallest network and decreasing down to 0.002578771 for the largest water supply network.
The node degree distribution is the analysis of the percentage of nodes with a certain nodal degree. The range for the node degree of all the networks is between 1 and 5. With the networks HG-100-1-1-1, HG-200-1-1-1 and HG-500-1-2-5 having a maximum node degree of 4 and the other remaining network have a maximum node degree of 5. For all of the networks the highest percentage of nodes with degree equal k seem to be at node degree 2 with the highest value being around 49% and the lowest being at around 35%. From the graph it is observed that the lowest percentage distribution of nodal degree seems to be at the node degree of 5. There does note seen to be any correlation between the number of nodes and edges of the network and its general connectivity in the form of node degree distribution. Since the structure of the network is quite similar for all of the networks with regards to the link per node ratio due to the fact that link per node ratio of all the analysed network fall close to the value of 1 it is observed that the all networks are distributed in the same manner where the highest and lowest and degree distributions are the same for all of the networks. The connectivity of the network is an important quantifiable characteristic of the network as it allows for the determining the best to optimise the distributional abilities of the given water supply networks. So for the this stated goal that if the interconnectedness of the network is increased the distribution to all of the nodes network will be optimised. The connectivity of the network is dependent on the number of links which in the case of water supply networks will be in the form of the number of distribution pipes connecting to each node in the network. It is important that the connectivity of the network is maintained at its most optimal position so that the water distribution of all the nodes is secured.
The aim of analysing the redundancy of the given water supply networks is to determine whether in the case of failures occurring that there are other paths for the distribution to continue across the network. The method with which these paths can be analysed is by understanding the number of loops which are present in the network as these loops will act as a method of continuing the distributional ability of the water supply network. In short the redundancy of the water supply network will be dependent on the number of loops in the network. The analytical metric for the number of loops occurring in a complex network can be the clustering coefficient and the meshed-ness coefficient. As can be seen from the results of the analysis for all of the water supply networks the clustering coefficient the results range from 0.04 up to 0.16 with the highest value of clustering coefficient occurring at HG-500-1-2-5 and the lowest occurring at network HG-100-1-1-1. As for the meshed-ness coefficient for the networks it is observed that the values range from 0.040201 up to 0.150868 with the highest value occurring for the network HG-1000-2-2-5 and the lowest occurring at the network HG-100-1-1-1. A method with which can be used to compare the networks and their respective redundancy is to compare the number of links of the water supply networks. The reason that there is a comparison of the redundancy against the number of links for each network is because it will allow for the connectivity of the network to be used as a comparison which is what the redundancy of the network is dependent on and not in fact the actual physical size of the network as this will not have any bearing on the clustering or meshed-ness coefficients of the networks as the actually depend on the number paths available for the distribution of the water supply systems to maintain function. The number of links is observed to range from 110 up to 1314 with the lowest being at HG-100-1-1-1 and the highest being for HG-1000-2-2-5.
When the clustering coefficient is compared against the number of links of the given water supply networks it is observed that there is a general correlation between the two data values showing that the as there is an increase in the clustering coefficient of the network as the number of links or edges in the network increases. Due to the fact that the clustering coefficient is not the most accurate method of analysing the redundancy it is observed from the graph that there are areas where the general pattern is not occurring where by the clustering coefficient is decreasing. The more accurate analysis form seems to be the meshed-ness coefficient where the general pattern of increasing redundancy as the number of links present in the networks is also increased. This finding confirms the assumption that the redundancy of any give network is improved with the increase in the connectivity of the network. This is due to the fact that the increase in the connectivity of any given network implies that there will be more transient loops and cycles present in the network creating other paths for the water supply networks to use as distribution links which will counter the possible failure experienced by any other links connecting to a node. Redundancy is a very important network characteristic due to the fact that water distribution is a vital function in the running of any populated area and disruption of this will come at great costs economical in repairs and servicing of the network. Therefore, the redundancy of the networks should be as high as possible within the physical limits.
When analysing any complex network but especially water supply networks we observe that the robustness is a very important network characteristic for in understanding how a network will react to failures within through the breakage of links or important supply nodes being affected. A method of analysing how robust water supply networks is by observing the average centrality of a network. If a network is highly centralised around an individual or group of nodes it is extremely susceptible to failure as the of analysing how robust water supply networks is by observing the average centrality of a network. If a network is highly centralised around an individual or group of nodes it is extremely susceptible to failure because if the supply nodes which are highly centralised or densely connected were to somehow experience disruption or experience failure they would affect a large portion of the network and reducing the distribution ability of the water supply network.
One of the metrics that is used to quantify the centrality and in turn the robustness of the network is the average between-ness centrality of the network which will determine the average centrality of all given paths in the network through each link thus allowing us to quantify the robustness of the network. From the analysed water supply networks, it is observed that the average between-ness centrality ranges from 651.7745098 up to 8524.496376 with the lowest value being at HG-100-1-1-1 and the highest value occurring for network HG-1000-2-2-5.
Another metric with which the robustness of the network can be quantified is by analysing the average closeness centrality of the network, unlike the average between-ness centrality this metric will hope to ascertain how centralised the network is around one or a group of nodes and their ability to affect the rest of the network by determining the shortest between each node. Observations from the water supply networks show the average closeness centrality ranging from 0.074983681 up to 0.035914688 with the highest being at HG-100-1-1-1 and the lowest value occur at network HG-1000-2-2-5.
The average path length is a metric for determining both the robustness and efficiency of the supply networks. The average path length is the average of the sum of the distance of all nodes between each other. Optimising the average path length so that it is as short as possible will allow for the efficient distribution across the water supply systems. Usually the average path length will correlate with size of the network, with increased diameters indicating an increase in the average path length and thus a reduction in the efficiency and robustness of the network. This is proven with the analysis showing an increase from 13.906 from the network with the smallest diameter up to 26.642 for the biggest network.
During the analysis of the water supply networks through the use of graph theory to determine their network characteristics such as their connectivity, redundancy and their robustness, there will be six networks used which will encompass two small, two medium and two large sized networks. As can be seen from the stated figures the water supply networks that will be analysed will vary quite greatly between each other in many metrics. The networks all vary in their sparseness with some networks being a lot less sparse.
- There will be networks with different numbers of junctions ranging from 100 to 1000 junctions allowing for the analysis of a large range of possible metric outcomes which would depend on the size of the networks being analysed, during which in the analysis they will be labelled as nodes of the graph. The other network aspect that will be interpreted as nodes in the graph form of the network will be the reservoirs of the water supply network. As can be seen from the networks the number of reservoirs will range from 2 up to 15 reservoirs as the increase in the number junctions will call more water to be supplied through the network to meet the demand which will require an increase in the number of reservoirs.
- The number of the tanks, pumps and valves for all networks will be zero and will not be taken into account during the analysis of the networks.
- The water supply networks which will be used will have a number of pipes which are dependent on the size of the overall network with the number of pipes for each network ranging from 110 to 1314. This is important to record as during the analysis of each network the edges will be defined as the connections between vertices of the network and this case the edges of the graph will be the pipes of the network.
Discussion:
The ability to conduct analysis of complex networks such as the networks created by water supply systems has been greatly improved through the use of graph theory. The ability to map these networks onto graphs using the mathematical model G = G (N, E) has allowed for a more time and computationally efficient method of quantify the characteristics of water supply networks. The aim of using graph theory to conduct a more efficient of network analysis is due to the importance with which water supply systems to functioning of everyday life in almost all societies, with uses ranging from agriculture to manufacturing, so any disruption to this service will severely impact on the everyday function of any society. So with this in mind by quantifying the characteristics of water supply networks will show how the given networks will react to failures both random and planned which will in turn allow for measures to be taken to prevent these possible failures and subsequent disruption to the distribution of the water throughout the network.
The network characteristics which are quantified through analysis to determine how the network will react to possible failures and disruptions are the analysis of the connectivity, redundancy and the robustness of the network. These network characteristics are quantified through the use of metrics analysed from the network. The quantifiable network characteristic will correspond to these metrics for the network. The metrics and the network characteristics that they correspond to is understood as:
- Connectivity of the network: This characteristic will define how connected a network is through the analysis of how each node in the water supply networks is connected to all other nodes in the network. The connections between the nodes is through links which are in water distribution networks the pipes that are used for water distribution from service nodes. The connectivity of a network will determine how easily water is distributed through the water supply system and will help determine the structure of the network. The metrics used for defining the network connectivity are the average node degree of the network, the link per node ratio and the link density of the networks. By analysing these metrics, the connectivity of the network can be determined and the structure of the network can be observed to see whether it is in the form of grid like and regular structure or more in the form of tree like structure. The connectivity of the network will show how failures will affect the network.
- Redundancy of the network:
- Robustness of the network:
