Research Of Holographic Spectral Clustering Algorithm Used In Multi-scale Community Detection

Many kinds of complex networks exist in our daily life, which can be viewed as highly models of complex systems. With the deep research of complex networks, some common topological features of real networks were found by researchers, such as small-world,power law distributions of degree and community structure. Community structure that describes groups of nodes within which connections are relatively dense and between which they are sparser is one of the most important topological features of complex networks. So community detection in complex networks attracts many scholars' attention, Aiming at this issue, the main focuses of this thesis were as follows:1. Backgrounds and significance of community detection in complex networks were first introduced, then the classical algorithms for community detection were classified and the corresponding algorithm theories or ideological fundamentals were introduced. The advantages and disadvantages of spectral clustering algorithms and the applications of spectral clustering algorithms in community detection were especially analyzed.2. For the two problems of spectral clustering algorithm existed in community detection: (1)Only a part of eigenvectors of network matrix were used to cluster nodes in complex networks which resulted in not taking the whole topological structure of complex networks into consideration; (2) Computation complexity of matrix eigenvectors is high which made spectral clustering methods unsuitable in networks that contain thousands of nodes. Spectral clustering algorithm was dramatically improved in this paper, the improved algorithm was called holographic spectral clustering algorithm, in which all eigenvectors of network matrix were under consideration, and cosine similarity between nodes was converted according to Parseval Equation in spectral graph theory that left out the computation of matrix eigenvectors. In this way, computation complexity of this algorithm was reduced dramatically.3. Aiming at the issue that the importance of eigenvectors of network matrix is different for clustering nodes, a weighted function was introduced in this thesis. Not only the whole topological structure of networks, but the importance of eigenvectors was under consideration through weighting the eigenvectors by the weighted function. Otherwise, scale parameter was introduced to reflect the multi-scale feature of communities. Networks can be divided into communities at different scales by adjusting the scale parameter and controlling the weighted function for weighting eigenvectors.Experiment results indicated that, compared with spectral clustering algorithm,computation and memory complexity of holographic spectral clustering algorithm were reduced to linear level. Moreover, not only community structure can be detected effectively but multi-scale feature of communities can be reflected by holographic spectral clustering algorithm.