University of Cambridge > > Probability > Hidden Ancestor Graphs with Assortative Vertex Attributes

Hidden Ancestor Graphs with Assortative Vertex Attributes

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Jason Miller.

Synthetic vertex-labelled graphs play a valuable role indevelopment and and testing of graph machine learning algorithms. The hidden ancestor graph is a new stochastic model for a vertex-labelled multigraph $G$ in which the observable vertices are the leaves $L$ of a random rooted tree $T$, whose edges and non-leaf nodes are hidden. The likelihood of an edge in $G$ between two vertices in $L$ depends on the height of their lowest common ancestor in $T$. The label of a vertex $v$ in $L$ depends on a randomized label inheritance mechanism within $T$ such that vertices with the same parent often have the same label. High label assortativity,high average local clustering, heavy tailed vertex degree distribution, and sparsity, can all coexist in this model. Subgraphs consisting of the agreement edges (end point labels agree), and the conflict edges (end point labels differ), respectively, play an important role in testing anomaly correction algorithms. Instances with a hundred million edges can be built in minutes on an average workstation with sufficient memory.

This talk is part of the Probability series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity