As a well-known clustering algorithm, Markov Clustering (MCL) has been used in many areas due to its simplicity and the ability to detect a cluster of different sizes and shapes for example clustering in bioinformatics. MCL shows good performance as a fast and scalable unsupervised cluster algorithm for graphs. However, a limitation of MCL is that the clustering results are mostly dependent on its inflation parameter whose value is user specified. In this paper, we develop a new method named as PIO-MCL to detected protein-protein interaction network by using Pigeon-Inspired Optimization (PIO) Algorithm to optimize the parameter of inflating operator in MCL algorithm. The experiments on PPI dataset show that PIO-MCL outperforms the state of the art method for clustering protein-protein interaction in terms of several criteria.