Community-finding Algorithm In Complex Networks Based On Spectral Clustering

Complex network is one of the important tools and models to study complexsystems. And it has one remarkable topological property--Communities. Findingcommunity structures in complex networks is of more important significance, such asfor analyzing the compose of networks, and exploring the behavior of networks.However, finding correspond community structures in complex networks becomesmore difficult with large-scale and complex characteristics.In this paper, by analyzing and researching the theory of spectral clustering andthe concept of modularity function, the characteristics and advantages of them areachieved which are of in finding community structures in complex networks. By acombination of both, a new algorithm to find out community structure in network hasbeen proposed in this paper. The algorithm can divide into two stages: The first stage isdesigning the strategy of community partition, which takes the similarity matrix as thefeature of community, extracting the data features and measuring the similaritycombined by Floyd-Warshall algorithm. In the second stage, Finding-communitystructure algorithm is presented, sample data sets are handled with spectral clustering,finally several community structure are found, afterwards, with the measurement ofmodular function Q, the maximum of modularity is chosen to be the output. Further on,in this algorithm, the process of k-means which is a traditional clustering method ischanged with the thought of triangle equality, which increased the operating efficiencyobviously.The experiment on three classical social networks shows that thefinding-community structure algorithm based on spectral clustering can get moreefficiency on time complexity and the quality of community structure compared withtraditional ones.