Identifying protein complexes in protein-protein interaction (PPI) networks is a fundamental problem in computational biology. High-throughput experimental techniques have generated large, experimentally detected PPI datasets. These interactions represent a rich source of data that can be used to detect protein complexes; however, such interactions contain much noise. Therefore, these interactions should be validated before they could be applied to detect protein complexes. We propose an efficient measure to estimate PPI reliability (PPIR) and reduce noise level in two different yeast PPI networks. PPIRU, which is a new protein complex clustering algorithm based on PPIR, is introduced. Experiments demonstrated that interactome graph weighting methods incorporating PPIR clearly improve the results of several clustering algorithms. PPIR also outperforms other PPI graph weighting schemes in most cases. We compare PPIRU with several efficient, existing clustering algorithms and reveal that the accuracy values of PPIRU clusters are much higher than those of other algorithms.