Random Graphs

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.




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


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




%d bloggers like this: