Random Apollonian Networks

Simulation of a Random Apollonian Networks (RANs)

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 $k$ largest degrees, the $k$ largest eigenvalues ( $k$ is a constant),
the diameter.

Code

Paper

Rainbow Connectivity

Random regular graphs. An edge colored graph $G$ 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 $G$ , denoted by $rc(G)$ , is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$ -regular graph $G=G(n,r)$ of order~ $n$ , where $r\ge 4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(\log n)$ , 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

Random Graphs