Recent advances in experimental techniques resulted in the accumulation of a vast amount of protein interaction information, which is routinely represented by protein interaction networks. Therefore it is not surprising that increasingly more complex graph-theoretical tools are deployed to analyze protein interaction graphs and extract biologically meaningful patterns.