We study properties of random graphs within families of graphs equipped with a group law. The group structure enables one to perform a random walk on the family of graphs. If the generating system is a big enough random subset of graphs, a result of Alon--Roichman provides us with useful expansion properties well suited to give quantitative estimates for the rarefaction of non-typical elements attained by the random walk. Applying the general setting we show, e.g., that, with high probability (in a strong explicit sense), random graphs contain cycles of small length, or that a random coloring of the edges of a graph contains a monochromatic triangle.