| Multilevel algorithms on clustering algorithms aim both to improve clustering results and to reduce computational time. These algorithms conventionally consist of three main steps: coarsening, partitioning and decoarsening. The main focus of multilevel algorithms is on the coarsening step which finds groups of close nodes to merge. Each level completes by merging these groups and a series of levels are constructed until a small graph is generated. A clustering algorithm performs on this small graph in the partitioning step. While transferring the clustering results from the coarsest graph, a refining process is accompanied to improve the clustering results at each level of decoarsening.; The two main applications of multilevel algorithms are groups of documents and proteomic networks. Two applications contrast sharply in that the former ones are dense and weighted and the latter ones are sparse and unweighted. Therefore, different approaches on these applications are necessary.; The last part of thesis talks about Manufacturing Cell Formation Problem, which is described as finding an efficient block-diagonalization of an incidence matrix [parts x machines] corresponding to the global production system. We present a bipartite graph modeling on two disjoint components, parts and machines, with a graph clustering algorithm. Our algorithm generates fewer off-diagonal entries than previously proposed methods. Moreover, some practical constraints are satisfied with a few adjustments. |
