BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Maximising nestedness in bipartite graphs - Benno Simmons\, Dept. 
 Zoology
DTSTART:20180130T130000Z
DTEND:20180130T140000Z
UID:TALK100732@talks.cam.ac.uk
CONTACT:Dr Vivien Gruar
DESCRIPTION:"Bipartite graphs are graphs with two sets of vertices\, where
  edges are between sets but not within sets. Bipartite graphs are widely u
 sed in a range of disciplines outside mathematics\, such as in ecology\, w
 here they are used to represent interactions between species. For example\
 , the two sets of vertices could represent plant and pollinators respectiv
 ely\, with edges representing which pollinators visit which plants. Altern
 atively\, the vertices could correspond to hosts and their parasites\, wit
 h edges showing which hosts are parasitized by which parasites.\n\nOne pat
 tern 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 v
 isits D and E\; and bee Z visits D. It is perfectly nested because X has a
 ll plants\, Y has a subset of X’s plants\, and Z has a subset of Y’s p
 lants. Nestedness arises due to a variety of ecological and evolutionary p
 rocesses\, and is a subject of much study in ecology.\n\nVarious measures 
 exist to calculate the level of nestedness in a bipartite graph. However\,
  because nestedness is affected by the number of vertices (species) and th
 e number of edges (interactions between species) in a bipartite graph\, it
  is necessary to normalise nestedness values so that they can be fairly co
 mpared between graphs.\n\nA recent paper by Song et al (2017) proposed tha
 t values should be normalised by expressing the nestedness of a graph rela
 tive to the maximum possible nestedness that could be achieved in a graph 
 with the same number of vertices and edges i.e. nestedness_normalised = ne
 stedness/max(nestedness). However\, the methods proposed for calculating t
 he maximum nestedness of a bipartite graph are very basic and extremely un
 likely to find the true maximum nestedness (they used a greedy algorithm).
  We were able to find higher levels of nestedness than the algorithm propo
 sed by Song et al\, using a more sophisticated algorithm (simulated anneal
 ing). However\, this algorithm is a heuristic algorithm\, so we do not kno
 w if the solutions are optimal\, or how far from optimality they are. \n\n
 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 constrai
 nt that each vertex must have at least one edge (i.e. each species must in
 teract with at least one other)? This constraint is necessary for the grap
 h to make ecological sense. Possible directions might include exact algori
 thms (e.g. branch and bound)\, but the student would be free to develop wh
 atever methods they thought were best. These methods would then be written
  into code (preferably R or MATLAB). If the project is successful\, the pl
 an is to write this project up as a paper and submit it to a peer-reviewed
  journal (with the student as an author). \n\nThe student would be based i
 n 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 wan
 ts 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 Januar
 y 2018.\n\nAs well as being mathematically interesting\, this project woul
 d would advance the field of ecology (and other fields using bipartite net
 works)\, by improving our understanding of ecosystems\, and could potentia
 lly inform biodiversity conservation. Additionally\, if the student finish
 es developing the methods\, there are a number of interesting questions th
 e student would be free to pursue using the newly developed methods."\n
LOCATION:MR3 Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR