University of Hull

CSRG - Graph Research


| CSI Technical Reports | Department of Computer Science | University of Hull |

Graphs and Networks

London Underground Graph

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.

Some Areas of Research Involving Graphs and Networks

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-0055: Computational Methods for Finding Long Cycles in Complex Networks

CSI-0026: Offshore Wind farm Network Connectivity Analysis and Optimisation using Graph Algorithms and Metrics

CSI-0015: Scaling Properties of Minimal Spanning Trees in Simulated Ad Hoc Wireless Networks

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

CSTN-068: Spectral Analysis of Attractors in Random Boolean Network Models
CSTN-051: Eigenvalue Spectra Measurements of Complex Networks

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

CSTN-117: GP-GPU and Multi-Core Architectures for Computing Clustering Coefficients of Irregular Graphs
CSTN-069: Small-World Networks, Distributed Hash Tables and the e-Resource Discovery Problem in support of Global e-Science Infrastructure
CSTN-064: A Small-World Network Model for Distributed Storage of Semantic Metadata
CSTN-001: 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

Graph Generation

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

Tools for Graph Perforemance and Scalability

CSTN-043: Exploring Data Structures and Tools for Computations on Graphs and Networks
CSTN-016: Performance, scalability and Object-Orientation in Discrete Graph-based Simulation Models
CSTN-021: Node Importance Ranking and Scaling Properties of some Complex Networks

| CSI Technical Reports | Ken Hawick | Department of Computer Science | University of Hull |