Abstract

“Bipartite graphs are graphs with two sets of vertices, where edges are between sets but not within sets. Bipartite graphs are widely used in a range of disciplines outside mathematics, such as in ecology, where they are used to represent interactions between species. For example, the two sets of vertices could represent plant and pollinators respectively, with edges representing which pollinators visit which plants. Alternatively, the vertices could correspond to hosts and their parasites, with edges showing which hosts are parasitized by which parasites.

One pattern widely found in empirical ecological bipartite graphs is nestedness. A bipartite graph is nested when vertices with few edges have a subset of the edges of vertices with more edges. For example, imagine an ecosystem with three bees (X, Y and Z) and three plants (D, E and F). Let’s say bee X visits 3 plants; bee Y visits 2 plants; and bee Z visits 1 plant. The system would be perfectly nested if bee X visits D, E and F; bee Y visits D and E; and bee Z visits D. It is perfectly nested because X has all plants, Y has a subset of X’s plants, and Z has a subset of Y’s plants. Nestedness arises due to a variety of ecological and evolutionary processes, and is a subject of much study in ecology.

Various measures exist to calculate the level of nestedness in a bipartite graph. However, because nestedness is affected by the number of vertices (species) and the number of edges (interactions between species) in a bipartite graph, it is necessary to normalise nestedness values so that they can be fairly compared between graphs.

A recent paper by Song et al (2017) proposed that values should be normalised by expressing the nestedness of a graph relative to the maximum possible nestedness that could be achieved in a graph with the same number of vertices and edges i.e. nestedness_normalised = nestedness/max(nestedness). However, the methods proposed for calculating the maximum nestedness of a bipartite graph are very basic and extremely unlikely to find the true maximum nestedness (they used a greedy algorithm). We were able to find higher levels of nestedness than the algorithm proposed by Song et al, using a more sophisticated algorithm (simulated annealing). However, this algorithm is a heuristic algorithm, so we do not know if the solutions are optimal, or how far from optimality they are.

The problem the student would work on is therefore: for a bipartite graph with a given number of vertices in each set, and a given number of edges, what is the maximum nestedness that can be achieved, given the constraint that each vertex must have at least one edge (i.e. each species must interact with at least one other)? This constraint is necessary for the graph to make ecological sense. Possible directions might include exact algorithms (e.g. branch and bound), but the student would be free to develop whatever methods they thought were best. These methods would then be written into code (preferably R or MATLAB ). If the project is successful, the plan is to write this project up as a paper and submit it to a peer-reviewed journal (with the student as an author).

The student would be based in the Conservation Science Group in the Department of Zoology, but we can be very flexible if the student wants to work remotely. As a supervisor, I will be very available for any discussions or questions the student wants to have. I hosted my first student from this programme last year, and it went very well – we have now written a paper based on the project (of which the student is an author), and are planning to submit it in January 2018.

As well as being mathematically interesting, this project would would advance the field of ecology (and other fields using bipartite networks), by improving our understanding of ecosystems, and could potentially inform biodiversity conservation. Additionally, if the student finishes developing the methods, there are a number of interesting questions the student would be free to pursue using the newly developed methods.”