Automorphisms of a certain digraph defined on the set of primes? [Edited] Define a digraph $P=(V,E)$ with $V$ equal to the set of prime numbers and an arrow from $p$ to $q$ if $p|q-1$ (definition motivated by Pratt's primality certificates).
Does $P$ indeed admit only the trivial automorphism (as seems reasonable to guess)? 
Edit:  In light of Gjergji Zaimi's heuristic suggesting a very large automorphism group, perhaps the better question asks what can one say, otherwise unconditionally, about hypothetical nontrivial automorphisms of $P$ and the permutations of ${\Bbb N}$ that they induce.
 A: I would expect this digraph to have a lot of automorphisms, but I cannot prove it unconditionally.
First, notice that $2$ is the only prime with no incoming edges. The primes which have incoming edges only from $2$ are the Fermat primes. You can keep going defining new collection of primes with incoming edges from a specific set of primes that were already considered.
Here is a conjecture: For any primes $2=p_1\le p_2 \le \cdots \le p_k$ there are infinitely many primes $q$ so that $q=1+p_1^{a_1}\cdots p_k^{a_k}$. (This seems like a reasonable conjecture generalizing the infinitude of Fermat primes.)
Assuming this conjecture, for any collection of primes previously considered there is an infinite set of primes whose incoming edges come exactly from this set of primes. This implies that in this graph, for example, the Fermat primes can not be distinguished. But there are of course many more automorphisms.
I must say, however, that for all I know, there are only finitely many Fermat primes, or even better, for every set of primes $S$ there are only finitely many primes so that $q-1$ has $S$ as its set of prime factors. If, moreover, the number of such primes is distinct for ever $S$, then the graph turns out to be rigid (no automorphisms). But deciding unconditionally which is the case should be very hard.
