Inferring topology from clustering coefficients in protein-protein interaction networks

Background: Although protein-protein interaction networks
determined with high-throughput methods are incomplete, they are
commonly used to infer the topology of the complete interactome.
These partial networks often show a scale-free behavior with only a
few proteins having many and the majority having only a few
connections. Recently, the possibility was suggested that this
scale-free nature may not actually reflect the topology of the
complete interactome but could also be due to the error proneness
and incompleteness of large-scale experiments. Results: In this
paper, we investigate the effect of limited sampling on average
clustering coefficients and how this can help to more confidently
exclude possible topology models for the complete interactome. Both
analytical and simulation results for different network topologies
indicate that partial sampling alone lowers the clustering
coefficient of all networks tremendously. Furthermore, we extend
the original sampling model by also including spurious interactions
via a preferential attachment process. Simulations of this extended
model show that the effect of wrong interactions on clustering
coefficients depends strongly on the skewness of the original
topology and on the degree of randomness of clustering coefficients
in the corresponding networks. Conclusion: Our findings suggest
that the complete interactome is either highly skewed such as e.g.
in scale-free networks or is at least highly clustered. Although
the correct topology of the interactome may not be inferred beyond
any reasonable doubt from the interaction networks available, a
number of topologies can nevertheless be excluded with high
confidence.