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.