Detecting protein complexes in protein-protein interaction (PPI) networks plays a significant part in the bioinformatics field. It enables us to obtain a better understanding of the structures and characteristics of biological systems. In this study, we present a novel algorithm, named Improved Flower Pollination Algorithm (IFPA), to identify protein complexes in multi-relation reconstructed dynamic PPI networks. Specifically, we first introduce a concept called co-essentiality, which considers the protein essentiality to search essential interactions, Then, we devise the multi-relation reconstructed dynamic PPI networks (MRDPNs) and discover the potential cores of protein complexes in MRDPNs. Finally, an IFPA algorithm is put forward based on the flower pollination mechanism to generate protein complexes by simulating the process of pollen finding the optimal pollination plants, namely, attaching the peripheries to the corresponding cores. The experimental results on three different datasets (DIP, MIPS, and Krogan) show that our IFPA algorithm is more superior to some representative methods in the prediction of protein complexes. Our proposed IFPA algorithm is powerful in protein complex detection by building multi-relation reconstructed dynamic protein networks and using an improved flower pollination algorithm. The experimental results indicate that our IFPA algorithm can obtain better performance than other methods.