What is the difference between Z-scores and p-values? In network motif algorithms, it seems quite common to return both a p-value and a Z-score for a statistic: "Input network contains X copies of subgraph G".  A subgraph is deemed a motif if it satisfies


*

*p-value < A,

*Z-score > B and

*X > C,
for some user-defined (or community-defined) A, B and C.


This motivates the question:

Question: What are the differences between p-value and Z-score?

And the subquestion:

Question: Are there situations where the p-value and Z-score of the same statistic might suggest opposite hypotheses?  Are the first and second conditions listed above essentially the same?

 A: A $Z$-score describes your deviation from the mean in units of standard deviation. It is not explicit as to whether you accept or reject your null hypothesis.
A $p$-value is the probability that under the null hypothesis we could observe a point that is as extreme as your statistic. This explicitly tells you whether you reject or accept your null hypothesis given a test size $\alpha$.
Consider an example where $X\sim \mathcal{N}(\mu,1)$ and the null hypothesis is $\mu=0$. Then you observe $x_1=5$. Your $Z$-score is 5 (which only tells you how far you deviate from your null hypothesis in terms of $\sigma$) and your $p$-value is 5.733e-7. For 95% confidence, you will have a test size $\alpha=0.05$ and since $p<\alpha$ then you reject the null hypothesis. But for any given statistic, there should be some equivalent $A$ and $B$ such that the tests are the same.
A: $p$-value indicates how unlikely the statistic is. $z$-score indicates how far away from the mean it is. There may be a difference between them, depending on the sample size. 
For large samples, even small deviations from the mean become unlikely. I.e. the $p$-value may be very small even for a low $z$-score. Conversely, for small samples even large deviations are not unlikely. I.e. a large $z$-score will not necessarily mean a small $p$-value.
A: I would say, based on your question, that there is no difference between the three tests.  This is in the sense that you can always choose A, B, and C such that the same decision is arrived at regardless of what criterion you are using.  Although you need to have the p-value be based on the same statistic (i.e. the Z-score)
To Use the Z-score, both the mean $\mu$ and variance $\sigma^2$ are assumed to be known, and the distribution is assumed normal (or asymptotically/approximately normal).  Suppose the p-value criterion is the usual 5%.  Then we have:
$$p=Pr(Z>z)<0.05\rightarrow Z>1.645\rightarrow \frac{X-\mu}{\sigma}>1.645\rightarrow X > \mu+1.645\sigma$$
So we have the triple $(0.05, 1.645, \mu+1.645\sigma)$ which all represent the same cut-offs.
Note that the same correspondence will apply to the t-test, although the numbers will be different.  The two tails test will also have a similar correspondence, but with different numbers.
