<p>Groups of two or more proteins interacting to form protein complexes are essential for cellular activity. Despite their importance, our knowledge of these complexes remains limited, underscoring the demand for robust detection methods in bioinformatics. However, accurately identifying these complexes is challenging because of the complex and dynamic structure of protein–protein interaction (PPI) networks, compounded by the asymmetric nature of protein interactions; this feature is often overlooked in conventional PPI network analyses. In this article, we present two variants of the (Mutually Dependent Star (mDepStar) method. The method uses asymmetric relationships between pairs of proteins to detect protein complexes around a single (core) protein from its local interactions. The modified local variant of the mDepStar method eliminates the need to use the information obtained from the whole network analysis. We evaluated the performance of mDepStar on two established PPI networks and three newly constructed networks for Saccharomyces cerevisiae and humans using the BioGRID and STRING databases. In addition, we created new Gene Ontology (GO)-based references. Using a combination of two sets of measures, mostly known and partly proposed by us, together with GO pair similarity, our results show that mDepStar consistently outperforms seven state-of-the-art methods, providing a more accurate and reliable tool for protein complex detection. To further refine our understanding of the methods, we examined their key features, identifying those that yielded the best results. These insights provide guidance for improving detection methods.</p>