An　algorithm　based　on　local　affinity　propagation　and　a　new　similarity　measure　concerning　user　profile　is　proposed.　On　one　hand,　by　loosening　the　exemplar　constraint　and　requiring　the　messages　propagate　around　a　node＇s　neighbors,　the　algorithm　achieves　lower　time　and　space　complexity　without　too　much　lost　in　clustering　accuracy,　which　makes　it　adaptable　to　the　mining　of　large-scale　social　networks.　On　the　other　hand,　by　designing　a　hybrid　similarity　measure　based　on　the　topological　similarity　and　the　profile　similarity　of　the　nodes,　the　algorithm　can　effectively　tackle　the　situation　of　the　social　networks　data　without　complete　user　relation　information.　The　experimental　results　on　the　artificial　datasets　and　the　real-world　datasets　demonstrate　that　the　algorithm　not　only　has　near-linear　time　complexity　and　linear　space　complexity,　but　also　retains　high　detecting　accuracy　when　handling　incomplete　networks.　©,　2015,　Tongxin　Xuebao/Journal　on　Communications.　All　right　reserved.