Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-03-11T13:49:02Z No. of bitstreams: 2 Dissertação JOAO Emanoel Gomes.pdf: 2503585 bytes, checksum: da1614178e044688f1ee5fe198272497 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Approved for entry into archive by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-03-13T12:59:43Z (GMT) No. of bitstreams: 2 Dissertação JOAO Emanoel Gomes.pdf: 2503585 bytes, checksum: da1614178e044688f1ee5fe198272497 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T12:59:43Z (GMT). No. of bitstreams: 2 Dissertação JOAO Emanoel Gomes.pdf: 2503585 bytes, checksum: da1614178e044688f1ee5fe198272497 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-07-17 / Com o crescimento das redes sociais, diversas pesquisas vêm sendo realizadas para entendimento de suas estruturas. A detecção de comunidades nessas redes é importante para verificar especificidades que motivaram o agrupamento de usuários. Caracterizar comunidades pode auxiliar no entendimento das estruturas sociais existentes, como também na visualização, navegação e análise da rede. Caracterizar grupos em redes sociais no contexto educacional, denominadas Redes Sociais Educacionais (RSE), possibilita o fornecimento de conteúdos adaptáveis e um aprendizado direcionado aos grupos, auxiliando ainda, a tomada de decisão por parte de gestores e professores. As principais abordagens para caracterização de grupos são as baseadas em agregação e diferenciação. No entanto, relatos encontrados na literatura, indicam que os melhores perfis caracterizadores de grupos são obtidos por métodos baseados em diferenciação. Dessa maneira, este trabalho tem como objetivo avaliar a aplicação do teste estatístico Wilcoxon Rank Sum como método baseado em diferenciação para a caracterização de grupos em redes sociais. A partir dos atributos individuais dos usuários e comunidades identificadas, o método proposto busca caracterizar os grupos verificando características comuns que os diferenciem do restante da rede. Para avaliar o método proposto, foi realizado um estudo de caso com duas RSEs: as Olimpíadas de Jogos Digitais e Educação de Pernambuco (OJE-PE) e Acre (OJE-AC). Conforme verificado nos experimentos realizados, foram obtidos resultados promissores, dentre os quais se destacam a identificação de características descritivas para 80% dos grupos da rede OJE-PE e 70% para a OJE-AC.

O crescimento constante dos dados musicais na Internet tem encorajado diversos pesquisadores a desenvolver ferramentas adequadas para a análise e a classificação destes dados. O objetivo principal de tais ferramentas é extrair a informação de forma compacta e representativa ao conteúdo dos bancos de dados. Dentro deste contexto, os gêneros musicais apresentam descrições importantes para o desenvolvimento destas ferramentas. Além dos mesmos serem usados frequentemente para organizar coleções musicais e refletirem a interação ente culturas, resumem características (padrões) comuns entre as peças musicais. Em face ao exposto, a principal motivação deste projeto de pesquisa é propor uma maneira original, e de baixo esforço computacional, para representar os gêneros musicais e investigar a contribuição desta representação em aplicações e estudos que estão inseridos no contexto de pesquisas que envolvem a recuperação da informação musical. A representação proposta refere-se aos padrões rítmicos das músicas, uma vez que o ritmo configura um aspecto musical significante na discriminação dos gêneros. Os padrões rítmicos são estabelecidos pela dependência temporal das notas musicais presentes na percussão, de forma que cada música é representada por um vetor de probabilidades condicionais entre pares e trios de notas computadas pelo uso de cadeias de Markov de primeira e segunda ordem. Os padrões rítmicos de diversos gêneros são explorados em aplicações como: classificação, síntese musical, recomendação musical, humor/emoção em música, e análise de aspectos evolutivos. Constatou-se que estes, como estabelecidos neste estudo, são sensíveis à discriminação dos gêneros, evidenciando sequências de notas que são comuns aos mesmos, e sequências que são distintas e características de cada um. Uma segunda motivação deste projeto é o uso de medidas topológicas de redes e dígrafos de músicas para a análise dos dados. Comunidades obtidas nestas redes proporcionaram a definição de uma abordagem não supervisionada, a qual apresentou taxas de desempenho superiores ao agrupamento hierárquico. A determinação das características rítmicas de cada música motivou o desenvolvimento de estratégias para a composição automática e para a geração de listas de reprodução, assim como para a averiguação da relação destes padrões com aspectos emotivos. Por fim, uma análise estatística da evolução do ritmo de diferentes gêneros é desempenhada, na qual verificou-se a presença de mecanismos de inovação e recuperação. Estes mecanismos parecem ser consequência da competição entre fatores que favorecem a inovação de material musical, e fatores que a previnem, como, por exemplo, a obediência às regras de composição que mantém as características fundamentais de cada gênero. / Musical databases have increased in number and size continuously, paving the way to large amounts of online music data, including discographies, biographies and lyrics. The constant growth of data on the Internet has attracted musical research for developing tools to analyze and classify music data. The main objective of such tools is to extract reliable information to adequately represent and compact music content in databases. In this context, musical genres are particularly interesting descriptors, since they have being used for years to organize music collections, reflect interaction between cultures and summarize common features (or patterns) between musical pieces. The main motivation of this study is to propose a original and low cost framework to represent musical genres, as well as investigate the contribution of this representation in applications and studies that are placed in the context of music information retrieval researches. The representation of music content is referred to the rhythmic patterns, since rhythm configures a significant aspect in the discrimination of musical genres. The rhythmic patterns are determined by the temporal dependency of the musical notes present in the percussion, so that each song is represented by a vector of conditional probabilities between pairs and triples of notes, computed by the use of first and second order Markov chains. The rhythm patterns from distinct genres are investigated in applications such as: classification, music synthesis, music recommendation, mood/emotion in music, and analysis of evolutionary aspects. The main finding is that the rhythmic patterns as established in this study are sensitive to the genre discrimination, suggesting that there are sequences of notes common to all genres, and sequences that are distinct and characteristics of each one. A second motivation for this study is the use of topological measures of music networks and music digraphs for the data analysis. Communities obtained from these networks contributed to the definition of an unsupervised approach that provided performance rates superior to the hierarchical clustering. The rhythmic patterns also motivated the development of strategies for automatic composition, for the generation of playlists, and the analysis of the relationship between these patterns and emotional aspects. Finally, a statistical analysis of the rhythm evolution is performed, in which the principal finding is the presence of innovation and retrieval mechanisms for all genres. These mechanisms seems to be the result of the competition between factors that promote the innovation, and factors that prevent it, as, for example, the obedience to composition rules that retains the fundamental characteristics of each genre.

Diferentes sistemas do mundo real podem ser representados por redes. As redes são estruturas nas quais seus vértices (nós) representam entidades e links representam relações entre essas entidades. Além disso, as redes caracterizam-se por ser estruturas dinâmicas, o que implica na rápida aparição e desaparição de entidades e seus relacionamentos. Nesse cenário, um dos problemas importantes a serem enfrentados no contexto das redes, é da predição de links, isto é, prever a ocorrência futura de um link ainda não existente entre dois vértices com base nas informações já existentes. A importância da predição de links deve-se ao fato de ter aplicações na recuperação de informação, identificação de interações espúrias e, ainda, na avaliação de mecanismos de evolução das redes. Para enfrentar o problema da predição de links, a maioria dos métodos utiliza informações da vizinhança topológica das redes para atribuir um valor que represente a probabilidade de conexão futura entre um par de vértices analisados. No entanto, recentemente têm aparecido métodos híbridos, caracterizados por usar outras informações além da vizinhança topológica, sendo as informações das comunidades as normalmente usadas, isso, devido ao fato que, ao serem grupos de vértices densamente ligados entre si e esparsamente ligados com vértices de outros grupos, fornecem informações que podem ser úteis para determinar o comportamento futuro das redes. Assim, neste trabalho são apresentadas duas propostas na linha dos métodos baseados nas informações das comunidades para predição de links. A primeira proposta consiste em um novo índice de similaridade que usa as informações dos vértices pertencentes a mesma comunidade na vizinhança de um par de vértices analisados, bem como as informações dos vértices pertencentes a diferentes comunidades nessa mesma vizinhança. A segunda proposta consiste de um conjunto de índices obtidos a partir da reformulação de algumas propostas já existentes, porém, inserindo neles informações dos vértices pertencentes unicamente à mesma comunidade na vizinhança topológica de um par de vértices analisados. Experimentos realizados em dez redes complexas de diferentes domínios demonstraram que, em geral, os índices propostos obtiveram desempenho superior às abordagens usuais / Different real-world systems can be represented as networks. Networks are structures in which vertices (nodes) represent entities and links represent relationships between these entities. Moreover, networks are dynamic structures, which implies rapid appearance and disappearance of entities and their relationships. In this scenario, the link prediction problem attempts to predict the future existence of a link between a pair of vertices considering existing information. The link prediction importance is due to the fact of having different applications in areas such as information retrieval, identification of spurious interactions, as well as for understanding mechanisms of network evolution. To address the link prediction problem, many proposals use topological information to assign a value that represents the likelihood of a future connection between a pair of vertices. However, hybrid methods have appeared recently. These methods use additional information such as community information. Communities are groups of vertices densely connected among them and sparsely connected to vertices from other groups, providing useful information to determinate the future behavior of networks. So, this research presents two proposals for link prediction based on communities information. The first proposal consists of a new similarity index that uses information about the communities that the vertices in the neighborhood of a analyzed pair of vertices belong. The second proposal is a set of indices obtained from the reformulation of various existing proposals, however, using only the information from vertices belonging to the same community in the neighborhood of a pair of vertices analyzed. Experiments conducted in ten complex networks of different fields show the proposals outperform traditional approaches

O crescimento constante dos dados musicais na Internet tem encorajado diversos pesquisadores a desenvolver ferramentas adequadas para a análise e a classificação destes dados. O objetivo principal de tais ferramentas é extrair a informação de forma compacta e representativa ao conteúdo dos bancos de dados. Dentro deste contexto, os gêneros musicais apresentam descrições importantes para o desenvolvimento destas ferramentas. Além dos mesmos serem usados frequentemente para organizar coleções musicais e refletirem a interação ente culturas, resumem características (padrões) comuns entre as peças musicais. Em face ao exposto, a principal motivação deste projeto de pesquisa é propor uma maneira original, e de baixo esforço computacional, para representar os gêneros musicais e investigar a contribuição desta representação em aplicações e estudos que estão inseridos no contexto de pesquisas que envolvem a recuperação da informação musical. A representação proposta refere-se aos padrões rítmicos das músicas, uma vez que o ritmo configura um aspecto musical significante na discriminação dos gêneros. Os padrões rítmicos são estabelecidos pela dependência temporal das notas musicais presentes na percussão, de forma que cada música é representada por um vetor de probabilidades condicionais entre pares e trios de notas computadas pelo uso de cadeias de Markov de primeira e segunda ordem. Os padrões rítmicos de diversos gêneros são explorados em aplicações como: classificação, síntese musical, recomendação musical, humor/emoção em música, e análise de aspectos evolutivos. Constatou-se que estes, como estabelecidos neste estudo, são sensíveis à discriminação dos gêneros, evidenciando sequências de notas que são comuns aos mesmos, e sequências que são distintas e características de cada um. Uma segunda motivação deste projeto é o uso de medidas topológicas de redes e dígrafos de músicas para a análise dos dados. Comunidades obtidas nestas redes proporcionaram a definição de uma abordagem não supervisionada, a qual apresentou taxas de desempenho superiores ao agrupamento hierárquico. A determinação das características rítmicas de cada música motivou o desenvolvimento de estratégias para a composição automática e para a geração de listas de reprodução, assim como para a averiguação da relação destes padrões com aspectos emotivos. Por fim, uma análise estatística da evolução do ritmo de diferentes gêneros é desempenhada, na qual verificou-se a presença de mecanismos de inovação e recuperação. Estes mecanismos parecem ser consequência da competição entre fatores que favorecem a inovação de material musical, e fatores que a previnem, como, por exemplo, a obediência às regras de composição que mantém as características fundamentais de cada gênero. / Musical databases have increased in number and size continuously, paving the way to large amounts of online music data, including discographies, biographies and lyrics. The constant growth of data on the Internet has attracted musical research for developing tools to analyze and classify music data. The main objective of such tools is to extract reliable information to adequately represent and compact music content in databases. In this context, musical genres are particularly interesting descriptors, since they have being used for years to organize music collections, reflect interaction between cultures and summarize common features (or patterns) between musical pieces. The main motivation of this study is to propose a original and low cost framework to represent musical genres, as well as investigate the contribution of this representation in applications and studies that are placed in the context of music information retrieval researches. The representation of music content is referred to the rhythmic patterns, since rhythm configures a significant aspect in the discrimination of musical genres. The rhythmic patterns are determined by the temporal dependency of the musical notes present in the percussion, so that each song is represented by a vector of conditional probabilities between pairs and triples of notes, computed by the use of first and second order Markov chains. The rhythm patterns from distinct genres are investigated in applications such as: classification, music synthesis, music recommendation, mood/emotion in music, and analysis of evolutionary aspects. The main finding is that the rhythmic patterns as established in this study are sensitive to the genre discrimination, suggesting that there are sequences of notes common to all genres, and sequences that are distinct and characteristics of each one. A second motivation for this study is the use of topological measures of music networks and music digraphs for the data analysis. Communities obtained from these networks contributed to the definition of an unsupervised approach that provided performance rates superior to the hierarchical clustering. The rhythmic patterns also motivated the development of strategies for automatic composition, for the generation of playlists, and the analysis of the relationship between these patterns and emotional aspects. Finally, a statistical analysis of the rhythm evolution is performed, in which the principal finding is the presence of innovation and retrieval mechanisms for all genres. These mechanisms seems to be the result of the competition between factors that promote the innovation, and factors that prevent it, as, for example, the obedience to composition rules that retains the fundamental characteristics of each genre.

Diferentes sistemas do mundo real podem ser representados por redes. As redes são estruturas nas quais seus vértices (nós) representam entidades e links representam relações entre essas entidades. Além disso, as redes caracterizam-se por ser estruturas dinâmicas, o que implica na rápida aparição e desaparição de entidades e seus relacionamentos. Nesse cenário, um dos problemas importantes a serem enfrentados no contexto das redes, é da predição de links, isto é, prever a ocorrência futura de um link ainda não existente entre dois vértices com base nas informações já existentes. A importância da predição de links deve-se ao fato de ter aplicações na recuperação de informação, identificação de interações espúrias e, ainda, na avaliação de mecanismos de evolução das redes. Para enfrentar o problema da predição de links, a maioria dos métodos utiliza informações da vizinhança topológica das redes para atribuir um valor que represente a probabilidade de conexão futura entre um par de vértices analisados. No entanto, recentemente têm aparecido métodos híbridos, caracterizados por usar outras informações além da vizinhança topológica, sendo as informações das comunidades as normalmente usadas, isso, devido ao fato que, ao serem grupos de vértices densamente ligados entre si e esparsamente ligados com vértices de outros grupos, fornecem informações que podem ser úteis para determinar o comportamento futuro das redes. Assim, neste trabalho são apresentadas duas propostas na linha dos métodos baseados nas informações das comunidades para predição de links. A primeira proposta consiste em um novo índice de similaridade que usa as informações dos vértices pertencentes a mesma comunidade na vizinhança de um par de vértices analisados, bem como as informações dos vértices pertencentes a diferentes comunidades nessa mesma vizinhança. A segunda proposta consiste de um conjunto de índices obtidos a partir da reformulação de algumas propostas já existentes, porém, inserindo neles informações dos vértices pertencentes unicamente à mesma comunidade na vizinhança topológica de um par de vértices analisados. Experimentos realizados em dez redes complexas de diferentes domínios demonstraram que, em geral, os índices propostos obtiveram desempenho superior às abordagens usuais / Different real-world systems can be represented as networks. Networks are structures in which vertices (nodes) represent entities and links represent relationships between these entities. Moreover, networks are dynamic structures, which implies rapid appearance and disappearance of entities and their relationships. In this scenario, the link prediction problem attempts to predict the future existence of a link between a pair of vertices considering existing information. The link prediction importance is due to the fact of having different applications in areas such as information retrieval, identification of spurious interactions, as well as for understanding mechanisms of network evolution. To address the link prediction problem, many proposals use topological information to assign a value that represents the likelihood of a future connection between a pair of vertices. However, hybrid methods have appeared recently. These methods use additional information such as community information. Communities are groups of vertices densely connected among them and sparsely connected to vertices from other groups, providing useful information to determinate the future behavior of networks. So, this research presents two proposals for link prediction based on communities information. The first proposal consists of a new similarity index that uses information about the communities that the vertices in the neighborhood of a analyzed pair of vertices belong. The second proposal is a set of indices obtained from the reformulation of various existing proposals, however, using only the information from vertices belonging to the same community in the neighborhood of a pair of vertices analyzed. Experiments conducted in ten complex networks of different fields show the proposals outperform traditional approaches

Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. / Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

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 problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta Tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto, o custo computacional foi alto, principalmente o da metaheurística para o modelo de maximização da modularidade. Com o passar dos anos, estudos revelaram que a formulação que maximiza a modularidade das partições possui algumas limitações. A fim de promover uma alternativa à altura do modelo de maximização da modularidade, esta Tese propõe novas formulações matemáticas de agrupamento em grafos com e sem pesos que visam encontrar partições cujos clusters apresentem alta conectividade. Além disso, as formulações propostas são capazes de prover partições sem a necessidade de definição prévia do número de clusters. Testes com centenas de grafos com pesos comprovaram a eficiência dos modelos propostos. Comparando as partições provenientes de todos os modelos estudados nesta Tese, foram observados melhores resultados em uma das novas formulações propostas, que encontrou partições bastante satisfatórias, superiores às outras existentes, até mesmo para a de maximização de modularidade. Os resultados apresentaram alta correlação com a classificação real dos dados simulados e reais, sendo esses últimos, em sua maioria, de origem biológica / Graph clustering aims at identifying highly connected groups or clusters of nodes of a graph. This problem can assume others nomenclatures, such as: graph partitioning problem and community detection problem. There are many mathematical formulations to model this problem, each one with advantages and disadvantages. Most of these formulations have the disadvantage of requiring the definition of the number of clusters in the final partition. Nevertheless, this type of information is not found in graphs for clustering, i.e., whose data are unlabeled. This is one of the reasons for the popularization in the last decades of the measure known as modularity, which is being maximized to find graph partitions. This formulation does not require the definition of the number of clusters of the partitions to be produced, and produces high quality partitions. In this Thesis, Greedy Randomized Search Procedures metaheuristics for two existing graph clustering mathematical formulations are proposed: one for the maximization of the partition modularity and the other for the maximization of the intra-cluster similarity. The results obtained by these proposed metaheuristics outperformed the results from other heuristics found in the literature. However, their computational cost was high, mainly for the metaheuristic for the maximization of modularity model. Along the years, researches revealed that the formulation that maximizes the modularity of the partitions has some limitations. In order to promote a good alternative for the maximization of the partition modularity model, this Thesis proposed new mathematical formulations for graph clustering for weighted and unweighted graphs, aiming at finding partitions with high connectivity clusters. Furthermore, the proposed formulations are able to provide partitions without a previous definition of the true number of clusters. Computational tests with hundreds of weighted graphs confirmed the efficiency of the proposed models. Comparing the partitions from all studied formulations in this Thesis, it was possible to observe that the proposed formulations presented better results, even better than the maximization of partition modularity. These results are characterized by satisfactory partitions with high correlation with the true classification for the simulated and real data (mostly biological)

No contexto de Redes Complexas, particularmente das redes sociais, grupos de objetos densamente conectados entre si, esparsamente conectados a outros grupos, são denominados de comunidades. Detecção dessas comunidades tornou-se um campo de crescente interesse científico e possui inúmeras aplicações práticas. Nesse contexto, surgiram várias pesquisas sobre estratégias multinível para particionar redes com elevada quantidade de vértices e arestas. O objetivo dessas estratégias é diminuir o custo do algoritmo de particionamento aplicando-o sobre uma versão reduzida da rede original. Uma possibilidade dessa estratégia, ainda pouco explorada, é utilizar heurísticas de refinamento local para melhorar a solução final. A maioria das abordagens de refinamento exploram propriedades gerais de redes complexas, tais como corte mínimo ou modularidade, porém, não exploram propriedades inerentes de domínios específicos. Por exemplo, redes sociais são caracterizadas por elevado coeficiente de agrupamento e assortatividade significativa, consequentemente, maximizar tais características pode conduzir a uma boa solução e uma estrutura de comunidades bem definida. Motivado por essa lacuna, neste trabalho é proposto um novo algoritmo de refinamento, denominado RSim, que explora características de alto grau de transitividade e assortatividade presente em algumas redes reais, em particular em redes sociais. Para isso, adotou-se medidas de similaridade híbridas entre pares de vértices, que utilizam os conceitos de vizinhança e informações de comunidades para interpretar a semelhança entre pares de vértices. Uma análise comparativa e sistemática demonstrou que o RSim supera os algoritmos de refinamento habituais em redes com alto coeficiente de agrupamento e assortatividade. Além disso, avaliou-se o RSim em uma aplicação real. Nesse cenário, o RSim supera todos os métodos avaliado quanto a eficiência e eficácia, considerando todos os conjuntos de dados selecionados. / In the context of complex networks, particularly social networks, groups of densely interconnected objects, sparsely linked to other groups are called communities. Detection of these communities has become a field of increasing scientific interest and has numerous practical applications. In this context, several studies have emerged on multilevel strategies for partitioning networks with high amount of vertices and edges. The goal of these strategies is to reduce the cost of partitioning algorithm by applying it on a reduced version of the original network. The possibility for this strategy, yet little explored, is to apply local refinement heuristics to improve the final solution. Most refinement approaches explore general properties of complex networks, such as minimum cut or modularity, however, do not exploit inherent properties of specific domains. For example, social networks are characterized by high clustering coefficient and significant assortativity, hence maximize such characteristics may lead to a good solution and a well-defined community structure. Motivated by this gap, in this thesis, we propose a new refinement algorithm, called RSim, which exploits characteristics of high degree of transitivity and assortativity present in some real networks, particularly social networks. For this, we adopted hybrid similarity measures between pairs of vertices, using the concepts of neighborhood and community information to interpret the similarity between pairs of vertices. A systematic and comparative analysis showed that the RSim statistically outperforms usual refinement algorithms in networks with high clustering coefficient and assortativity. In addition, we assessed the RSim in a real application. In this scenario, the RSim surpasses all evaluated methods in efficiency and effectiveness, considering all the selected data sets.

No contexto de Redes Complexas, particularmente das redes sociais, grupos de objetos densamente conectados entre si, esparsamente conectados a outros grupos, são denominados de comunidades. Detecção dessas comunidades tornou-se um campo de crescente interesse científico e possui inúmeras aplicações práticas. Nesse contexto, surgiram várias pesquisas sobre estratégias multinível para particionar redes com elevada quantidade de vértices e arestas. O objetivo dessas estratégias é diminuir o custo do algoritmo de particionamento aplicando-o sobre uma versão reduzida da rede original. Uma possibilidade dessa estratégia, ainda pouco explorada, é utilizar heurísticas de refinamento local para melhorar a solução final. A maioria das abordagens de refinamento exploram propriedades gerais de redes complexas, tais como corte mínimo ou modularidade, porém, não exploram propriedades inerentes de domínios específicos. Por exemplo, redes sociais são caracterizadas por elevado coeficiente de agrupamento e assortatividade significativa, consequentemente, maximizar tais características pode conduzir a uma boa solução e uma estrutura de comunidades bem definida. Motivado por essa lacuna, neste trabalho é proposto um novo algoritmo de refinamento, denominado RSim, que explora características de alto grau de transitividade e assortatividade presente em algumas redes reais, em particular em redes sociais. Para isso, adotou-se medidas de similaridade híbridas entre pares de vértices, que utilizam os conceitos de vizinhança e informações de comunidades para interpretar a semelhança entre pares de vértices. Uma análise comparativa e sistemática demonstrou que o RSim supera os algoritmos de refinamento habituais em redes com alto coeficiente de agrupamento e assortatividade. Além disso, avaliou-se o RSim em uma aplicação real. Nesse cenário, o RSim supera todos os métodos avaliado quanto a eficiência e eficácia, considerando todos os conjuntos de dados selecionados. / In the context of complex networks, particularly social networks, groups of densely interconnected objects, sparsely linked to other groups are called communities. Detection of these communities has become a field of increasing scientific interest and has numerous practical applications. In this context, several studies have emerged on multilevel strategies for partitioning networks with high amount of vertices and edges. The goal of these strategies is to reduce the cost of partitioning algorithm by applying it on a reduced version of the original network. The possibility for this strategy, yet little explored, is to apply local refinement heuristics to improve the final solution. Most refinement approaches explore general properties of complex networks, such as minimum cut or modularity, however, do not exploit inherent properties of specific domains. For example, social networks are characterized by high clustering coefficient and significant assortativity, hence maximize such characteristics may lead to a good solution and a well-defined community structure. Motivated by this gap, in this thesis, we propose a new refinement algorithm, called RSim, which exploits characteristics of high degree of transitivity and assortativity present in some real networks, particularly social networks. For this, we adopted hybrid similarity measures between pairs of vertices, using the concepts of neighborhood and community information to interpret the similarity between pairs of vertices. A systematic and comparative analysis showed that the RSim statistically outperforms usual refinement algorithms in networks with high clustering coefficient and assortativity. In addition, we assessed the RSim in a real application. In this scenario, the RSim surpasses all evaluated methods in efficiency and effectiveness, considering all the selected data sets.