# Random Apollonian Networks

In this work, we analyze fundamental properties of Random Apollonian Networks, a popular random graph model which generates planar graphs with power law properties. Specifically, we analyze the following properties:

- the degree distribution,
- the largest degrees, the largest eigenvalues ( is a constant),
- the diameter.

## Code

## Paper

# Rainbow Connectivity

**Random regular graphs.** An edge colored graph is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph , denoted by , is the smallest number of colors that are needed in order to make rainbow connected. In this work we study the rainbow connection of the random -regular graph of order~, where is a constant. We prove that with probability tending to one as goes to infinity the rainbow connection of satisfies , which is best possible up to a hidden constant.

**Note**: The optimal result for 3-regular random graphs was proved by Michael Molloy.

**Random Erdős–Rényi graphs**. We prove optimal results for rainbow connectivity at the connectivity threshold.

## Papers

- Rainbow connectivity of sparse random graphs, by Andrzej Dudek, Alan Frieze, Charalampos E. Tsourakakis
- Rainbow Connectivity of Sparse Random Graphs, Alan Frieze, Charalampos E. Tsourakakis

# Motif Expanders

In our work “Scalable motif-aware community detection” we introduce the concept of triangle expanders, that serves as the theoretical basis of the theory behind motif based clustering.

# Streaming graph partitioning in the planted partition model