Study On Eigenvectors Selection Methods In Spectral Partitioning Algorithm

As information technology is developing at staggering rate, the scale of data increases sharply. Partitioning, which is prevalent in the procession of data analysis and knowledge discovery, has drawn extensive attention in many areas. As a basic data structure, graph is playing increasingly important role in modeling complex networks and their interactions. In order to achieve further analysis and deal with the internal relations and the meanings of these mass data, partitioning which based on the graph has become an attractive task in the field of data mining.Graph partition is a NP-complete problem. Some algorithms have already been discovered, however, these algorithms cannot keep pace with continuous expansion of the scale of the data and the emergence of the new problems. Recently, spectral partitioning algorithm has become one of the most popular partitioning algorithms. Compared with the traditional algorithms, it can be utilized in any of the sample space and converge to the global optimal solution, which could be treated as a good combination of the graph theory and spectral decomposition theory in the field of partition. There are many new algorithms and literatures have been published, and the main differences are the choice of the eigenvectors. In this paper, we will examine the eigenvectors selection in the spectral partitioning algorithm thereby illustrating the approach to chose the eigenvectors, and then deserve a good result in these graphs with different size and structure. We primarily explore the problem from the following three methods:(1) The Fiedler eigenvector; (2) The first k eigenvectors; (3) The relevant eigenvectors. Lastly, we will show the advantages and disadvantages of these three methods as well as their applications through a lot of experiments.