A Novel Approach for Finding Clusters from Complex Networks

A feasible structural clustering method based on breadth-first-search is proposed for graphs. Clustering is very important and widely used in analyzing complex networks such as community identification. There are clusters with different shapes such as cliques and stars in practical application. Some existing algorithms can find clique-shaped clusters, but they are unable to identify star-shaped clusters that are familiar in scale free networks. A feasible solution is provided to solve the problem. It is superior to other algorithms in one or several of the following aspects: An algorithm without any input parameters, Running time on a network with n nodes and m links is O(n), Extracting clusters of mixed shapes.