CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graph Processes

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

Let $G$ be a random directed graph with given in- and out-degree sequence and $p\in[0,1]$. Delete each vertex (together with all incident edges) with probability $1-p$, independently of the other vertices and denote the resulting random graph by $G_p$. We present a threshold $p_c$ such that for $p>p_c$, $G_p$ asymptotically almost surely contains a strongly connected component of size $\Theta(n)$ and for $p<p_c$, asymptotically almost surely every strongly connected component of $G_p$ has size $O(\Delta^2\log(n))$, where $\Delta$ is the minimum of the maximum in-degree and maximum out-degree of $G$. (Joint work with Jane Gao.)

ABBAS MEHRABIAN, University of California Berkeley
The push\&pull protocol for rumour spreading  [PDF]

Consider a social network modelled as a graph, with people and friendships represented by vertices and edges, respectively. Suppose that a person knows a piece of information, and as time passes, talks to other people and spreads it. How long it takes until everyone knows the rumour? The answer, which we call the "spread time", certainly depends on the graph's structure and how the rumour spreads. In this talk we discuss two well known randomized rumour spreading protocols (known as push\&pull protocols) and prove several results on their spread times on various graphs.

Based on joint work with H. Acan, O. Angel, A. Collevecchio, Y. Peres, and N. Wormald.

RYAN MELVIN, Wake Forest University
Unifying proximity and clustering on networks  [PDF]

We introduce a unified and natural approach to clustering subsets of active (selected, occupied or infected, etc.) vertices within a graph. The method rests on a unifying, random walk based measure of distances between vertices that bridges the gap between community detection and clustering of subsets of interest. The important case of community detection is the limiting instance in which all vertices are considered active. Since we allow for selection of vertices of interest, the method can be applied to particular node types on multipartite graphs. In this presentation we emphasize the applicability of the approach to disease networks, epidemiology and biological networks.

JANE WODLINGER, University of Victoria
Minimum $k$-conversion sets in $(k+1)$-regular graphs  [PDF]

Imagine a disease that spreads through a population in discrete time steps according to the rule that an uninfected individual becomes permanently infected at time $t$ if at least $k$ of their contacts are infected at time $t - 1$. On a graph $G$, such a process is called an irreversible $k$-threshold conversion process, and a set $S$ of vertices is a $k$-conversion set of $G$ if the infection of these vertices at time $0$ results in the whole graph becoming infected eventually. We present new results on the size and structure of minimum $k$-conversion sets in $(k + 1)$-regular graphs. When restricted to these graphs, $k$-conversion sets are also known as feedback vertex sets and decycling sets.


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é Ryerson Office of Naval Research Science and Technology