  Self-avoiding random walks were performed on protein residue networks.
Compared with protein residue networks with randomized links, the probability
of a walk being successful is lower and the length of successful walks shorter
in (non-randomized) protein residue networks. Fewer successful walks and
shorter successful walks point to higher communication specificity between
protein residues, a conceivably favourable attribute for proteins to have. The
use of random walks instead of shortest paths also produced lower node
centrality, lower edge betweeness and lower edge load for (non-randomized)
protein residue networks than in their respective randomized counterparts. The
implications of these properties for protein residue networks are discussed in
terms of communication congestion and network vulnerability. The randomized
protein residue networks have lower network clustering than the
(non-randomized) protein residue networks. Hence, our findings also shed light
on a hitherto neglected aspect: the importance of high network clustering in
protein residue networks. High clustering increases navigability of a network
for local search and the combination of a local search process on a highly
clustered small-world network topology such as protein residue networks reduces
communication congestion and network vulnerability.
