Anna Strzelecka received her master's degree in Applied Mathematics from Lodz University of Technology in Poland in 2009 and her bachelor degree in Chemical and Process Engineering from the same university in 2011. In 2011 she started her PhD research titled "One Utility for Sustainable Communities: Modelling and Optimization of UtilityService Provision" in the Water Software Systems group at De Montfort University in the United Kingdom. She was also involved in "AllinOne: Feasibility Analysis of Supplying All Services through One Utility Product" project that was funded by the Engineering and Physical Sciences Research Council (EPSRC). The project explored the possibility of delivering all household utility services via a single utility product or infrastructure 100 years in the future. She is now working on an EUfunded project titled "BlueSCities" – "Blueprints for Smart Cities: Developing the methodology for a coordinated approach to the integration of the water and waste sectors within the EIP (European Innovation Partnership) Smart Cities and Communities". One of the main objectives of the project is to develop a set of indicators for energy, transport and ICT that will assess sustainability of cities complementing the City Blueprints and Trends and Pressures Framework.
Tomasz Janus holds BEng and MSc degrees in Sanitary Engineering from Warsaw University of Technology and a PhD degree in Chemical Process Engineering from De Montfort University, UK. He has over 10 years of experience working both in industry and academia. His domain of expertise lies in modelling environmental systems, specifically wastewater treatment, water recycling, and process and energy optimisation in water and wastewater processing facilities. He is a tenured Senior Research Fellow at De Montfort University where he researches in membrane processes for wastewater treatment, process control, and pressure control in water distribution networks. He lectures in control and instrumentation and engineering mathematics. Tomasz has over 25 publications in peer reviewed journals and conferences.
Leticia OzawaMeida is a Research Fellow Research Fellow in the Institute of Energy and Sustainable Development at De Montfort University in the United Kingdom. Leticia works on the quantification and evaluation of Greenhouse Gas (GHG) emissions at the local, sectoral and organizational level using productionbased and consumptionbased calculation approaches. She has worked on research and consultancy projects for the Higher Education Funding Council for England (HEFCE) and JISC on measuring and reporting indirect ‘Scope 3’ GHG emissions, particularly related to procurement, water and waste management. She has also worked on a project funded by the UK Engineering and Physical Sciences Research Council (EPSRC) examining the scientific and technological viability of substituting the current diversity of utility products such as water, gas and electricity with a “single utility product” that can provide all the services required by the endusers. She has also worked on an EU and ICT PSP cofunded project titled “Saving Energy in Europe's Public Buildings Using ICT (SmartSpaces)” focusing on the evaluation of the impact that the energy management and energy decision support services implemented in each pilot site have on building users and consequently on energy and water savings.
Bogumil Ulanicki graduated from Warsaw University of Technology in Poland in 1974 and received PhD in 1979 and DSc 1994 from the same university. Since 1987 he has been working at De Montfort University in Leicester in the UK. Currently he is Head of Centre of Engineering Science and Advanced Systems (CESAS) and Director of the Water Software Systems (WSS) research group. His expertise covers the areas of control and water engineering and IT. He has over 130 publications in world leading journals and refereed conference proceedings mainly in the water distribution systems management area. He is a member of the EPSRC College and acts as an EC projects reviewer. Prof. Ulanicki led 36 major projects of which 17 were research projects 19 contract research projects for the UK and the EU water industry.
Piotr Skworcow holds BEng and MSc degrees in Computer Science from Wroclaw University of Technology in Poland and PgC in Systems and Control from Coventry University, UK. In 2008 he received PhD in Control Engineering from Coventry University. Since 2008 he has been working at De Montfort University in Water Software System in the areas of model predictive control, applied control systems, optimisation methods, software development, systems engineering, and water distribution systems management. He was a module leader in Control and Instrumentation Engineering. Dr. Skworcow was a coorganizer of series of workshops organized jointly by Coventry University, UK and Wroclaw University of Technology, Poland; coeditor (20062007) and editor (2008  ongoing) of proceedings: PolishBritish Workshop: Computer Systems Engineering, IET Control and Automation Professional Network. He has 9 journal papers and 33 refereed conference papers. Since 2014 he has been working as a Programmer Analyst at Callisto Integration.
Utility–service provision is a process in which products are transformed by appropriate devices into services satisfying human needs and wants. Utility products required for these transformations are usually delivered to households via separate infrastructures, i.e., realworld networks such as, e.g., electricity grids and water distribution systems. However, provision of utility products in appropriate quantities does not itself guarantee that the required services will be delivered because the needs satisfaction task requires not only utility products but also fully functional devices. Utility infrastructures form complex networks and have been analysed as such using complex network theory. However, little research has been conducted to date on integration of utilities and associated services within one complex network. This paper attempts to fill this gap in knowledge by modelling utility–service provision within a household with a hypergraph in which products and services are represented with nodes whilst devices are hyperedges spanning between them. Since devices usually connect more than two nodes, a standard graph would not suffice to describe utility–service provision problem and therefore a hypergraph was chosen as a more appropriate representation of the system. This paper first aims to investigate the properties of hypergraphs, such as cardinality of nodes, betweenness, degree distribution, etc. Additionally, it shows how these properties can be used while solving and optimizing utility–service provision problem, i.e., constructing a socalled transformation graph. The transformation graph is a standard graph in which nodes represent the devices, storages for products, and services, while edges represent the product or service carriers. Construction of different transformation graphs to a defined utility–service provision problem is presented in the paper to show how the methodology is applied to generate possible solutions to provision of services to households under given local conditions, requirements and constraints.
Utility–service provision is a process in which utility products such as water, electricity, food, etc. are delivered to households to satisfy basic human needs such as nutrition, adequate quantity and quality of water, thermal comfort, and wants such as leisure. These products can either be delivered via infrastructure or produced locally, e.g., electricity can be produced from sunlight using solar panels or water can be harvested from rainwater and subsequently treated to drinking water standards
Utility infrastructures such as power grids, water and gas pipelines, or transportation and communication systems can be considered as complex networks with similar topological and dynamic properties to the World Wide Web
Social networks in which a set of people form patterns of contacts or interactions, e.g., friendships, thematic groups, mutual likes and hobbies, etc.;
Information networks, otherwise referred to as knowledge networks, e.g., the network of citations between academic papers or the World Wide Web where web pages are linked via hyperlinks pointing from one page to another;
Biological networks such as the food web, in which nodes represent species in an ecosystem and directed edges between two nodes indicate that the former species prays on the latter one
Technological networks designed for distribution of some commodity or resource, e.g., information, water, electricity, etc.; such networks are the main focus of this paper.
Utility–service provision can be considered as a technological network and analyzed as such since its main objective is to deliver different utility products to households and then convert these utility products using different devices into services in order to satisfy basic human needs and wants. This task is very complex as its success depends on multiple factors such as proper functioning of devices and the infrastructures delivering the required utility products. Failure of one or more of these components might possibly deprive the users of a product and thus, service, for an unknown amount of time.
The complexity utility–service provision becomes more visible when we look at the structure of a typical utility infrastructure which is hierarchical and can be divided into households, communities, districts and cities. A household is a component of a community, the community can be a part of a district in a city whilst cities can be regarded as hubs in a countrywide network. Each level of this hierarchy has its own structure and distinct operational properties. Such a hierarchical structure creates complexity as the behavior of the overall behavior of the cities and districts emerges from the combined behavior of single households. However, it is difficult to deduct the features of a city from the characteristics or properties of an individual households due to inherent variability of the households and the living patterns of the inhabitants
The mapping between products, services and devices in the utility–service provision task is best to be represented with a directed graph. Unfortunately, a standard directed graph restricts the user in providing a complete description of the system under investigation
The main objective of this paper is to represent utility–service provision as a directed hypergraph and analyze its statistical properties such as degree distribution, path lengths, cardinality of nodes, etc. Such an utility–service provision hypergraph contains all available, i.e., possible to use, devices. These statistical measures can later be used to help in solving individual utility–service provision problems under given constraints such availability of products, devices and the required services to be provided. While the overall utility–service provision hypergraph is later referred to as ‘mastergraph’ the individual casestudy utility–service provision for a specified household will be called a ‘transformation graph’. Therefore, the ‘transformation graph’ is a subgraph of the ‘mastergraph’. For the purpose of further quantitative calculations and optimisation the ‘transformation graph’ is however later converted into a standard graph in which nodes represent devices, and storage for products and services, while edges are product or service carriers.
As the number of devices in our ‘mastergraph’ is rather significant this paper considers a simplified utility–service provision case in which the number of devices, products and services have been reduced. This simplified ‘mastergraph’ is represented as a hypergraph (as described above) and its statistical properties are subsequently analyzed. Moreover, different transformation graphs are then constructed from this simplified ‘mastergraph’ to highlight how this methodology can be applied to reallife utility–service provision problem.
The paper is structured as follows: Section "Review of technological networks" provides a theoretical introduction to graph theory followed by an examination of the properties of physical infrastructures selected from literature. Section "Utility–service provision as a complex network" describes an approach to model utility–service provision with a directed hypergraph. In particular Section "A simplified utility–service provision scenario" describes a simplified utility–service provision example and its hypergraph description while Section "A complete utility–service provision model" analyses the properties of the master graph considering all utilities, devices and services stored in the database. The paper concludes in Section "Conclusion" with potential future research directions.
Realworld networks such as electricity grids, water pipelines, transport systems and communication networks consist of millions of nodes with multiple edges spanning between them. Structures of these networks are usually irregular and evolving in time, and have been successfully analyzed in the past using graph theory
A topological structure of a network can be represented as an undirected or directed
A
However, as mentioned in the introduction, representing a complex network as a standard graph has its limits because in such graphs and edge can connect only two nodes while, in general case, this may not be sufficient. Estrada and RodriguezVelazquez
A standard graph can be defined with a
Each node
Hypergraphs additionally have another property called
Connections between nodes in a graph are described with paths, each path having an associated length. A path in a graph
such that
Some technological networks such, in particular transport networks, can be additionally quantified by calculation of the shortest paths between nodes, e.g., shortest paths between bus stops or train stations. The
The
Another crucial property of a node or edge is the
where
Complex network theory have been used to analyze various realworld problems e.g., Watts and Strogatz
A particular type of a real network is a
Table 1 lists the values of the most relevant properties of the utility infrastructure networks introduced in the previous section, in particular two water distribution networks, a power grid, and two transport networks.
Properties of utility infrastructure networks selected from literature:
Utility infrastructure  Network  n  m  k  l  C  ?  Reference 
Water distribution networks  EastMersea (UK)  755  769  2.04  34.5  0  1.71 

Richmond (UK)  872  957  2.23  51.4  0.04  1.98  
Power grids  Coarsegrain Italian 380 kV transmission network  127  171  2.7  8.47  0.16  0.18 

Transport  Rapid Transit System (Singapore)  93  3843  82.6  1.1  0.93  0.08 

Bus systems (Singapore)  4,131  213,103  103.2  2.5  0.56  0.01 
The first row of Table 1 features two examples of water distribution networks in the United Kingdom: the EastMersea distribution subnetwork owned by Anglian Water and the Richmond subnetwork of Yorkshire Water. These networks were examined by Yazdani and Jeffrey
Pagani and Aiello
Soh
Rosato
The analysis of the topology of utility–service provision systems was carried out with two aims in mind: (a) to explore the possibility of delivering all services to households or small local communities via a single utility product by developing visions of future infrastructure
The utility–service provision can be shortly explained as follows. Utility products are usually delivered to households via separate infrastructures, i.e., realworld networks such as electricity grids, water distribution systems, etc. However, provision of different utility products in appropriate quantities does not itself guarantee that the required services will be delivered as the needs satisfaction problem requires not only utility products but also appropriate devices. An approach to solve this type of problems was earlier described in
Since construction of a dynamic simulation model based on the topology of the utility–service provision graph is not a part of this article, it will not be described here in much detail. In principle, the paths between products and services are selected from the utility–service provision hypergraph. These paths form candidate solutions, also called transformation graphs, and are sets of devices connected together that either are required to deliver services defined in the problem formulation or are necessary to recycle some of the products. Each transformation graph is then evaluated under requirements, i.e., the amount and type of services to be provided and constraints, e.g., maximum size of a particular device or maximum amount of a product sourced onsite in order to check whether it is possible to satisfy the requirements, i.e., if a feasible solution exists. The computational engine analyses the feasibility of solution(s) and calculates the mass balances of all products and services. The feasible candidate solutions can then be compared against various criteria such as total energy consumption, reliance on natural resources, resilience, etc.
More information about the simulation system can be found in
In order to allow the user to better understand how the utility–service provision problem may be described as a directed hypergraph, we will first consider a simplified scenario in which only a small number of utility products,services and devices are considered. The hypergraph created for this purpose is shown in Figure 1. The nodes, marked in Figure 1 with circles represent products:
Having such a utilityservice provision solution space specified with the hypergraph in Figure 1 we can now search for possible candidate solution given the required services to be delivered and constraints put on products. In this example the required services are
The next step after problem formulation is to find candidate solutions based on the topology of the utility– service provision hypergraph and with the requirements and constraints specified in problem formulation. Search for candidate solutions is directed towards finding an answer whether it is possible to deliver required services with available devices and under the given constraints. At this stage demands for services and maximum throughputs of the devices are not considered, only the topological properties of the hypergraph and the given constraints on the amounts of products to be produced and consumed.
Definition of a transformation graph from the hypergraph is preceded by formulation of an incidence matrix which describes the topological structure of the hypergraph. For our simplified hypergraph shown in Figure 1 the colorcoded incidence matrix is given in Figure 2. The storage’s product outputs, i.e., tail nodes are shown in green and have an associated value 1 representing a sink and thus input to the device. Storage product inputs, i.e., head node are shown in red and have a value of 1 denoting the source, i.e., output from the device. Greycoded fields represent products that are used both as an input and as an output and have been assigned a value of 2. Finally, bluecolored fields denote the produced services and are have an assigned value of 1 as head nodes.
The incidence matrix in Figure 2 shows that product
In addition to the incidence matrix, which provides information about the topology of the hypergraph, we introduce two more matrices which additionally provide quantitative information about the operating rules of the devices, i.e., how much of a product is used and produced by a given device. The benefit of such representations is that it enables a quantitative comparison of the amounts of products produced or used by corresponding devices and of the amounts of services they generated by the devices. This information can be later used to calculate the mass balances of all services and products and, subsequently, assess the feasibility of a given solution. Whilst Figure 3 presents the amounts of products (inputs) used by all devices Figure 4 shows the amounts of products and services produced by these devices. Since services cannot be used by devices as inputs they not included in Figure 3.
Additional information about a hypergraph, for construction of transformation graphs, is provided by a matrix of shortest paths from product nodes to service nodes, such as one listed in Table 2. Shortest path values in Table 2 are calculated with Equation 5. The matrix of shortest paths is used for solution optimization, e.g., when it is required to minimize the number of used devices. If the sought solution is such in which the number of used devices are reduced to minimum the devices chosen from the hypergraph to form the transformation graph should lie on the shortest paths. Another piece of information provided in Table 2 indicates whether there is a possibility to deliver a service starting from a given product node, e.g., when investigating the first column it is clear that there is only one path between the product node
Shortest paths lengths in the hypergraph introduced in Figure 1
n_{10}  n_{11}  n_{12}  n_{13}  

n_{1}    2  2  2 
n_{2}    1  1  1 
n_{3}        1 
n_{4}    2  2  2 
n_{5}         
n_{6}    2  3  3 
n_{7}    1  2  2 
n_{8}  1  3  1  4 
n_{9}    2  2  2 
Another parameter that is useful when analyzing a hypergraph (and therefore potential candidate solutions) is the
A candidate solution, i.e., transformation graph is formulated based on the requirements listed in the problem formulation in the section titled "Problem formulation". In principle, this problem can have many solutions and these solutions can then be evaluated and compared against each other from the point of view of their complexity, resilience, energy demand, robustness, etc. The first step in generating transformation graphs is to create an empty transformation graph containing all required service nodes, i.e.,
An example of a transformation graph is presented in Figure 5 where devices are given a rectangular shape, services have an octagonal shape and products are depicted with trapezoids.
Sensitivity of a hypergraph to critical nodes can be described by degree distribution which provides the information on how many nodes in a hypergraph are highly and lowly connected. The more connections a node has the more important it is in the graph as more paths traverse through it. Therefore such a node may be critical to a proper functioning of a system described with such a graph. Figure 6 shows that the degree distribution for our hypergraph follows a powerlaw function
Top betweenness nodes in our example are: electricity:
The ‘mastergraph’, as defined in the Introduction, has the same structure like the simplified hypergraph presented in Figure 1 but with larger number of nodes and hyperedges. It is built from the database of devices obtained from literature and technical data sheets and is used to generate authentic transformation graphs (i.e., utility–service provision solutions) for reallife problems. At the current state of development the master graph contains
The size of our master graph is 299 with a device having, on average, 3.1 inputs and outputs. Degree distributions of the nodes in the master graph considering individually inputs (in), outputs (out), and total number of connected edges (all), are presented in Figure 7. The identified degree distribution for inputs as well as outputs follows a powerlaw function
Analysis of the master graph led to the following observations. The most connected nodes are: electricity (total: 81, in: 28, out: 53), clean water (total: 19, in: 13, out: 6), drinking water (total: 16, in: 7, out: 9), greywater (total: 13, in: 11, out: 2) and waste water (total: 12, in: 3, out: 9).
Top betweenness nodes are: electricity:
This paper began with the examination of the relevant characteristics of the chosen utility infrastructures, i.e., realworld networks, such as water distribution systems, electricity grids, etc. These networks were reviewed using complex network analysis based on existing studies which investigated such properties of the networks as, i.e., topological features, robustness, redundancy, vulnerability (e.g., against intentional attacks), etc. The methods used in these studies were later applied to the analysis of hypergraphs describing utility–service provision scenarios.
Utility–service provision problem was formulated and presented with a hypergraph instead of simple graph as the hypergraph allows to map more than two nodes with one edge which is necessary to describe utility–service provision in which edges describe the devices which can use more then one product as an input and output. This hypergraph was then analysed with a number of statistical measures in order to extract additional information about the graph which is then used to generate candidate solutions, i.e., transformation graphs, which are subsequently used to specify dynamic models of utility–service provision systems which are then simulated and optimized  see
First the topology of the hypergraph is visualized with an incidence matrix which helps to identify the devices (edges) necessary to deliver the specified services (nodes) and the products (nodes) required for proper functioning of the devices (edges). This incidence matrix is then complemented with two additional matrices which, in addition to graph topology, also provide quantitative information about the amount of products consumed and produced and services produced in the system. Subsequently, yet another matrix, i.e., the matrix of shortest paths is produced to aid with identification of shortest paths between utility products and services, i.e., transformations requiring the least amount of devices. Additionally, the matrix of shortest paths is used to identify critical products required to deliver a specified service required for an assessment of the system’s resilience, i.e., its lack of vulnerability to situations where one or many products fails to be delivered. To assess the vulnerability of the system to failures of the devices we use both the matrix of shortest paths (which can be used to show the number of alternative paths to deliver the required service) as well as the cardinality of hyperedges which quantifies how many inputs and outputs, i.e., products and services are associated with this particular device. Finally, as the last measure of quantifying a hypergraph we calculate the node degree distribution which shows the critical nodes (with large number of connections) as well as its share in the total number of nodes in the system.
All of these measures offer crucial information for further analysis of utility–service provision such as generation of possible solutions (utility–service provision configurations), subsequent analysis of their resilience, vulnerability, robustness, and redundancy, and generation of dynamic models for the purpose of simulation and optimization.
This research is a part of the Engineering and Physical Sciences Research Council (EPSRC) project “All in One: Feasibility Analysis of Supplying All Services Through One Utility Product” (EP/J005592/1).