Abstract: One of statistical characteristics in complex networks is a community structure. Detecting communities in networks has aroused great interest among researches in recent years. Actually, community detection is very similar to the classical cluster analysis in machine learning field. Thus, the key point is how to define vertex similarities in complex networks. We first proposed an algorithm named SUN based on vertex similarities. Compared with UN, SUN is much better and faster than UN. Secondly, we used four classical clustering algorithms to detect community structure in networks based on some existing vertex similarity measures. I}he results on artificial networks and real social networks show that the similarity measures based on signal propagation and regular equivalence theory by using the whole topology structure of networks are better than the methods of Jaccard based on local vertex information. Therefore, if vertex similarities arc given well enough,proper clustering algorithms based on similarity matrices can be used to detect community structures fast and effectively in complex networks.

Key words: Complex network, Community structure, Affinity propagation, Signal propagation, Vertex similarity