Finding　communities　in　networks　is　one　of　the　challenging　issues　in　complex　network　research.　We　have　to　deal　with　very　large　networks　that　contain　billions　of　vertices,　which　makes　community　discovery　a　computationally　intensive　work.　Moreover,　communities　usually　overlap　each　other,　which　greatly　increases　the　difficulty　of　identifying　the　boundaries　of　communities.　In　this　paper,　we　propose　a　parallel　multi-label　propagation　algorithm　(PMLPA)　that　enhances　traditional　multi-label　propagation　algorithm　(MLPA)　in　two　ways.　First,　the　critical　steps　of　MLPA　are　parallelized　based　on　the　MapReduce　model　to　get　higher　scalability.　Second,　new　label　updating　strategy　is　used　to　automatically　determine　the　most　valuable　labels　of　each　vertex.　Furthermore,　we　study　the　improvement　of　PMLPA　through　considering　the　influence　of　vertices　and　labels　on　label　updating.　In　this　way,　the　importance　of　each　label　can　be　described　with　higher　precision.　Experiments　on　artificial　and　real　networks　prove　that　the　proposed　algorithms　can　achieve　both　high　discovering　accuracy　and　high　scalability.　©　2017　World　Scientific　Publishing　Company.