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
Circuits, loops and Applications
Components and Communities
Spectral Graph Analysis Methods
Biological and Neural Applications
Tools for Graph Perforemance and Scalability