A study on matching algorithm in multilevel k-way for partitioning topology under the cognitive network environment

In order to study the cognitive networks, the multilevel k-way partitioning methods and the coarsening strategies for graphs are studied. The four kinds of classic matching algorithm used in the coarsening stage for multilevel k-way partitioning an irregular graph are introduced, including random matching, heavy-edge matching, improved heavy-edge matching, and light-edge matching algorithm. The basic idea and specific process of light-vertex matching algorithm are described, which is proposed for the features of network topology. In the case of that the weight of a vertex has positive correlation with the sum edges weight connected to, the light-vertex matching algorithm works better than the other algorithms on balance and edge cuttings. Furthermore, a method to improve light-vertex matching algorithm is proposed.