Random networks in PPi
If your goal is only to account for degree distribution (i.e. Matteo Ferla's comment), a simulation approach you could use is:


measure the degree (number of links) of each protein in your PPI
find a large set of proteins that are equal or similar in degree to each of your proteins of interest (you may have to use a range of degrees to get a large enough set for comparison, ideally >=1000). We'll call these "comparable proteins" for each of your proteins of interest.
For each protein of interest, make all of your measurements also for its set of comparable proteins
Compare your measurement (shortest distance?) for the protein of interest to that for its comparable proteins. You could compute Z-scores from the parameters of the comparable protein distribution, or just empirical Monte Carlo p-values from where it falls in the distribution.


This will give you at least a heuristic null distribution for each protein. It should be relatively easy to code up in whatever your favorite language is.

Hope that helps-