CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Probability and graphs

PETER BARR, Wake Forest University
A transport redundancy approach to clustering  [PDF]

In this talk, we consider a new random walks-based method for measuring clustering on finite graphs. The method is versatile and can provide valuable insight into the locations of centers of clusters and outliers. Some results and applications are discussed. This work is in collaboration with K. S. Berenhaut and M. Gao.

DANIELLE COX, Acadia University
The Average Reliability of a Graph  [PDF]

Let $G$ be a graph on $n$ vertices and $m$ edges. The all terminal reliability of $G$, Rel$(G,p)$, is the probability that at least a spanning tree is operational, given vertices always operate and edges operate independently with $p\in[0,1]$. It is known that most optimal graphs do not always exist. We will discuss a new measure of optimality, the average reliability of a graph $G$, avgRel$(G)$. This talk will examine properties of average reliability and for situations where most optimal graphs do not exist in the traditional sense, we will apply it to propose "good" graphs for network reliability.

ALESSANDRA GRAF, University of Waterloo
Percolation on random regular directed graphs  [PDF]

Let $G$ be a random $d$-regular directed graph (i.e. the in-degree and out-degree of every vertex is $d$) and $p\in[0,1]$. Delete each vertex (together with all incident edges) with probability $1-p$, independently of the other vertices. We denote the resulting random graph by $G_p$. We prove that for $p>(1+\epsilon)\frac{1}{d}$, $G_p$ asymptotically almost surely contains a strongly connected subgraph of size $\Omega(n)$. Also, for $p<(1-\epsilon)\frac{1}{d}$, asymptotically almost surely every strongly connected subgraph of $G_p$ has size $O(\log(n))$. Joint work with Jane Gao.

ABBAS MEHRABIAN, Pacific Institute for the Mathematical Sciences
Rumour spreading in the SPA model  [PDF]

The Spatial Preferential Attachment model is a spatial random graph used to model social networks. Nodes live in a metric space, and edges are formed based on the metric distance and degree of the nodes. Rumour spreading is a protocol for the spread of information through a graph. In each time step nodes can pass the rumour to only one of their neighbours. The spread time is the expected time when all nodes have the rumour. We analyze rumour spreading on the SPA model, and show that the spread time differs substantially from the diameter. Joint work with Jeannette Janssen.

CHRISTOPHER ROSS, St. Catherine University
Firefighter on Random Threshold Graphs  [PDF]

We investigate the firefighter problem on random threshold graphs, constructed by randomly assigning each vertex $v$ a weight $w(v) \in [0,1]$, and adding an edge between distinct vertices $u$ and $v$ if and only if $w(u)+w(v)>1$. With an optimal strategy for firefighter on these threshold graphs, we found the distribution and expectation for the maximum number of saved vertices, as well as the number of firefighters required to save a given fraction of the vertex set. (Joint work with Rose Winter.)


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan