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:Probability
SUMMARY:Hidden Ancestor Graphs with Assortative Vertex Att
ributes - Richard Darling (NSA)
DTSTART;TZID=Europe/London:20220906T150000
DTEND;TZID=Europe/London:20220906T160000
UID:TALK178478AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/178478
DESCRIPTION:Synthetic vertex-labelled graphs play a valuable r
ole indevelopment and and testing of graph machine
learning algorithms. The hidden ancestor graph i
s a new stochastic model for a vertex-labelled mul
tigraph $G$ in which the observable vertices are t
he leaves $L$ of a random rooted tree $T$\, whose
edges and non-leaf nodes are hidden. The likelihoo
d of an edge in $G$ between two vertices in $L$ de
pends on the height of their lowest common ancesto
r in $T$. The label of a vertex $v$ in $L$ depends
on a randomized label inheritance mechanism withi
n $T$ such that vertices with the same parent ofte
n have the same label. High label assortativity\,h
igh average local clustering\, heavy tailed vertex
degree distribution\, and sparsity\, can all coex
ist in this model. Subgraphs consisting of the agr
eement edges (end point labels agree)\, and the co
nflict edges (end point labels differ)\, respectiv
ely\, play an important role in testing anomaly co
rrection algorithms. Instances with a hundred mill
ion edges can be built in minutes on an average wo
rkstation with sufficient memory.
LOCATION:MR9\, Centre for Mathematical Sciences
CONTACT:Jason Miller
END:VEVENT
END:VCALENDAR