  For a prime $p$ we define the Paley graph to be the graph with the set of
vertices $\mathbb{Z}/p\mathbb{Z}$, and with edges connecting vertices whose sum
is a quadratic residue. Paley graphs are notoriously difficult to study,
particularly finding bounds for their clique numbers. For this reason, it is
desirable to have a random model. A well known result of Graham and Ringrose
shows that the clique number of the Paley graph is $\Omega(\log p\log\log\log
p)$ (even $\Omega(\log p\log\log p)$, under the generalized Riemann hypothesis)
for infinitely many primes $p$ -- a behaviour not detected by the random Cayley
graph which is hence deficient as a random model for for the Paley graph. In
this paper we give a new probabilistic model which incorporates some
multiplicative structure and as a result captures the Graham-Ringrose
phenomenon. We prove that if we sample such a random graph independently for
every prime, then almost surely (i) for infinitely many primes $p$ the clique
number is $\Omega(\log p\log\log p)$, whilst (ii) for almost all primes the
clique number is $(2+o(1))\log p$.
