Haven't had a chance to read the paper yet (though I do like both number theory and network theory, so it'll be on my to-do list). But if anyone is interested in a probabilistic notion of primality, the best practical example out there is the Miller-Rabin test (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_...). This describes the function that sits behind most `is_prime()` methods that you'll find in technical computing libraries.
Fun fact: it becomes a deterministic test if the generalized Riemann hypothesis is ever proven.
That's not really the same sort of "probabilistic notion of primality". This isn't about a test for primality; this is about a probabilistic model of the primes, where we replace the actual primes by a randomly-generated subset of the natural numbers that we believe ought to have similar properties. The basic one is the Cramér model, where we say that n is prime with probability 1/(log n), and these are independent of one another. This is giving a more complicated such model which it claims agrees better with the statistics of the actual primes.
Another point of this model is, unlike Cramér's, it doesn't assume the prime number theorem as an entry point but rather displays it as a naturally derived property.
There's a different concept relating randomness and primes, and that's the model of the primes being distributed randomly. You can read more about that here:
Fun fact: it becomes a deterministic test if the generalized Riemann hypothesis is ever proven.