## CSRG - Graph Research |

A **graph or network is a data structure** comprising a set of nodes (or vertices) that are connected together by a set of edges
(or arcs). Probably the best known "graph" is the planar graph representation of the London Underground train system. A
representation of this graph (rendered by the GraViz tool) is shown above - the nodes or tube stations are shown as red squares and
the connecting lines are shown as black edges. Many application problems can be formulated in terms of graphs or networks, and as
such can be analysed using the many standard graph algorithms that are available. As well as being able to apply static analysis
techniques that: count the statistics of node or edge properties; study the connected components or highly connected communities of
nodes; or study the spectral properties of various matrices associated with graphs, we also investigate the dynamics of models that
can be defined on graphs and networks.

Some aspects of graphs that are of particular interest are the **scalability problems** that arise when we have large and
changing networks of "**big data**" or when the nodes are especially densely connected. We study graphs and networks that arise
from: energy, and utilities distributions; traffic and transport systems; biological and neural networks; sociological networks;
financial and economic systems; Internet and Web overlay networks; and from various artificially generated networks with known
statistical properties.

Our research is aided by a set of **software tools and the metrics** that they enable, to both visualise and to carry out
numerical experiments and analyses on individual and families of networks. In many cases, even a well-known metric turns out to be
too computationally hard to study for large graphs and networks with off-the-shelf existing tools, and our research contribution has
been to find a sophisticated way to program and implement the calculation for interestingly large systems.

An emerging area of strong interest is the use of **graph databases**. Traditional databases use a relational model to capture
the relationship properties between the data items. However, despite the widespread use of structured query language( SQL)
databases there is a growing "NOSQL" movement which is "not only" limited to just SQL. Graph databases capture the relationships
between entities on the nodes using edges to hold the relational properties. As well as offering a great deal of scalability and
other flexible properties, graph databases also typically allow all the power of known graph and network analysis algorithms to be
brought to bear on the data in the database, opening up scope for pattern detection, analysis and some very **powerful analytic**
metrics and tools.

Our research group has a number of live and ongoing projects involving graph and network analyses. These include large scale
computational logistics problems in freight transportation networks, and in energy distribution systems. Please contact us if you
have data that might be amenable to study using the sort of graph and network analysis techniques discussed here. You can also
**become involved** in this work as a student at the University of Hull either as an **undergraduate research intern**, or as a
**postgraduate/doctoral student** - there are suitable graph and network projects available at both levels.

The links below connect to Technical Notes or peer-reviewed and published articles on various areas of our graph-related research activities. Links are to abstracts and bibliographic details, and in most cases also link onwards to a full-PDF version of each article.

## Centrality and Applications- CSI-0002:
**Centrality Metrics for Identifying Network Fragility in Protein-Protein Interaction Networks and Synthesized NK Systems** - CSTN-158:
**Water Distribution Network Robustness and Fragmentation using Graph Metrics** - CSTN-152:
**Node-Failure and Islanding in National Grid Scale Electricity Distribution Networks** - CSTN-119:
**Betweenness Centrality Metrics for Assessing Electrical Power Network Robustness against Fragmentation and Node Failure**
## Circuits, loops and Applications- CSTN-046:
**Circuits, Attractors and Reachability in Mixed-K Kauffman Networks** - CSTN-013:
**Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs** - CSTN-003:
**Circuits as a Classifier for Small-World Network Models**
## Components and Communities- CSTN-089:
**Parallel Graph Component Labelling with GPUs and CUDA** - CSTN-083:
**Detecting and Labelling Wireless Community Network Structures from Eigen-spectra**
## Graph Visualisation- CSTN-061:
**Interactive Graph Algorithm Visualization and the GraViz Prototype** - Describes GraViz software, developed in Java, and some graph data formats, as well as some issues for visualising a complex graph in 2d.
## Spectral Graph Analysis Methods |
## Biological and Neural Applications- CSTN-149:
**Simulating Anaesthetic Effects on a Network of Spiking Neurons with Graphics Processing Units** - CSTN-136:
**Applying Enumerative, Spectral and Hybrid Graph Analyses to Biological Network Data**
## Small-World Graphs
GP-GPU and Multi-Core Architectures for Computing Clustering Coefficients of Irregular Graphs
Small-World Networks, Distributed Hash Tables and the e-Resource Discovery Problem in support of Global e-Science Infrastructure
A Small-World Network Model for Distributed Storage of Semantic Metadata
Small-World Effects in Wireless Agent Sensor Networks
## Graph Applications- CSTN-176:
**Analysing Spinodal Decomposition using Image Morphology with Thinning, Edge Detection and Graph Methods** - CSTN-030:
**Simulating Cooperating Localised Agents on Graphs** - CSTN-166:
**Fluent Interfaces and Domain-Specific Languages for Graph Generation and Network Analysis Calculations** - CSTN-126:
**Graph Generation on GPUs using Dynamic Memory Allocation** - CSTN-039:
**Simulating Large Random Boolean Networks**
## Graph Generation## Tools for Graph Perforemance and Scalability |