BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Cambridge Mathematics Placements Seminars
SUMMARY:Maximising nestedness in bipartite graphs - Benno
Simmons\, Dept. Zoology
DTSTART;TZID=Europe/London:20180130T130000
DTEND;TZID=Europe/London:20180130T140000
UID:TALK100732AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/100732
DESCRIPTION:"Bipartite graphs are graphs with two sets of vert
ices\, where edges are between sets but not within
sets. Bipartite graphs are widely used in a range
of disciplines outside mathematics\, such as in e
cology\, where they are used to represent interact
ions between species. For example\, the two sets o
f vertices could represent plant and pollinators r
espectively\, with edges representing which pollin
ators visit which plants. Alternatively\, the vert
ices could correspond to hosts and their parasites
\, with edges showing which hosts are parasitized
by which parasites.\n\nOne pattern widely found in
empirical ecological bipartite graphs is nestedne
ss. 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 ecosyste
m with three bees (X\, Y and Z) and three plants (
D\, E and F). Let’s say bee X visits 3 plants\; be
e Y visits 2 plants\; and bee Z visits 1 plant. Th
e system would be perfectly nested if bee X visits
D\, E and F\; bee Y visits D and E\; and bee Z vi
sits D. It is perfectly nested because X has all p
lants\, 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.\n\nVar
ious measures exist to calculate the level of nest
edness in a bipartite graph. However\, because nes
tedness is affected by the number of vertices (spe
cies) and the number of edges (interactions betwee
n species) in a bipartite graph\, it is necessary
to normalise nestedness values so that they can be
fairly compared between graphs.\n\nA recent paper
by Song et al (2017) proposed that values should
be normalised by expressing the nestedness of a gr
aph relative to the maximum possible nestedness th
at could be achieved in a graph with the same numb
er of vertices and edges i.e. nestedness_normalise
d = nestedness/max(nestedness). However\, the meth
ods proposed for calculating the maximum nestednes
s of a bipartite graph are very basic and extremel
y unlikely to find the true maximum nestedness (th
ey used a greedy algorithm). We were able to find
higher levels of nestedness than the algorithm pro
posed by Song et al\, using a more sophisticated a
lgorithm (simulated annealing). However\, this alg
orithm is a heuristic algorithm\, so we do not kno
w if the solutions are optimal\, or how far from o
ptimality they are. \n\nThe problem the student wo
uld work on is therefore: for a bipartite graph wi
th a given number of vertices in each set\, and a
given number of edges\, what is the maximum nested
ness that can be achieved\, given the constraint t
hat 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 m
ake ecological sense. Possible directions might in
clude exact algorithms (e.g. branch and bound)\, b
ut the student would be free to develop whatever m
ethods 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 w
rite this project up as a paper and submit it to a
peer-reviewed journal (with the student as an aut
hor). \n\nThe student would be based in the Conser
vation 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 ver
y available for any discussions or questions the s
tudent wants to have. I hosted my first student fr
om this programme last year\, and it went very wel
l – we have now written a paper based on the proje
ct (of which the student is an author)\, and are p
lanning to submit it in January 2018.\n\nAs well a
s being mathematically interesting\, this project
would would advance the field of ecology (and othe
r fields using bipartite networks)\, by improving
our understanding of ecosystems\, and could potent
ially inform biodiversity conservation. Additional
ly\, if the student finishes developing the method
s\, 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
CONTACT:Dr Vivien Gruar
END:VEVENT
END:VCALENDAR