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.
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.
- 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
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