The use of network theory to model disparate ship design information

International Journal of Naval Architecture and Ocean Engineering.
2014.
Jun,
6(2):
484-495

This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

- Published : June 30, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

INTRODUCTION

Ships are extremely complex systems comprised of many smaller but equally complex subsystems that often have unforeseen interactions and interdependencies. This paper introduces a network theory based approach to quickly model and analyze the design of these systems and their interactions. The goal of this work is provide a new way of handling ship and ship system design information in the early design stage. All too often, information about the interactions of ship systems is only captured in detailed CAD models that are not available in the early stages of design. The lack of knowledge of these interactions can lead to substantial redesign in later stages or, in extreme cases, unforeseen failures in completed ships.
The paper will begin with a brief introduction to relevant network theory concepts, the network representations of three ship systems are developed and each system is analyzed individually. The systems to be analyzed are a passageway system with a focus on evacuation and personnel movement, an electrical system with focus on robustness, and a fire fighting system also with a focus on robustness. The individual systems will be analyzed using the network concepts of density, centrality, and community structure. Following the individual analysis, the three systems will be analyzed as a whole using a multiplex network which will enable the evaluation of disparate systems in a common framework. The paper will conclude with a brief summary and a discussion of possible directions for future research.
MOTIVATION

Existing general arrangement tools are capable of generating feasible layouts, but lack the underlying knowledge regarding why layouts are configured as they are. Network based methods, developed at the University of Michigan (
Gillespie, 2012
), can be used to bridge this gap as they provide a unique perspective to the traditional view of ship arrangements by relying on the relationships between ship board elements and components. A network analysis expands the scope of the general arrangement process and helps to manage complexity by revealing underlying character and structure, providing insight into the function of a complex system. Quality three dimensional distributed system layouts are difficult to generate, thus the ability to evaluate the design drivers prior to the general arrangement process through a network approach would be of value. Identifying the disparate ship design information in the form of design drivers captures the abstract concept of designer intent while modeling design rules and best practices. These metrics indicate the underlying personality and style of the design (
Pawling et al., 2013
). By modeling ship systems as networks, the designer can evaluate network metrics to further understand the design space.
Graph theory also has been shown to be useful as a model for the facilities layout problem (
Hassan and Hogg, 1987
NETWORK THEORY BACKGROUND

This section serves to introduce basic network theory nomenclature and metrics used in this paper. For a more comprehensive discussion of network and graph theory the authors recommend the textbook written by
Newman (2010)
.
- Network structure

Networks, which are also called graphs depending on the context, consist of a collection of nodes connected by edges. The networks described in this section and the next are known as simplex networks in that the nodes and edges represent only one type of entity and connection, respectively. For this work, networks will be represented mathematically using an adjacency matrix A, which represents the connections between the nodes. The two most basic kinds of networks are undirected and directed networks. In an undirected network the adjacency matrix is symmetric and the links between nodes represent any connection between them. A directed network on the other hand has an asymmetric adjacency matrix and the edges represent a link from one node to another.
Fig. 1
displays an unweighted, undirected network with its adjacency matrix. In this kind of network, an edge is represented by the number 1 in some element of the matrix showing a connection from node
PPT Slide

Lager Image

- Degree

The degree of node
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- Paths

Where degree measures are concerned with the edges into and out of one node, path measures are concerned with the edges that connect various nodes. The most basic, and easiest to overlook, path dependent measure is connectivity or whether or not each node is connected to each other node through some path. Every network presented in this work should be a fully connected network otherwise, for example, there could be spaces that are inaccessible from other spaces. Next, one can analyze the shortest path or longest path characteristics between nodes. In an evacuation scenario, the shortest path between a berthing space and a muster station for lifeboats would be of utmost importance. The diameter of a graph is the length of the longest, shortest path between any pair of nodes and is a useful for quickly judging the size of a network. Longest paths are useful for determining upper bounds for the time or size of network based processes.
- Centrality

Centrality is a way of addressing which are the most important nodes within a network. The simplest measure of centrality, mentioned above, is the degree of a node. But for this work, a more advanced concept of centrality called betweenness centrality, or simply betweenness, will be used.
Betweenness is the measure of the extent a node lies in the paths between other nodes (
Freeman, 1977
) and is not concerned with the degree of the nodes. A node with a degree of two could easily have the highest betweenness in a network because it is the only connection between all the other nodes. More generally, it can be said that nodes with high betweeness have the most control over traffic across the network because the most amount of traffic must pass through them. They can be considered choke points and their removal from the network would cause the most disruption of traffic flow across the network. The betweenness, bi, of node i is the ratio of the number of shortest paths, ni, between node s and node t that cross node i to the total number of shortest paths, gst, between s and t Eq. (4).
PPT Slide

Lager Image

- Communities

It is natural to try and breakdown networks into smaller groups or communities to see how the different groups interact. There are two ways of going about this: graph partitioning or community detection. Graph partitioning seeks to divide a network into a predetermined number of groups or into groups with a fixed sized while minimizing the number of edges between the groups. Partitioning can be used to aid in creating a logical general arrangement (
Gillespie, 2012
).
Community detection, on the other hand, does not start with a predetermined number or size of groups. The community detection approach will be used in this work as we assume a basic general arrangement or series of general arrangements have already been completed and now a designer is attempting a tradeoff study between them. This work will consider a subgraph (a smaller part of the network) a community if the intensity of the interactions among nodes in the subgraph is higher than what would be expected in a random graph (
Barigozzi et al., 2011
). In this paper communities will be found via spectral modularity maximization using the Louvain method (
Blondel et al., 2008
). The method seeks to maximize a quality function (Eq. (5) for simplex networks (
Lambiotte et al., 2009
)) by first maximizing modularity in local communities then creating a new network based on these communities. The process is repeated until no increase in the overall quality function is possible.
PPT Slide

Lager Image

SHIP SYSTEMS AS NETWORKS

In this section, a nominal warship’s general arrangements will be used to create network representations of the ship’s passageway, electrical, and firefighting systems. This ship design is a senior design project from the University of Michigan Department of Naval Architecture and Marine Engineering’s capstone design class. While the general arrangements are complete, the distributed system design is not and has been approximated using by the authors of this paper. The ship is a 108
- Passage system

The passageway network of a ship is nearly identical to that of the road network of a city; as such, many of the techniques for modeling and analyzing passages have been borrowed from the urban planning and traffic engineering disciplines. Road or passage networks are called spatial networks because nodes represent something in a physical space and edges are equipped with some sort of physical metric. Typically the space is a two dimensional space and the metric is Euclidean distance (
Barthélemy, 2011
). There are two ways of representing such systems as a network: either passage segments are denoted as edges and intersections are nodes or the reverse where the intersections are treated as edges connecting the nodes representing road segments. For this analysis, the former representation where the passage segments are edges and the intersections of the segments are nodes was used as it is a more intuitive structure when dealing with personnel movement and evacuation. A node is placed at each doorway from a space or stairwell as well as anywhere that two passages intersect, nodes are then connected by edges representing the connecting passages. Edge weights are equal to the distance, in meters, between the intersections. The 02 level was not included in the passageway network as it only had two functional spaces.
Fig. 2
displays a small section of the ship with the passage nodes and edges shown. This representation also was chosen because it can easily be adapted into a discrete event simulation (
Teknomo and Fernandez, 2012
) where the movement of agents throughout the passage system can be visualized. The goal of this work is not simulation but rather an easy-to-use metric for comparing multiple designs.
Table 1
displays some key properties of the passage system networks of the example ship.
PPT Slide

Lager Image

PPT Slide

Lager Image

Characteristics of ship passage networks.

PPT Slide

Lager Image

- Electrical system

The electrical system network was created by placing a node in each space, at each passage intersection, and at each passage dead end. Longer passageways also had a node place at their midpoint. Additionally, nodes were placed where major deck machinery and weapons systems are located. The network assumes three voltage levels which are used for assigning edge weights: a 120
Electrical system edge weight factors.

PPT Slide

Lager Image

Characteristics of ship electrical networks. Deck No. of Nodes No.

PPT Slide

Lager Image

Electrical system network communities.

PPT Slide

Lager Image

PPT Slide

Lager Image

- Fire fighting system

The fire fighting system network representation used the same nodes and edges as the electrical system with different weighting factors on the edges. The edge weights for the fire fighting system are the distances between nodes multiplied by a risk factor. Each node was assigned one of three levels of risk: high, medium, and low based on a combination of the nodes likelihood of damage and the nodes importance to ship’s operation. High risk spaces include engine spaces, damage controls spaces, and magazines. Medium risk spaces include galleys and the steering gear room. Berthing and general storage spaces are considered low risk.
Table 5
shows the weighting factors for the fire fighting system. The fire fighting system will be driven by the location of critical mission equipment and major machinery.
Since the fire fighting system network is a re-weighting of the electrical system network the number of nodes and edges as well as the average degree and density are the same as those reported in
Table 3
. The betweenness scores for the nodes are also similar: the hub nodes have high betweenness while the spoke nodes have low to zero betweenness. The fire fighting system network has the same robustness issues as the electrical system in that it is susceptible to targeted attacks due to its scale-free degree distribution. While the fire fighting and electrical networks share many similarities, they have different community structures and quality values as can be seen in
Table 6
.
The electrical system and fire fighting system on the 01 Level have same community structure with only a minor difference in quality due to the low voltage spaces on that level also being low fire risk spaces and high voltage spaces being high fire risk spaces. The same can be said about the communities on the second deck. The main deck has the largest difference between communities and quality due the deck machinery and weapons systems outside of the deck house which do not receive as high of a fire risk factor, almost detaching them from the rest of the main deck’s fire fighting system. On the third deck, the fire fighting system has an extra community because it breaks the port and starboard gas turbine spaces and the aft auxiliary machinery room into three different groups whereas the starboard gas turbine space and aft auxiliary are in the same electrical community.
Fire fighting system edge weight factors.

PPT Slide

Lager Image

Fire fighting system network communities.

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

Multiplex network communities.

PPT Slide

Lager Image

CONCLUSIONS

In this paper it has been shown that network theory can be used to quickly model and analyze disparate ship systems. This network-based approach is useful in the early design stage because it can be used to evaluate ship systems, both individually and in aggregate, without relying on detailed CAD or physical models that are often too time or cost intensive in this early stage. Additionally, these concepts can be used for any ship system and limited only by a designer’s creativity in representing said system with a network.
The passageway, electrical, and firefighting systems for a nominal corvette-sized naval combatant were modeled and analyzed using basic network concepts. Using the concept of evacuation betweenness, introduced in this paper, it was found that a berthing area on the third deck was unacceptability hard to escape from. Additionally, it was determined, using betweenness centrality, that stairwells are the most important connections for a passageway system a extra care should be taken when placing them in a general arrangement. A community detection algorithm also showed the ship spaces were grouped around stairwells, once again pointing to their importance. It is believed the groups generated by this community detection algorithm can be used for simplifying discrete event simulations for egress, separating the ship into damage control zones, or in planning block breaks for ship construction.
Due to their hub and spoke nature, which is vulnerable to targeted attack, the electrical and firefighting systems proposed for this ship were found to be inadequate for the ships mission. Additionally, the community structures of both systems were found to be nearly identical. This is not acceptable as it would be very easy to simultaneously lose electrical and firefighting capabilities in one area of the ship.
Combining the networks into a multiplex network and again using a community detection algorithm identified essentially the same community structure as was found for the electrical and firefighting systems individually. The quality of the multiplex communities was higher than the quality for the communities in the individual networks which means the communities more strongly delineated for the multiplex network. This increase in quality is due to the electrical and firefighting systems being similar as well as an additional coupling, via passageways, between the two systems. This additional interconnectedness of the electrical and firefighting systems could further reduce the robustness of these system to targeted attack by making the major hub nodes even more important to the overall system.
FUTURE WORK

There are two major avenues of future work. One is using the results here as a guide for automatically generating general arrangements and their respective distributed systems. Much work has already been done on creating general arrangements (
Pawling, 2007
;
Nick, 2008
;
Oers, 2011
), but the generation of the distributed systems within those designs has been lacking. Additionally, analysis of early stage personnel movement through these general arrangements relies heavily on 3D models and simulation (
Casarosa, 2011
) which is time consuming and requires a more detailed model than many concepttual or initial designs can provide.
The other possible route for future work is tracking design changes by way of a multislice network. If the structure of the multiplex ships systems networks from this paper were kept, this would entail connecting a series of multiplex networks through time which can be visualized as a series of three dimensional matrices in sequential order. It is proposed that at the most initial design only the most general of ships networks would be filled in, and as a design progressed the networks for the more specialized systems would be created. Community detection for such a model would require a new and more complex quality function. Knowing how the communities changed or did not change would be valuable for designers, as they could keep track of when adding new information or systems to a design no longer changed the overall structure. Additionally, designers could use such a system to either try to keep like parts together for production reasons (keeping all of certain subsystem contained within a production block for example) or spread the different subsystems or parts of subsystems through the ship for survivability.
PPT Slide

Lager Image

Altshuler Y.
,
Puzis R.
,
Elovici Y.
,
Bekhor S.
,
Sandy A.
2011
Augmented betweenness centrality for mobilityprediction in transportation networks
In Finding Patterns of Human Behaviors in Network and Mobility Data
1 -
12

Azadivar F.
,
Wang J.
2000
Facility layout optimization using simulation and genetic algorithms
International Journalof Production Research
38
(17)
4369 -
4383
** DOI : 10.1080/00207540050205154**

Barigozzi M.
,
Fagiolo G.
,
Mangioni G.
2011
Community structure in the multi-network of international trade
Complex Networks
116
1 -
27
** DOI : 10.1007/978-3-642-25501-4_1**

Barthélemy M.
2011
Spatial networks
Physics Reports
499
(1-3)
1 -
86
** DOI : 10.1016/j.physrep.2010.11.002**

Blondel V.D.
,
Guillaume J.-L.
,
Lambiotte R.
,
Lefebvre E.
2008
Fast unfolding of communities in large networks
Journal of Statistical Mechanics
2008
(10)
10008 -
10019
** DOI : 10.1088/1742-5468/2008/10/P10008**

Casarosa L.
2011
The integration of human factors, operability and personnel movement simulation into the preliminarydesign of ships utilising the Design Building Block approach. Ph.D. thesis
University College of London

Fleck M.
2013
In Building Blocks for Theorectical Computer Science
1.3 edn
Univesity of IllinoisChampaign-Urbana
Champaign

Freeman L.
1977
A set of measures of centrality based on betweenness
Sociometry
40
(1)
35 -
41
** DOI : 10.2307/3033543**

Gillespie J.W.
2012
A network science approach to understanding and generating ship arrangements in early-stagedesign. Ph.D. thesis
University of Michigan

Gillespie J.W.
,
Singer D.J.
2012
Helping bridge the gap between space-only arrangements and distributed systemlayouts
Proceedings of ASNE Day 2012
1 -
4

Hassan M.M.
,
Hogg G.L.
1987
A review of graph theory application to the facilities layout problem
Omega
15
(4)
291 -
300
** DOI : 10.1016/0305-0483(87)90017-X**

2007
Guidelines for evacuation analysis for new and existing passenger ships. MSC Circular 1238
InternationalMaritime Organization
London

Jutla I.S.
,
Jeub L.G.S.
,
Mucha P.J.
2011
A generalized louvain method for community detection implemented in MATLAB. [online]
Available at: < http://netwiki.amath.unc.edu/GenLouvain/GenLouvain>

Kemink L.
,
McKenney T.A.
,
Parker M.C.
,
Partida A.
2009
Cougar-108 design report
University of Michigan
Ann Arbor

Lambiotte R.
,
Delvenne J.
,
Barahona M.
2009
Laplacian dynamics and multiscale modular structure in networks

Lee K.-Y.
,
Roh M.-I.
,
Jeong H.-S.
2005
An improved genetic algorithm for multi-floor facility layout problemshaving inner structure walls and passages
Computers & Operations Research
32
(4)
879 -
899
** DOI : 10.1016/j.cor.2003.09.004**

Lewis K.
,
Kaufman J.
,
Gonzalez M.
,
Wimmer A.
,
Christakis N.
2008
Tastes, ties, and time, a new social networkdataset using Facebook.com
Social Networks
30
(4)
330 -
342
** DOI : 10.1016/j.socnet.2008.07.002**

Mucha P.J.
,
Richardson T.
,
Macon K.
,
Porter M.A.
,
Onnela J.-P.
2010
Community structure in time dependent,multiscale, and multiplex networks
Science
328
(5980)
876 -
878
** DOI : 10.1126/science.1184819**

Newman M.
2004
Analysis of weighted networks
Physical Review E
70
(5)
056131 -
** DOI : 10.1103/PhysRevE.70.056131**

Newman M.E.J.
2010
Networks, An Introduction
Oxford University Press
Oxford

Nick E.K.
2008
Fuzzy optimal allocation and arrangement of spaces in naval surface ship design. Ph.D. thesis
Universityof Michigan

Oers van B.
2011
A packing approach for the early stage design of service vessels. Ph.D. thesis
Delft University of Technology

Parker M.C.
,
Singer D.J.
2013
The impact of design tools, looking for insights with a network theoretic approach
In Proceedings of the 12th International Conference on Computer Applications and Information Technology in theMaritime Industries
96 -
109

Pawling R.
2007
The application of the design building block approach to innovative ship design. Ph.D. thesis
UniversityCollege London

Pawling R.
,
Andrews D.
,
Piks R.
,
Singer D.
,
Duchateau E.
,
Hopman H.
2013
An integrated approach to style definitionin early stage design
In Proceedings of the 12th International Conference on Computer Applications andInformation Technology in the Maritime Industries
248 -
263

Singh P.
,
Sharma R.R.K.
2005
A review of different approaches to the facility layout problems
The International Journal of Advanced Manufacturing Technology
30
(5-6)
425 -
433

Teknomo K.
,
Fernandez P.
2012
Simulating optimum egress time
Safety Science
50
(5)
1228 -
1236
** DOI : 10.1016/j.ssci.2011.12.025**

Zhao J.
,
Xu K.
2009
Enhancing the robustness of scale-free networks
Journal of Physics A: Mathematical and Theoretical
42
(19)
195003 -
** DOI : 10.1088/1751-8113/42/19/195003**

Citing 'The use of network theory to model disparate ship design information
'

@article{ E1JSE6_2014_v6n2_484}
,title={The use of network theory to model disparate ship design information}
,volume={2}
, url={http://dx.doi.org/10.2478/IJNAOE-2013-0194}, DOI={10.2478/IJNAOE-2013-0194}
, number= {2}
, journal={International Journal of Naval Architecture and Ocean Engineering}
, publisher={The Society of Naval Architects of Korea}
, author={Rigterink, Douglas
and
Piks, Rebecca
and
Singer, David J.}
, year={2014}
, month={Jun}