The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

Many problems appearing in scientific computing and other areas can be formulated as a graph partitioning problems. Examples include data distribution for parallel computers, decomposition of sparse matrices and VLSI-design. In this survey we present the graph partitioning problem, describe some applications and introduce many of the algorithms used to solve the problem.

Many problems appearing in scientific computing and other areas can be formulated as a graph partitioning problems. Examples include data distribution for parallel computers, decomposition of sparse matrices and VLSI-design. In this survey we present the graph partitioning problem, describe some applications and introduce many of the algorithms used to solve the problem.

O grande volume de dados armazenados em meio digital dificulta a anáalise e extração de informações por um ser humano sem que seja utilizada alguma ferramenta computacional inteligente. A área de Aprendizado de Máquina (AM) estuda e desenvolve algoritmos para o processamento e obtenção automática de conhecimento em dados digitais. Tradicionalmente, os algoritmos de AM modelam os dados analisados com base na abordagem proposicional; entretanto, recentemente com a disponibilidade de conjuntos de dados relacionais novas abordagens têm sido estudadas, como a modelagem utilizando redes complexas. Redes complexas é uma área de pesquisa recente e ativa que têm atraíido a atenção de pesquisadores e tem sido aplicada em diversos domínios. Mais especificamente, o estudo de detecção de comunidades em redes complexas é o tema principal deste trabalho. Detectar comunidades consiste em buscar grupos de vértices densamente conectados entre si em uma rede. Detectar a melhor divisão em comunidades de uma rede é um problema NP-completo, o que requer que o desenvolvimento de soluções viáveis baseiem-se em heurísticas como, por exemplo, medidas de qualidade. Newman prop^os a medida de modularidade Q que tem se mostrado eficiiente na análise de comunidades em redes. Este trabalho apresenta o Algoritmo Multinível de Otimização de Modularidade (AMOM) que é baseado a na otimização da medida de modularidade e integrado na estratégia multinível. A estratégia multinível é composta de três fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fus~oes de vértices, (ii) particionamento da rede reduzida utilizando Algoritmo de Otimização de Modularidade (AOM) modificado, e (iii) sucessivas descompactações das redes intermediárias até que se retorne a rede inicial. O principal atrativo da estratégia é viabilizar a utilização de algoritmos custosos no particionamento do grafo compactado, uma vez que neste grafo a quantidade de vértices e arestas é uma fração reduzida em relação ao grafo inicial. O trabalho também propõe dois novos métodos para refinamento dos particionamentos durante a fase de uncoasening. A fiim de avaliar a escalabilidade e eficiiência da metodologia proposta foram realizados experimentos empíricos em redes consideradas benchmark. Os resultados demonstram um significativo ganho de desempenho, mantendo bons resultados qualitativos / Human based analysis of large amount of data is a hard task when no intelligent computer aid is provided. In this context, Machine Learning (ML) algorithms are aimed at automatically processing and obtaining knowledge from data. In general, ML algorithms use a propositional representation of data such as an attribute-value table. However, this model is not suitable for relational information modeling, which can be better accomplished using graphs or networks. In this context, complex networks have been call attention of scientific community recently and many applications in different domains have been developed. In special, one of complex networks research trends is the community detection field which is the main focus of this work. Community detection is the problem of finding dense and disjoint connected groups of vertices in a network. The problem is a well know NP-complete task which requires heuristics approaches, like quality measures, to be addressed. Newman introduced a specific quality measure called modularity that proved to be useful for analysis communities in networks. This work presents a new algorithm, called Multilevel Modularity Optimization Algorithm, based on modularity measure optimization integrated in a multilevel graph partitioning strategy. The multilevel graph partitioning scheme consists of three phases: (i) reduction of the size (coarsen) of original graph by collapsing vertices and edges, (ii) partitioning the coarsened graph, and (iii) uncoarsen it to construct a partition for the original graph. The rationale behind this strategy is to apply a computationally expensive method in a coarsened graph, i.e., with a significantly reduced number of vertices and edges. In addition, it is proposed two new methods that uses modularity and clustering coefficient for partition refinement. Empirical evaluation on benchmarks networks using this approach demonstrate a significant speed up gain compared to the original modularity-based algorithm, keeping a good quality clusters partitioning

O grande volume de dados armazenados em meio digital dificulta a anáalise e extração de informações por um ser humano sem que seja utilizada alguma ferramenta computacional inteligente. A área de Aprendizado de Máquina (AM) estuda e desenvolve algoritmos para o processamento e obtenção automática de conhecimento em dados digitais. Tradicionalmente, os algoritmos de AM modelam os dados analisados com base na abordagem proposicional; entretanto, recentemente com a disponibilidade de conjuntos de dados relacionais novas abordagens têm sido estudadas, como a modelagem utilizando redes complexas. Redes complexas é uma área de pesquisa recente e ativa que têm atraíido a atenção de pesquisadores e tem sido aplicada em diversos domínios. Mais especificamente, o estudo de detecção de comunidades em redes complexas é o tema principal deste trabalho. Detectar comunidades consiste em buscar grupos de vértices densamente conectados entre si em uma rede. Detectar a melhor divisão em comunidades de uma rede é um problema NP-completo, o que requer que o desenvolvimento de soluções viáveis baseiem-se em heurísticas como, por exemplo, medidas de qualidade. Newman prop^os a medida de modularidade Q que tem se mostrado eficiiente na análise de comunidades em redes. Este trabalho apresenta o Algoritmo Multinível de Otimização de Modularidade (AMOM) que é baseado a na otimização da medida de modularidade e integrado na estratégia multinível. A estratégia multinível é composta de três fases: (i) sucessivas compactações da rede inicial com base em contrações de arestas e fus~oes de vértices, (ii) particionamento da rede reduzida utilizando Algoritmo de Otimização de Modularidade (AOM) modificado, e (iii) sucessivas descompactações das redes intermediárias até que se retorne a rede inicial. O principal atrativo da estratégia é viabilizar a utilização de algoritmos custosos no particionamento do grafo compactado, uma vez que neste grafo a quantidade de vértices e arestas é uma fração reduzida em relação ao grafo inicial. O trabalho também propõe dois novos métodos para refinamento dos particionamentos durante a fase de uncoasening. A fiim de avaliar a escalabilidade e eficiiência da metodologia proposta foram realizados experimentos empíricos em redes consideradas benchmark. Os resultados demonstram um significativo ganho de desempenho, mantendo bons resultados qualitativos / Human based analysis of large amount of data is a hard task when no intelligent computer aid is provided. In this context, Machine Learning (ML) algorithms are aimed at automatically processing and obtaining knowledge from data. In general, ML algorithms use a propositional representation of data such as an attribute-value table. However, this model is not suitable for relational information modeling, which can be better accomplished using graphs or networks. In this context, complex networks have been call attention of scientific community recently and many applications in different domains have been developed. In special, one of complex networks research trends is the community detection field which is the main focus of this work. Community detection is the problem of finding dense and disjoint connected groups of vertices in a network. The problem is a well know NP-complete task which requires heuristics approaches, like quality measures, to be addressed. Newman introduced a specific quality measure called modularity that proved to be useful for analysis communities in networks. This work presents a new algorithm, called Multilevel Modularity Optimization Algorithm, based on modularity measure optimization integrated in a multilevel graph partitioning strategy. The multilevel graph partitioning scheme consists of three phases: (i) reduction of the size (coarsen) of original graph by collapsing vertices and edges, (ii) partitioning the coarsened graph, and (iii) uncoarsen it to construct a partition for the original graph. The rationale behind this strategy is to apply a computationally expensive method in a coarsened graph, i.e., with a significantly reduced number of vertices and edges. In addition, it is proposed two new methods that uses modularity and clustering coefficient for partition refinement. Empirical evaluation on benchmarks networks using this approach demonstrate a significant speed up gain compared to the original modularity-based algorithm, keeping a good quality clusters partitioning