Mining functional modules with biological significance has attracted lots of attention recently. However, protein-protein interaction (PPI) network and other biological data generally bear uncertainties attributed to noise, incompleteness and inaccuracy in practice. In this paper, we focus on received PPI data with uncertainties to explore interesting protein complexes. Moreover, some novel conceptions extended from known graph conceptions are used to develop a depth-first algorithm to mine protein complexes in a simple uncertain graph. Our experiments take protein complexes from MIPS database as standard of accessing experimental results. Experiment results indicate that our algorithm has good performance in terms of coverage and precision. Experimental results are also assessed on Gene Ontology (GO) annotation, and the evaluation demonstrates proteins of our most acquired protein complexes show a high similarity. Finally, several experiments are taken to test the scalability of our algorithm. The result is also observed.