Density set based detection of communities in social networks

Based on the definition of density set, an algorithm is proposed to detect communities in social networks. The ideal communities in network are extracted by a found node and its neighbors' information but not any global information from the whole community or network. The use of local information in the proposed algorithm directly leads to significant reduction of running time. The running time of the proposal is approximately O(n+m) for a general network and O(n) for a sparse network. Three typical real-world networks are selected to test the proposed algorithm and proper community partitions are obtained. So the proposal is reasonable, and has the potential for wide applications in data mining. PACS: 89.75.Hc; 05.10.-a; 87.23.Ge; 07.05.Mh.